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

Reply via email to