How to get intersection of very large polyshapes?

I have a large polygon and some small polygons, and I need to determine the area of intersection between them. Typically, my approach would involve creating polyshape objects for each polygon and using functions to calculate their intersection and area. However, the process of generating the polyshape for the larger polygon is causing my system to become unresponsive, consuming large chunks of memory likely due to the size and complexity of the shape.

Given this challenge, I’m looking for alternative methods or strategies to effectively compute the area of intersection without experiencing performance issues. Are there specific algorithms, libraries, or techniques that could help me handle this problem more efficiently? What would you recommend for managing such large polygons in the context of intersection area calculations?

Answer 1

[Gojo]

Hey Tom,

In order to compute area of intersection between polygons where one of the polygon is very large, I would suggest you the following:

1) Reduce the number of vertices as much as possible.

a) Remove duplicates using simplify

b) If you can further decrease the number of points while maintaining the overall shape,

Use Polygon Simplification. Note that this may reduce the accuracy.

2) Get the exact vertices that are inside the large polygon to effectively get the region of your interest and eventually compute its area.

3) For an intersection to happen, one point would lie inside of a polygon and another would be outside to connect the line segment. Get the vertices where one of them is inside a polygon and adjacent one is outside, draw the line segment and have it intersect with the polygon. In this way you can compute the intersection region's area.

I have tried to explain my approach in another MATLAB Answer more extensively here, which is very similar to your query.

I hope this was helpful!

[Tom]

Thanks for the quick response and giving me some direction. Let me try out the suggestions!

[John D'Errico]

This statement is incorrect!

"For an intersection to happen, one point would lie inside of a polygon and another would be outside to connect the line segment. "

I'm sorry, but totally untrue. Two polygons may easily intersect, yet no vertex of one polygon lies inside the other.

P1 = polyshape([0 0;0 1;1 0]);
P2 = polyshape([1/2 -1;1/2 1;1 1]);
plot(P1)
hold on
plot(P2)
grid on
hold off

No vertex lies inside the other polygon, yet the intersection is non-trivial.

P3 = intersect(P1,P2)

P3 = 
  polyshape with properties:

      Vertices: [4x2 double]
    NumRegions: 1
      NumHoles: 0

area(P3)

ans = 0.1000

[Gojo]

Thanks @John D'Errico for pointing it out, I made an oversight there. I guess then a better idea would be to process the larger polygon as chunks and check for intersections with the smaller ones, considering the memory limitations.

[John D'Errico]

Regardless, I think many of your ideas will be helpful. Make big problems smaller, by use of simplification if at all possible. Sadly, big problems are sometimes just ... big.