Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Dealing with "cracks" in the unary_union of several imprecise Polygons?

Tags:

python

shapely

I used shapely.ops.unary_union on a number of 6-sided shapely.geometry.Polygons, and obtained the following shape A:

An irregular polygon shaped with a "honeycomb" shape, with "cracks" in it.

Note how there are two "cracks" in the upper part. These are not intended, and are presumably caused by some floating-point edge cases.

If you construct another shape B that sits inside of A, and if A happens to intersect one of these "cracks", then A.covers(B) will be False!

In my particular case, this leads to a test suite failure, because A.covers(B) is supposed to be an invariant. Therefore I need to deal with this somehow. Is there some algorithm I can use to "seal" these cracks?

In practice, these "cracks" will not affect the functioning of the application, because we only care about the outer border of A covering B. Thus I am open to solutions that adjust the individual hexagons in order to make the cracks go away by introducing overlaps.

However, I cannot accept the outer border of this shape changing, because that would actually no longer be testing the application as it is intended to be used.

To summarize, I want the outcome to look like this (my hand-edited version):

The same polygon, without any cracks

like image 521
shadowtalker Avatar asked Oct 20 '25 11:10

shadowtalker


1 Answers

You can fix this by buffering and un-buffering the shape.

Here's an example of a polygon with a small crack:

from shapely.geometry import Polygon
bad_polygon = Polygon([[0, 0], [1, 0], [1, 0.4999], [0.5, 0.5], [1, 0.5001], [1, 1], [0, 1], [0, 0]])

polygon crack

To fix it, expand the shape slightly, and contract it the same amount, using the buffer() method.

tol = 1e-4
bad_polygon.buffer(tol).buffer(-tol)

The value tol must be at least as large as half the distance across the crack at the crack's widest point.

no crack

like image 171
Nick ODell Avatar answered Oct 23 '25 01:10

Nick ODell



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!