Is there a way to verify whether a non-empty intersection exists between two simple polygons (not necessarily convex) using the Chazelle's simplicity test ?
Using Chazelle's simplicity test to verify simple polygons intersection
1
$\begingroup$
computational-geometry
-
0Perhaps connecting the two polygons together by a "bridge" to form one polygon might allow Chazelle's algorithm to answer the question. But: Are you interested in this for theoretical purposes, or for pragmatic reasons? If the latter, it would be far easier to use a plane-sweep algorithm than it would be to implement Chazelle's algorithm. – 2010-12-20
1 Answers
2
Independent of Chazelle, a discussion of the case of intersecting convex polygons can be found at:
-
0Yes, although note that the convex-convex case is very special and will not help much for two simple polygons. – 2010-12-20