1   /* Copyright 2002-2025 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.Circle;
26  import org.hipparchus.geometry.spherical.twod.Edge;
27  import org.hipparchus.geometry.spherical.twod.S2Point;
28  import org.hipparchus.geometry.spherical.twod.Sphere2D;
29  import org.hipparchus.geometry.spherical.twod.SphericalPolygonsSet;
30  import org.hipparchus.geometry.spherical.twod.SubCircle;
31  import org.hipparchus.geometry.spherical.twod.Vertex;
32  
33  /** BSP Tree visitor aimed at finding a point strictly inside a spherical zone.
34   * <p>
35   * This class is heavily based on the class PropertiesComputer from the
36   * Hipparchus library, also distributed under the terms of
37   * the Apache Software License V2.
38   * </p>
39   * @author Luc Maisonobe
40   */
41  class InsidePointFinder implements BSPTreeVisitor<Sphere2D, S2Point, Circle, SubCircle> {
42  
43      /** Zone of interest. */
44      private final SphericalPolygonsSet zone;
45  
46      /** Inside point. */
47      private S2Point insidePointSecondChoice;
48  
49      /** Inside point. */
50      private S2Point insidePointFirstChoice;
51  
52      /** Simple constructor.
53       * @param zone zone of interest
54       */
55      InsidePointFinder(final SphericalPolygonsSet zone) {
56          this.zone                    = zone;
57          this.insidePointFirstChoice  = null;
58          this.insidePointSecondChoice = null;
59      }
60  
61      /** {@inheritDoc} */
62      @Override
63      public Order visitOrder(final BSPTree<Sphere2D, S2Point, Circle, SubCircle> node) {
64          return Order.MINUS_PLUS_SUB;
65      }
66  
67      /** {@inheritDoc} */
68      @Override
69      public void visitInternalNode(final BSPTree<Sphere2D, S2Point, Circle, SubCircle> node) {
70      }
71  
72      /** {@inheritDoc} */
73      @Override
74      public void visitLeafNode(final BSPTree<Sphere2D, S2Point, Circle, SubCircle> node) {
75  
76          // we have already found a good point
77          if (insidePointFirstChoice != null) {
78              return;
79          }
80  
81          if ((Boolean) node.getAttribute()) {
82  
83              // transform this inside leaf cell into a simple convex polygon
84              final SphericalPolygonsSet convex =
85                      new SphericalPolygonsSet(node.pruneAroundConvexCell(Boolean.TRUE,
86                                                                          Boolean.FALSE,
87                                                                          null),
88                                                                          zone.getTolerance());
89  
90              // extract the start of the single loop boundary of the convex cell
91              final List<Vertex> boundary = convex.getBoundaryLoops();
92              final Vertex start = boundary.get(0);
93              int n = 0;
94  
95              // Initialize centroid coordinates
96              Vector3D centroid = Vector3D.ZERO;
97  
98              // Iterate through each edge in the boundary loop
99              for (Edge e = start.getOutgoing(); n == 0 || e.getStart() != start; e = e.getEnd().getOutgoing()) {
100                 // Get the 3D coordinates of the start and end points of the edge
101                 final Vector3D startPoint = e.getStart().getLocation().getVector();
102                 final Vector3D endPoint   = e.getEnd().getLocation().getVector();
103 
104                 // Add the coordinates of the start and end points to the centroid
105                 centroid = centroid.add(startPoint).add(endPoint);
106 
107                 // Increment the counter
108                 n++;
109             }
110 
111             // Calculate the average centroid coordinates
112             centroid = centroid.scalarMultiply(1.0 / (2 * n));
113 
114             // Project the centroid coordinates onto the sphere to get the candidate point
115             final S2Point candidate = new S2Point(centroid.normalize());
116 
117             // check the candidate point is really considered inside
118             // it may appear outside if the current leaf cell is very thin
119             // and checkPoint selects another (very close) tree leaf node
120             if (zone.checkPoint(candidate) == Location.INSIDE) {
121                 insidePointFirstChoice = candidate;
122             } else {
123                 insidePointSecondChoice = candidate;
124             }
125 
126         }
127 
128     }
129 
130     /** Get the inside point.
131      * @return inside point, or null if the region is empty
132      */
133     public S2Point getInsidePoint() {
134         return insidePointFirstChoice != null ? insidePointFirstChoice : insidePointSecondChoice;
135     }
136 
137 }