New Intersection Algorithm of Convex Polygons Based on Voronoi Diagrams

A new fast and easy to implement tracing algorithm is presented for querying the intersection points of two convex polygons. We trace two edges to find the intersection points always along the boundaries of the union and intersection of P and Q respectively, which is different from O´Rourke ´s method that traces two edges always along P and Q respectively; and we utilizes a simple method to decide which edge to be advanced next step by using the space adjacency recording by polygons´ outer Voronoi diagrams. Compared with O´Rourke´s algorithm considered as the simplest algorithm available usually, the algorithm in this paper is more comprehensible; and it´s easy to implement and robust. The algorithm can also be used to query one intersection point of a convex polygon and a general polygon in a special virtual indoor scene to detect collision.