Jump to content
  • Advertisement
Sign in to follow this  
goocreations

Determine the intersecting area of a polygon

This topic is 2854 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

As the heading states, I'm looking for an efficient way of calculating the area which are shared by both a circle and an polygon.

What I have is the xy-coordinates for every corner of the polygon, and the xy-coordinate of the center of the circle and the radius of the circle.

Are there any ideas? Any creativity is welcome.

Share this post


Link to post
Share on other sites
Advertisement
Note: I assume convex polygons.

The way I do this is to walk the polygon and build a polygon from the intersection points that resides inside of the circle. As well as that polygon, you also have circular segments who's areas combined with the area of the inner polygon is the intersection area.

Of course you would do something like an AABB check to discard the two objects if they can not possible intersect; aswell as determining if the circle is entirely contained within the polygon, or the polygon is entirely contained within the circle.

My method (which is quite messy as it was a quick prototype so i won't post it out of embarrasment :P) goes along the lines of:

# test AABB of circle/polygon
# iterate polygon normals (my normals also store the the projected length of the polygon against the normals) to both determine if the circle/polygon could actually intersect at all, aswell as if the circle is entirely contained.
# if circle is entirely contained, we can stop here and return circle area

# if the circle is not entirely contained and the normals show intersection, then based on the normal which had the greatest penetration, evaluate the projection of the circle onto that edge to determine the circle does indeed intersect the polygon. (Up to this point, bar the testing for containment this is equivalent to seperating axis test for polygon-circle)
# build the inner polygon by walking the polygon, at this point also determine if the polygon is entirely contained.
# if it is entire contained, it's easy, we can stop here and return polygon area.

# walk the inner polygon computing it's area and the area contributed by any required circular segments on the edges of the inner polygon.

to determine which edges require circular segments to be calculate for, i add metadata to the inner polygon whilst building it depending on which vertices of the original polygon are inside/outside etc which are used in the last step to know if i need to perform the circular segment calculation for that edge.

Share this post


Link to post
Share on other sites
here's a visual description of the general case for my algorithm.



red polygon being the inner polygon, with the blue circular segments which come together to give the intersection area.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!