Cover polygon with minimal number of overlapping polygons at fixed positions
Pawel
How to select the minimal number of polygons from a set of polygons with fixed positions, whose union covers the input polygon?
For example, let's consider the following input, where the green polygons are the queried set and the blue one is the query:
The correct covering would be with two polygons:
How to calculate which polygons most efficiently cover the input area (minimizing the number of selected polygons)?
Pawel
The solution that seems to give correct results is the following:
Clip all polygons to the queried area
Divide each of the clipped polygon with any others that intersect it, eliminating any duplicates - let's call this operation "chopping". For example, such operation would produce the following non-overlapping polygons:
From the following polygons (clipped by range):
All of the chopped polygons represent the universe in the set covering terms; the chopped polygons covered by a single clipped cover polygon represent a subset
Pre-select all subsets corresponding to the polygons that are not fully covered by the union of other polygons.
Use the approximate algorithm to find the minimum set cover (as described here)
I've implemented this using GeoTools. Here's the code: https://github.com/w-k/MinimalCoverage and the archive with the jar and the dependencies can be downloaded from here: https://github.com/w-k/MinimalCoverage/releases.
I've based this on Ante's answer which was very valuable but did not provide the correct solution. It is incorrect because satisfying the requirement that all intersection parts be covered, results in excessive coverage of the query polygon. For example, the cover polygons clipped by the range polygon (as in the picture above) produce the following common parts:
In order to cover all of the common parts we would have to select all three cover polygons (the middle common part is not entirely covered by either the leftmost nor the rightmost polygon).
Collected from the Internet
Please contact [email protected] to delete if infringement.
edited at
- Prev: How to compute a column that depends on a function that uses the value of a variable of each row?
- Next: Conditional on pandas DataFrame's
Related
Related Related
- 1
Minimal number of groups necessary to cover user/product permissions
- 2
Polygon created by subtracted polygons
- 3
MYSQL polygons that contains a polygon
- 4
Polygon created by subtracted polygons
- 5
Points in Polygon, multiple polygons
- 6
Overlapping polygons in Python PIL
- 7
Boost polygon discards input polygons
- 8
Merging intersecting polygons to single polygon
- 9
CSS background fixed and cover
- 10
GLSL - How to avoid polygons overlapping?
- 11
position: fixed overlapping page
- 12
fixed position header overlapping
- 13
Overlapping dynamic fixed header
- 14
Position fixed overlapping issue?
- 15
Fixed notifications overlapping
- 16
Avoiding overlapping with fixed element
- 17
Artifacts similar to overlapping polygon faces
- 18
Minimal Vertex Cover using Meet-in-the-Middle
- 19
how to find the minimal cover for a set of functional dependencies?
- 20
Plot ggplot polygons with holes with geom_polygon
- 21
Adding attributes to datapoints from overlapping polygons in qgis
- 22
Non-overlapping non-convex polygons
- 23
Non-overlapping non-convex polygons
- 24
Graph Planarity with Fixed Node Positions
- 25
string replacement of fixed positions in python
- 26
FileHelpers dynamic fixed field positions
- 27
fixed positions filling up div
- 28
FileHelpers dynamic fixed field positions
- 29
Minimal number of swaps?
Comments