# Determine the intersecting area of a polygon

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

## 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 on other sites
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 on other sites
thaks, i will try this

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

1. 1
Rutin
31
2. 2
3. 3
4. 4
5. 5

• 13
• 49
• 11
• 10
• 14
• ### Forum Statistics

• Total Topics
632965
• Total Posts
3009546
• ### Who's Online (See full list)

There are no registered users currently online

×