Jump to content
  • Advertisement
Sign in to follow this  
NMO

Calculating the intersection area of two polygons

This topic is 4111 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

Hi! As the subject says, I have two abitrary polygons which are intersecting. Both are coplanar too. Now I want to calculate the intersection area of these two polygons. Are there any good approaches for this problem??

Share this post


Link to post
Share on other sites
Advertisement
This is a difficult problem. The easier way to solve it is using a third-party library. I have used the GPC library before, and I was satisfied.

Share this post


Link to post
Share on other sites
Thank you for your answer, but is it really as complicated? I would really like to implement my own version. I don't have complicated things like self-intersecting or holes. Aren't there any good approaches??

Share this post


Link to post
Share on other sites
The only simple, robust approach I can think of is expressing each polygon as a union of convex polygons, computing the intersections of the convex polygons and putting the results back together. Even this is harder than it looks.

Share this post


Link to post
Share on other sites
Maybe i have found a sultion. When there is an intersection between two polys, at first i compute the intersection polygon(s). The hard thing is to compute the area
of these intersection polygons. To do this I have found an area calculation algorithm according to Gauß. I have tried some examples an all of them worked properly. :)

Share this post


Link to post
Share on other sites
Computing the area of an arbitrary polygon is a relatively trivial problem. Calculating the intersection of two arbitrary polygons in a robust manner is much much harder. How do you intend to do that part?

Share this post


Link to post
Share on other sites
Quote:
Computing the area of an arbitrary polygon is a relatively trivial problem.


Yes okay, but that was the main problem.

Quote:
Calculating the intersection of two arbitrary polygons in a robust manner is much much harder. How do you intend to do that part?


I did that already:

Click

And then to calculate the area of this intersecting polygon, I use a Gauß algorithm as mentioned before.

Share this post


Link to post
Share on other sites
Area = .5 * abs(x[0]*y[1]-x[1]*y[0] + x[1]*y[2]-x[2]*y[1] + ... + x[n-1]*y[0]-x[0]*y[n-1])


Is that what Gauss said?

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!