1 /* Copyright 2002-2021 CS GROUP
2 * Licensed to CS GROUP (CS) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * CS 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 * http://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 package org.orekit.models.earth.tessellation;
18
19 import java.util.List;
20
21 import org.hipparchus.geometry.euclidean.threed.Vector3D;
22 import org.hipparchus.geometry.partitioning.BSPTree;
23 import org.hipparchus.geometry.partitioning.BSPTreeVisitor;
24 import org.hipparchus.geometry.partitioning.Region.Location;
25 import org.hipparchus.geometry.spherical.twod.Edge;
26 import org.hipparchus.geometry.spherical.twod.S2Point;
27 import org.hipparchus.geometry.spherical.twod.Sphere2D;
28 import org.hipparchus.geometry.spherical.twod.SphericalPolygonsSet;
29 import org.hipparchus.geometry.spherical.twod.Vertex;
30
31 /** BSP Tree visitor aimed at finding a point strictly inside a spherical zone.
32 * <p>
33 * This class is heavily based on the class PropertiesComputer from the
34 * Hipparchus library, also distributed under the terms of
35 * the Apache Software License V2.
36 * </p>
37 * @author Luc Maisonobe
38 */
39 class InsideFinder implements BSPTreeVisitor<Sphere2D> {
40
41 /** Zone of interest. */
42 private final SphericalPolygonsSet zone;
43
44 /** Inside point. */
45 private S2Point insidePointSecondChoice;
46
47 /** Inside point. */
48 private S2Point insidePointFirstChoice;
49
50 /** Simple constructor.
51 * @param zone zone of interest
52 */
53 InsideFinder(final SphericalPolygonsSet zone) {
54 this.zone = zone;
55 this.insidePointFirstChoice = null;
56 this.insidePointSecondChoice = null;
57 }
58
59 /** {@inheritDoc} */
60 @Override
61 public Order visitOrder(final BSPTree<Sphere2D> node) {
62 return Order.MINUS_PLUS_SUB;
63 }
64
65 /** {@inheritDoc} */
66 @Override
67 public void visitInternalNode(final BSPTree<Sphere2D> node) {
68 }
69
70 /** {@inheritDoc} */
71 @Override
72 public void visitLeafNode(final BSPTree<Sphere2D> node) {
73
74 // we have already found a good point
75 if (insidePointFirstChoice != null) {
76 return;
77 }
78
79 if ((Boolean) node.getAttribute()) {
80
81 // transform this inside leaf cell into a simple convex polygon
82 final SphericalPolygonsSet convex =
83 new SphericalPolygonsSet(node.pruneAroundConvexCell(Boolean.TRUE,
84 Boolean.FALSE,
85 null),
86 zone.getTolerance());
87
88 // extract the start of the single loop boundary of the convex cell
89 final List<Vertex> boundary = convex.getBoundaryLoops();
90 final Vertex start = boundary.get(0);
91 int n = 0;
92 Vector3D sumB = Vector3D.ZERO;
93 for (Edge e = start.getOutgoing(); n == 0 || e.getStart() != start; e = e.getEnd().getOutgoing()) {
94 sumB = new Vector3D(1, sumB, e.getLength(), e.getCircle().getPole());
95 n++;
96 }
97
98 final S2Point candidate = new S2Point(sumB);
99
100 // check the candidate point is really considered inside
101 // it may appear outside if the current leaf cell is very thin
102 // and checkPoint selects another (very close) tree leaf node
103 if (zone.checkPoint(candidate) == Location.INSIDE) {
104 insidePointFirstChoice = candidate;
105 } else {
106 insidePointSecondChoice = candidate;
107 }
108
109 }
110
111 }
112
113 /** Get the inside point.
114 * @return inside point, or null if the region is empty
115 */
116 public S2Point getInsidePoint() {
117 return insidePointFirstChoice != null ? insidePointFirstChoice : insidePointSecondChoice;
118 }
119
120 }