1
$\begingroup$

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 ?

  • 0
    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.2010-12-20

1 Answers 1

2

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

http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html

http://www.springerlink.com/content/q744325k7350m237/

  • 0
    Yes, although note that the convex-convex case is very special and will not help much for two simple polygons.2010-12-20