Using Chazelle's simplicity test to verify simple polygons intersection

Question

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 ?

Perhaps 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. — Joseph O'Rourke, Dec 20 '10 at 15:43
See also https://math.stackexchange.com/questions/80798/detecting-polygon-self-intersection and https://math.stackexchange.com/questions/52733/equation-to-check-if-a-set-of-vertices-form-a-real-polygon — lhf, May 09 '22 at 11:00

score 2 · Answer 1 · edited May 09 '22 at 14:44

2

Independent of Chazelle, a discussion of the case of intersecting convex polygons can be found at:

edited May 09 '22 at 14:44

Glorfindel

3,955

answered Dec 05 '10 at 19:31

Joseph Malkevitch

5,035

Yes, although note that the convex-convex case is very special and will not help much for two simple polygons. – Joseph O'Rourke Dec 20 '10 at 15:36

Using Chazelle's simplicity test to verify simple polygons intersection

1 Answers1