2
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ Two books, Graphics Gems IV and Numerical Recipes, provide good discussion as well as source code. I recommend either. \$\endgroup\$
    – Throwback1986
    Feb 13, 2011 at 5:37
  • 1
    \$\begingroup\$ 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)? \$\endgroup\$
    – zacharmarz
    Feb 13, 2011 at 12:16
  • \$\begingroup\$ @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. \$\endgroup\$
    – bummzack
    Jan 24, 2013 at 20:19
  • \$\begingroup\$ You can get CS2 free, from Adobe; you can use that to view the code. Link: adobe.com/downloads/cs2_downloads/index.html \$\endgroup\$
    – ashes999
    Jan 24, 2013 at 20:31

2 Answers 2

Reset to default
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

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).

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Xavura
    Feb 12, 2011 at 19:04
  • \$\begingroup\$ @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). \$\endgroup\$
    – bummzack
    Jan 24, 2013 at 20:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .