iverase opened a new pull request, #13980:
URL: https://github.com/apache/lucene/pull/13980
One of the situation with David Eberly's algorithm for finding a bridge
between a hole and outer polygon was failing was the case of a polygon sharing
a vertex with the outer polygon. To fixed that we added a step to find shared
vertex between the hole and the polygon.
That worked well except on the situations where more than one hole was
sharing the same vertex with the outer polygon. In those cases, we might have
more than one vertex to choose from and we need to make sure we pick the right
one. The current algorithm test if the line joining the previous vertex if the
outer polygon band the next vertex from the hole intersects the polygon. This
worked well in many cases but it is not generic as it depends on the topology
of the union.
This commit tries to improve the algorithm by:
1) If there is only one vertex, then there is not further checks and that's
the one used.
2) if there is a common vertex, it first compute the signed area of the
join, if they have different sign, it chooses the negative one as that's the
convex union. If they have the same sign, it computes the angle of the join and
chooses the smallest angle.
I added a few test to check the different combinations and the new algorithm
seems resilient to them.
In addition I clean the tessellator class by removing some useless final
declarations for static methods and clean up the visibility of some internal
classes (no point of protected inner classes on a final class) and remove
unused methods. I clean up the tests too.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
