# Voronoi regions of a (convex) polygon

I'm looking to add circle-polygon collisions to my Separating Axis Theorem collision detection.

The metanet software tutorial (http://www.metanetsoftware.com/technique/tutorialA.html#section3) on SAT, which I discovered in the answer to a question I found when searching, talks about voronoi regions.

I'm having trouble finding material on how I would calculate these regions for an arbitrary convex polygon and also how I would determine if a point is in one + which.

The tutorial does contain source code but it's a .fla and I don't have Flash unfortunately.

-
Two books, Graphics Gems IV and Numerical Recipes, provide good discussion as well as source code. I recommend either. – Throwback1986 Feb 13 '11 at 5:37
What do you want to compute? Voronoi diagram or circle - convex polygon intersection test? What do you need to compute? Just bool (intersect x not intersect) or something more presice (points of intersection)? – zacharmarz Feb 13 '11 at 12:16
@ashes999 A `.fla` is not a compiled Flash-File. It's a source-file for the Flash IDE. The compiled files are `.swf` or `.swc` files. – bummzack Jan 24 '13 at 20:19
@bummzack thanks, clarified. – ashes999 Jan 24 '13 at 20:32

If you want to compute voronoi diagram of arbitrary (convex or non-convex) polygon, where elements are vertices and edges, you can use Fortune's sweep line algorithm, but you have to split polygon to line segments (edges). But I don't think you should use it - it's really hard to implement, especially for line segments.

In which region is your point is another problem (point location problem) - most used method is trapezoidal decomposition (I think) - it's build on space partitioning (your voronoi region) and search complexity should be O(log n).

I think you can find much easier way how to compute circle-polygon intersection test that with voronoi diagram and point location.

-

I didn't have to calculate voronoi regions for my SAT implementation. I implemented circle vs. polygon intersection as described here: http://www.sevenson.com.au/actionscript/sat/ and it worked fine (also have a look at the links at the bottom of the article).

-
That means looping through all of the vertices and computing the distance to the circle for each. (I think) distance squared could be used to get rid of the expensive square roots, but apparently voronoi regions eliminate the need to loop over the vertices altogether. Thank you for the links though, some good reading. – Xavura Feb 12 '11 at 19:04
@Xavura This is a very late answer to your comment, but: Unless your polygon consists of hundreds or thousands of vertices, I highly doubt you'll get any performance gain by implementing Voronoi regions. The general idea is to have a broad-phase (AABB vs. AABB or circle vs. circle test) first anyway, so you won't run SAT all the time (only during the narrow phase). – bummzack Jan 24 '13 at 20:23