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: issues-unsubscr...@lucene.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org