1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 /*
19 * This is not the original file distributed by the Apache Software Foundation
20 * It has been modified by the Hipparchus project
21 */
22 package org.hipparchus.geometry.spherical.twod;
23
24 import java.util.ArrayList;
25 import java.util.List;
26
27 import org.hipparchus.exception.MathRuntimeException;
28 import org.hipparchus.geometry.euclidean.threed.Vector3D;
29 import org.hipparchus.geometry.partitioning.BSPTree;
30 import org.hipparchus.geometry.partitioning.BSPTreeVisitor;
31 import org.hipparchus.util.FastMath;
32 import org.hipparchus.util.MathUtils;
33
34 /** Visitor computing geometrical properties.
35 */
36 class PropertiesComputer implements BSPTreeVisitor<Sphere2D, S2Point, Circle, SubCircle> {
37
38 /** Tolerance below which points are consider to be identical. */
39 private final double tolerance;
40
41 /** Summed area. */
42 private double summedArea;
43
44 /** Summed barycenter. */
45 private Vector3D summedBarycenter;
46
47 /** List of points strictly inside convex cells. */
48 private final List<Vector3D> convexCellsInsidePoints;
49
50 /** Simple constructor.
51 * @param tolerance below which points are consider to be identical
52 */
53 PropertiesComputer(final double tolerance) {
54 this.tolerance = tolerance;
55 this.summedArea = 0;
56 this.summedBarycenter = Vector3D.ZERO;
57 this.convexCellsInsidePoints = new ArrayList<>();
58 }
59
60 /** {@inheritDoc} */
61 @Override
62 public Order visitOrder(final BSPTree<Sphere2D, S2Point, Circle, SubCircle> node) {
63 return Order.MINUS_SUB_PLUS;
64 }
65
66 /** {@inheritDoc} */
67 @Override
68 public void visitInternalNode(final BSPTree<Sphere2D, S2Point, Circle, SubCircle> node) {
69 // nothing to do here
70 }
71
72 /** {@inheritDoc} */
73 @Override
74 public void visitLeafNode(final BSPTree<Sphere2D, S2Point, Circle, SubCircle> node) {
75 if ((Boolean) node.getAttribute()) {
76
77 // transform this inside leaf cell into a simple convex polygon
78 final SphericalPolygonsSet convex =
79 new SphericalPolygonsSet(node.pruneAroundConvexCell(Boolean.TRUE,
80 Boolean.FALSE,
81 null),
82 tolerance);
83
84 // extract the start of the single loop boundary of the convex cell
85 final List<Vertex> boundary = convex.getBoundaryLoops();
86 if (boundary.size() != 1) {
87 // this should never happen
88 throw MathRuntimeException.createInternalError();
89 }
90
91 // compute the geometrical properties of the convex cell
92 final double area = convexCellArea(boundary.get(0));
93 final Vector3D barycenter = convexCellBarycenter(boundary.get(0));
94 convexCellsInsidePoints.add(barycenter);
95
96 // add the cell contribution to the global properties
97 summedArea += area;
98 summedBarycenter = new Vector3D(1, summedBarycenter, area, barycenter);
99
100 }
101 }
102
103 /** Compute convex cell area.
104 * @param start start vertex of the convex cell boundary
105 * @return area
106 */
107 private double convexCellArea(final Vertex start) {
108
109 int n = 0;
110 double sum = 0;
111
112 // loop around the cell
113 for (Edge e = start.getOutgoing(); n == 0 || e.getStart() != start; e = e.getEnd().getOutgoing()) {
114
115 // find path interior angle at vertex
116 final Vector3D previousPole = e.getCircle().getPole();
117 final Vector3D nextPole = e.getEnd().getOutgoing().getCircle().getPole();
118 final Vector3D point = e.getEnd().getLocation().getVector();
119 double alpha = FastMath.atan2(Vector3D.dotProduct(nextPole, Vector3D.crossProduct(point, previousPole)),
120 -Vector3D.dotProduct(nextPole, previousPole));
121 if (alpha < 0) {
122 alpha += MathUtils.TWO_PI;
123 }
124 sum += alpha;
125 n++;
126 }
127
128 // compute area using extended Girard theorem
129 // see Spherical Trigonometry: For the Use of Colleges and Schools by I. Todhunter
130 // article 99 in chapter VIII Area Of a Spherical Triangle. Spherical Excess.
131 // book available from project Gutenberg at http://www.gutenberg.org/ebooks/19770
132 return sum - (n - 2) * FastMath.PI;
133
134 }
135
136 /** Compute convex cell barycenter.
137 * @param start start vertex of the convex cell boundary
138 * @return barycenter
139 */
140 private Vector3D convexCellBarycenter(final Vertex start) {
141
142 int n = 0;
143 Vector3D sumB = Vector3D.ZERO;
144
145 // loop around the cell
146 for (Edge e = start.getOutgoing(); n == 0 || e.getStart() != start; e = e.getEnd().getOutgoing()) {
147 sumB = new Vector3D(1, sumB, e.getLength(), e.getCircle().getPole());
148 n++;
149 }
150
151 return sumB.normalize();
152
153 }
154
155 /** Get the area.
156 * @return area
157 */
158 public double getArea() {
159 return summedArea;
160 }
161
162 /** Get the barycenter.
163 * @return barycenter
164 */
165 public S2Point getBarycenter() {
166 if (summedBarycenter.getNormSq() == 0) {
167 return S2Point.NaN;
168 } else {
169 return new S2Point(summedBarycenter);
170 }
171 }
172
173 /** Get the points strictly inside convex cells.
174 * @return points strictly inside convex cells
175 */
176 public List<Vector3D> getConvexCellsInsidePoints() {
177 return convexCellsInsidePoints;
178 }
179
180 }