Exception in thread "main" org.orekit.errors.OrekitInternalError: internal error, please notify development team by creating a new topic at https://forum.orekit.org

Exception in thread "main" org.orekit.errors.OrekitInternalError: internal error, please notify development team by creating a new topic at https://forum.orekit.org
	at org.orekit.models.earth.tessellation.EllipsoidTessellator.recurseMeetInside(EllipsoidTessellator.java:765)
	at org.orekit.models.earth.tessellation.EllipsoidTessellator.meetInside(EllipsoidTessellator.java:726)
	at org.orekit.models.earth.tessellation.EllipsoidTessellator.neighborExpandMesh(EllipsoidTessellator.java:367)
	at org.orekit.models.earth.tessellation.EllipsoidTessellator.sample(EllipsoidTessellator.java:266)
    public static void main(String[] args)  {

        final File home = new File(System.getProperty("user.home"));
        final File orekitData = new File(home, "orekit-data");
        DataProvidersManager manager = DataContext.getDefault().getDataProvidersManager();
        manager.addProvider(new DirectoryCrawler(orekitData));

        OneAxisEllipsoid earth = ReferenceEllipsoid.getWgs84(FramesFactory.getITRF(IERSConventions.IERS_2010, true));

        String targetArea = "282.97373079754315,38.210763014900365 282.97373079754315,38.210548438179174 282.97397756077252,38.210548438179174 282.97397756077252,38.210763014900365 282.97373079754315,38.210763014900365";
        
        String[] pointStrArray = targetArea.split(" ");
        List<GeodeticPoint> vertices = new ArrayList<>();
        for (int i = 0; i < pointStrArray.length; i++) {
            String[] point = pointStrArray[i].split(",");
            vertices.add(new GeodeticPoint(FastMath.toRadians(Double.parseDouble(point[1])), FastMath.toRadians(Double.parseDouble(point[0])), 0));
        }
        GeodeticPoint[] geodeticPointArray = vertices.toArray(new GeodeticPoint[0]);

        SphericalPolygonsSet zone = EllipsoidTessellator.buildSimpleZone( 1.0E-6, geodeticPointArray);

        final EllipsoidTessellator tessellator = new EllipsoidTessellator(earth, new DivertedSingularityAiming(zone), 1);
        final List<List<GeodeticPoint>> gpSample = tessellator.sample(zone, 4, 4);

        System.out.println("finished");
        
    }

test-polygon.geojson (332 Bytes)

If you change the tolerance to 1.0E-7, the following error occurs

Exception in thread "main" org.orekit.errors.OrekitException: maximal count (1,000) exceeded
	at org.orekit.models.earth.tessellation.EllipsoidTessellator.sample(EllipsoidTessellator.java:255)

I think I found the issue. The method used by the InsideFinder class to find interior points within spherical polygons has a problem.

The problem is that interior points are not guaranteed: Even if sumB points near the center of the polygon, there is no guarantee that the corresponding S2Point will actually lie inside the spherical polygon, especially when the polygon has a complex shape.

    /** {@inheritDoc} */
    @Override
    public void visitLeafNode(final BSPTree<Sphere2D> node) {

        // we have already found a good point
        if (insidePointFirstChoice != null) {
            return;
        }

        if ((Boolean) node.getAttribute()) {

            // transform this inside leaf cell into a simple convex polygon
            final SphericalPolygonsSet convex =
                    new SphericalPolygonsSet(node.pruneAroundConvexCell(Boolean.TRUE,
                                                                        Boolean.FALSE,
                                                                        null),
                                                                        zone.getTolerance());

            // extract the start of the single loop boundary of the convex cell
            final List<Vertex> boundary = convex.getBoundaryLoops();
            final Vertex start = boundary.get(0);
            int n = 0;
            Vector3D sumB = Vector3D.ZERO;
            for (Edge e = start.getOutgoing(); n == 0 || e.getStart() != start; e = e.getEnd().getOutgoing()) {
                sumB = new Vector3D(1, sumB, e.getLength(), e.getCircle().getPole());
                n++;
            }

            final S2Point candidate = new S2Point(sumB);

            // check the candidate point is really considered inside
            // it may appear outside if the current leaf cell is very thin
            // and checkPoint selects another (very close) tree leaf node
            if (zone.checkPoint(candidate) == Location.INSIDE) {
                insidePointFirstChoice = candidate;
            } else {
                insidePointSecondChoice = candidate;
            }

        }

    }

The calculation of the candidate point has a flaw. Currently, it sums up the direction vectors of each edge in the polygon, aiming to find an “average” direction, and then uses it to construct a candidate point. However, this method does not guarantee that the resulting point lies inside the polygon.

Problem Analysis:

  • Ambiguous Meaning of Summing Direction Vectors: Simply adding up the direction vectors of each edge does not accurately represent the “center” direction of the polygon.
  • Inability to Handle Concave Polygons: For concave polygons, even if the sum of all edge vectors points towards the polygon’s interior, there’s no guarantee that the final point will be inside.

Improvement Suggestion:

A more reliable approach is to calculate the centroid of the polygon and project this centroid onto the sphere as the candidate point.

Code Example:

// Initialize centroid coordinates
Vector3D centroid = Vector3D.ZERO;

// Iterate through each edge in the boundary loop
for (Edge e = start.getOutgoing(); n == 0 || e.getStart() != start; e = e.getEnd().getOutgoing()) {
    // Get the 3D coordinates of the start and end points of the edge
    Vector3D startPoint = e.getStart().getLocation().getVector();
    Vector3D endPoint = e.getEnd().getLocation().getVector();

    // Add the coordinates of the start and end points to the centroid
    centroid = centroid.add(startPoint).add(endPoint);

    // Increment the counter
    n++;
}

// Calculate the average centroid coordinates
centroid = centroid.scalarMultiply(1.0 / (2 * n));

// Project the centroid coordinates onto the sphere to get the candidate point
final S2Point candidate = new S2Point(centroid.normalize()); 

Hello @Sohnny,

First of all thank you for the detailed error message, code sample and associated ressource. This is the kind of practice that makes debugging much easier.

We can deduce from your second post that the problem lies within Hipparchus code. Have you actually tried your solution (which seems good to me by the way) ? If so then please open an issue here. You could also make a merge request if you feel motivated :wink:.

Cheers,
Vincent

Hello @Vincent
I’ve actually tried my solution, and everything seems to be working fine. By the way, this issue is not in the Hipparchus library, but in the orekit library. It seems that it would be difficult for me to open an issue or pull request since I don’t have a GitLab account.

Sohnny

My bad, I don’t know why i thought that the class was inside the Hipparchus library when i checked.

I’m opening the issue then :+1:.

UPDATE : Issue created, you can check it out here

Hello @Sohnny ,

I just accepted your account on Orekit’s Gitlab.

Maxime

1 Like

hello @Vincent ,
I have already submitted the MR.
Sohnny

1 Like

The method was explicitly designed to extract a convex polygon, this is the reason for the call to pruneAroundConvexCell and it was done precisely to avoid finding a point in a deep concave slots that would indeed be outside of the polygon.

[edit] If I remember correctly, the pruneAroundConvexCell method is based on an intrisic property of BSP trees: leaf cells are always convex and this is true in all topologies, even on the 2D sphere.

I guess we should look more precisely why this fails.

hello @luc
I previously thought it supported concave polygons, but now I understand it only supports convex polygons. My example uses a square. I investigated the getInsidePoint method in EllipsoidTessellator, and in my above example, it retrieved a point outside the convex polygon. During debugging, I found that the logic for getting the inner point in the visitLeafNode method of the InsideFinder class seems to have issues. I have provided my analysis and solution to this problem above. You can also try the example above.

1 Like