1   /* Copyright 2002-2024 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 InsidePointFinder 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      InsidePointFinder(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  
93              // Initialize centroid coordinates
94              Vector3D centroid = Vector3D.ZERO;
95  
96              // Iterate through each edge in the boundary loop
97              for (Edge e = start.getOutgoing(); n == 0 || e.getStart() != start; e = e.getEnd().getOutgoing()) {
98                  // Get the 3D coordinates of the start and end points of the edge
99                  final Vector3D startPoint = e.getStart().getLocation().getVector();
100                 final Vector3D endPoint   = e.getEnd().getLocation().getVector();
101 
102                 // Add the coordinates of the start and end points to the centroid
103                 centroid = centroid.add(startPoint).add(endPoint);
104 
105                 // Increment the counter
106                 n++;
107             }
108 
109             // Calculate the average centroid coordinates
110             centroid = centroid.scalarMultiply(1.0 / (2 * n));
111 
112             // Project the centroid coordinates onto the sphere to get the candidate point
113             final S2Point candidate = new S2Point(centroid.normalize());
114 
115             // check the candidate point is really considered inside
116             // it may appear outside if the current leaf cell is very thin
117             // and checkPoint selects another (very close) tree leaf node
118             if (zone.checkPoint(candidate) == Location.INSIDE) {
119                 insidePointFirstChoice = candidate;
120             } else {
121                 insidePointSecondChoice = candidate;
122             }
123 
124         }
125 
126     }
127 
128     /** Get the inside point.
129      * @return inside point, or null if the region is empty
130      */
131     public S2Point getInsidePoint() {
132         return insidePointFirstChoice != null ? insidePointFirstChoice : insidePointSecondChoice;
133     }
134 
135 }