Finding overlapping weighted polygons 'highest' area

1
votes

I have a number of polygons which are in the form of a list of coordinates. Each of these polygons represents an area on a global map and each has a weight.

I need to find the area on the map where this weight is the highest. This means that where polygons overlap the weight will be the sum of the two polygons for the intersection area. I would like to make the calculation as efficient as possible. Any help would be greatly appreciated.

1
pythonalgorithmmapsshapespolygons
Whar are the properties of the polygon? rectilinear, convex, concave, self-intersecting, etc.? – Paul
@GilbertAllen I have been looking at the intersections between them but so far I don't seen to be getting too far. – Humphrey
@Paul The polygons each represent an area such as a country. They won't be self-intersecting or rectilinear but they will be concave. – Humphrey
@Humphrey in that case the simplest solution would be to cluster the polygons by nearest neighbours and perform a transformation on each pair of neighbours (A , B) into three polygons A / B, B / A and A intersection B with the respective weights weight(A), weight(B) and weight(A) + weight(B) and refresh the cluster. Repeat this until no further intersections are found and you're done. – Paul
Thanks @Paul, that seems to have worked well. If you want to make that into an answer I can accept it. – Humphrey

1 Answers

1
votes

The simplest approach to this problem would be to cluster the polygons by nearest neighbours. This step is optional and only used to make the search for intersecting polygons more efficient. Instead the clustering can as well be omitted, which would require an exhaustive search for intersecting polygons.

In the next step you can replace two intersecting polygons A and B by three polygons as follows: a polygon that consists of the area of A without the intersection-area with the weight of A, an equivalent polygon for B, and a third polygon that covers the intersection-area of A and B with the added weights of A and B as weight. Replace A and B by the three generated polygons and update cluster. Repeat this step until no intersecting rectangles can be found and you're done.