3751661366

Build Type

push

github

Committed by GitHub

Commit Message

Improvements (#122)

Run Details

88 of 99 new or added lines in 7 files covered. (88.89%)

6 existing lines in 3 files now uncovered.

543 of 709 relevant lines covered (76.59%)

3.83 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.86

/mapbox_vector_tile/polygon.py

import pyclipper
from shapely.geometry.multipolygon import MultiPolygon
from shapely.geometry.polygon import Polygon
from shapely.ops import unary_union
from shapely.validation import explain_validity


def _coords(shape):
    """
    Return a list of lists of coordinates of the polygon. The list consists firstly of the list of exterior
    coordinates followed by zero or more lists of any interior coordinates.
    """

    assert shape.geom_type == "Polygon"
    coords = [list(shape.exterior.coords)]
    for interior in shape.interiors:
        coords.append(list(interior.coords))
    return coords


def _drop_degenerate_inners(shape):
    """
    Drop degenerate (zero-size) inners from the polygon.

    This is implemented as dropping anything with a size less than 0.5, as the polygon is in integer coordinates and
    the smallest valid inner would be a triangle with height and width 1.
    """
    assert shape.geom_type == "Polygon"

    new_inners = []
    for inner in shape.interiors:
        # need to make a polygon of the linearring to get the _filled_ area of
        # the closed ring.
        if abs(Polygon(inner).area) >= 0.5:
            new_inners.append(inner)

    return Polygon(shape.exterior, new_inners)


def _contour_to_poly(contour):
    poly = Polygon(contour)
    if not poly.is_valid:
        poly = poly.buffer(0)
    assert poly.is_valid, f"Contour {contour!r} did not make valid polygon {poly.wkt} because {explain_validity(poly)}"
    return poly


def _union_in_blocks(contours, block_size):
    """
    Generator which yields a valid shape for each block_size multiple of input contours. This merges together the
    contours for each block before yielding them.
    """
    n_contours = len(contours)
    for i in range(0, n_contours, block_size):
        j = min(i + block_size, n_contours)

        inners = []
        for c in contours[i:j]:
            p = _contour_to_poly(c)
            if p.geom_type == "Polygon":
                inners.append(p)
            elif p.geom_type == "MultiPolygon":
                inners.extend(p.geoms)
        holes = unary_union(inners)
        assert holes.is_valid

        yield holes


def _generate_polys(contours):
    """
    Generator which yields a valid polygon for each contour input.
    """
    for c in contours:
        p = _contour_to_poly(c)
        yield p


def _polytree_node_to_shapely(node):
    """
    Recurses down a Clipper PolyTree, extracting the results as Shapely objects.

    Returns a tuple of (list of polygons, list of children)
    """
    polygons = []
    children = []
    for ch in node.Childs:
        p, c = _polytree_node_to_shapely(ch)
        polygons.extend(p)
        children.extend(c)

    if node.IsHole:
        # Check expectations: a node should be a hole, _or_ return children. This is because children of holes must
        # be outers, and should be on the polygons list.
        assert len(children) == 0
        if node.Contour:
            children = [node.Contour]
        else:
            children = []

    elif node.Contour:
        poly = _contour_to_poly(node.Contour)

        # We add each inner one-by-one so that we can reject them individually if they cause the polygon to become
        # invalid. If the shape has lots of inners, then this can mean a proportional amount of work, and may take
        # 1,000s of seconds. Instead, we can group inners together, which reduces the number of times we call the
        # expensive 'difference' method.
        block_size = 200
        if len(children) > block_size:
            inners = _union_in_blocks(children, block_size)
        else:
            inners = _generate_polys(children)

        for inner in inners:
            # The difference of two valid polygons may fail, and in this  situation we'd like to be able to display
            # the polygon anyway. So we discard the bad inner and continue.
            #
            # See test_polygon_inners_crossing_outer for a test case.
            try:
                diff = poly.difference(inner)
            except Exception:
                continue

            if not diff.is_valid:
                diff = diff.buffer(0)

            # Keep this for when https://trac.osgeo.org/geos/ticket/789 is resolved.
            #
            # assert diff.is_valid, (
            #     f"Difference of {poly.wkt} and {inner.wkt} did not make valid polygon {diff.wkt} "
            #     f" because {explain_validity(diff)}"
            # )
            # NOTE: this throws away the inner ring if we can't produce a valid difference. Not ideal, but we'd
            # rather produce something that's valid than nothing.
            if diff.is_valid:
                poly = diff

        assert poly.is_valid
        if poly.geom_type == "MultiPolygon":
            polygons.extend(poly.geoms)
        else:
            polygons.append(poly)
        children = []

    else:
        # Check expectations: this branch gets executed if this node is not a hole, and has no contour. In that
        # situation we'd expect that it has no children, as it would not be possible to subtract children from
        # an empty outer contour.
        assert len(children) == 0

    return polygons, children


def _polytree_to_shapely(tree):
    polygons, children = _polytree_node_to_shapely(tree)

    # expect no left over children - should all be incorporated into polygons by the time recursion returns to the root.
    assert len(children) == 0

    union = unary_union(polygons)
    assert union.is_valid
    return union


def make_valid_pyclipper(shape):
    """
    Use the pyclipper library to "union" a polygon on its own. This operation uses the even-odd rule to determine
    which points are in the interior of the polygon, and can reconstruct the orientation of the polygon from that.
    The pyclipper library is robust, and uses integer coordinates, so should not produce any additional degeneracies.

    Before cleaning the polygon, we remove all degenerate inners. This is useful to remove inners which have
    collapsed to points or lines, which can interfere with the cleaning process.
    """

    # drop all degenerate inners
    clean_shape = _drop_degenerate_inners(shape)

    pc = pyclipper.Pyclipper()

    try:
        pc.AddPaths(_coords(clean_shape), pyclipper.PT_SUBJECT, True)

        # note: Execute2 returns the polygon tree, not the list of paths
        result = pc.Execute2(pyclipper.CT_UNION, pyclipper.PFT_EVENODD)

    except pyclipper.ClipperException:
        return MultiPolygon([])

    return _polytree_to_shapely(result)


def make_valid_polygon(shape):
    """
    Make a polygon valid. Polygons can be invalid in many ways, such as self-intersection, self-touching and
    degeneracy. This process attempts to make a polygon valid while retaining as much of its extent or area as possible.

    First, we call pyclipper to robustly union the polygon. Using this on its own appears to be good for "cleaning"
    the polygon.

    This might result in polygons which still have degeneracies according to the OCG standard of validity - as
    pyclipper does not consider these to be invalid. Therefore, we follow by using the `buffer(0)` technique to
    attempt to remove any remaining degeneracies.
    """
    assert shape.geom_type == "Polygon"

    shape = make_valid_pyclipper(shape)
    assert shape.is_valid
    return shape


def make_valid_multipolygon(shape):
    new_g = []

    for g in shape.geoms:
        if g.is_empty:
            continue

        valid_g = make_valid_polygon(g)

        if valid_g.geom_type == "MultiPolygon":
            new_g.extend(valid_g.geoms)
        else:
            new_g.append(valid_g)

    return MultiPolygon(new_g)


def make_it_valid(shape):
    """
    Attempt to make any polygon or multipolygon valid.
    """
    if shape.is_empty:
        return shape

    elif shape.geom_type == "MultiPolygon":
        shape = make_valid_multipolygon(shape)

    elif shape.geom_type == "Polygon":
        shape = make_valid_polygon(shape)

    return shape

1	import pyclipper	5✔
2	from shapely.geometry.multipolygon import MultiPolygon	5✔
3	from shapely.geometry.polygon import Polygon	5✔
4	from shapely.ops import unary_union	5✔
5	from shapely.validation import explain_validity	5✔
6
7
8	def _coords(shape):	5✔
9	"""
10	Return a list of lists of coordinates of the polygon. The list consists firstly of the list of exterior
11	coordinates followed by zero or more lists of any interior coordinates.
12	"""
13
14	assert shape.geom_type == "Polygon"	5✔
15	coords = [list(shape.exterior.coords)]	5✔
16	for interior in shape.interiors:	5✔
17	coords.append(list(interior.coords))	5✔
18	return coords	5✔
19
20
21	def _drop_degenerate_inners(shape):	5✔
22	"""
23	Drop degenerate (zero-size) inners from the polygon.
24
25	This is implemented as dropping anything with a size less than 0.5, as the polygon is in integer coordinates and
26	the smallest valid inner would be a triangle with height and width 1.
27	"""
28	assert shape.geom_type == "Polygon"	5✔
29
30	new_inners = []	5✔
31	for inner in shape.interiors:	5✔
32	# need to make a polygon of the linearring to get the _filled_ area of
33	# the closed ring.
34	if abs(Polygon(inner).area) >= 0.5:	5✔
35	new_inners.append(inner)	5✔
36
37	return Polygon(shape.exterior, new_inners)	5✔
38
39
40	def _contour_to_poly(contour):	5✔
41	poly = Polygon(contour)	5✔
42	if not poly.is_valid:	5✔
43	poly = poly.buffer(0)	5✔
44	assert poly.is_valid, f"Contour {contour!r} did not make valid polygon {poly.wkt} because {explain_validity(poly)}"	5✔
45	return poly	5✔
46
47
48	def _union_in_blocks(contours, block_size):	5✔
49	"""
50	Generator which yields a valid shape for each block_size multiple of input contours. This merges together the
51	contours for each block before yielding them.
52	"""
53	n_contours = len(contours)	5✔
54	for i in range(0, n_contours, block_size):	5✔
55	j = min(i + block_size, n_contours)	5✔
56
57	inners = []	5✔
58	for c in contours[i:j]:	5✔
59	p = _contour_to_poly(c)	5✔
60	if p.geom_type == "Polygon":	5✔
61	inners.append(p)	5✔
62	elif p.geom_type == "MultiPolygon":	5✔
63	inners.extend(p.geoms)	5✔
64	holes = unary_union(inners)	5✔
65	assert holes.is_valid	5✔
66
67	yield holes	5✔
68
69
70	def _generate_polys(contours):	5✔
71	"""
72	Generator which yields a valid polygon for each contour input.
73	"""
74	for c in contours:	5✔
75	p = _contour_to_poly(c)	5✔
76	yield p	5✔
77
78
79	def _polytree_node_to_shapely(node):	5✔
80	"""
81	Recurses down a Clipper PolyTree, extracting the results as Shapely objects.
82
83	Returns a tuple of (list of polygons, list of children)
84	"""
85	polygons = []	5✔
86	children = []	5✔
87	for ch in node.Childs:	5✔
88	p, c = _polytree_node_to_shapely(ch)	5✔
89	polygons.extend(p)	5✔
90	children.extend(c)	5✔
91
92	if node.IsHole:	5✔
93	# Check expectations: a node should be a hole, _or_ return children. This is because children of holes must
94	# be outers, and should be on the polygons list.
95	assert len(children) == 0	5✔
96	if node.Contour:	5✔
97	children = [node.Contour]	5✔
98	else:
99	children = []	×
100
101	elif node.Contour:	5✔
102	poly = _contour_to_poly(node.Contour)	5✔
103
104	# We add each inner one-by-one so that we can reject them individually if they cause the polygon to become
105	# invalid. If the shape has lots of inners, then this can mean a proportional amount of work, and may take
106	# 1,000s of seconds. Instead, we can group inners together, which reduces the number of times we call the
107	# expensive 'difference' method.
108	block_size = 200	5✔
109	if len(children) > block_size:	5✔
110	inners = _union_in_blocks(children, block_size)	5✔
111	else:
112	inners = _generate_polys(children)	5✔
113
114	for inner in inners:	5✔
115	# The difference of two valid polygons may fail, and in this situation we'd like to be able to display
116	# the polygon anyway. So we discard the bad inner and continue.
117	#
118	# See test_polygon_inners_crossing_outer for a test case.
119	try:	5✔
120	diff = poly.difference(inner)	5✔
121	except Exception:	×
122	continue	×
123
124	if not diff.is_valid:	5✔
125	diff = diff.buffer(0)	×
126
127	# Keep this for when https://trac.osgeo.org/geos/ticket/789 is resolved.
128	#
129	# assert diff.is_valid, (
130	# f"Difference of {poly.wkt} and {inner.wkt} did not make valid polygon {diff.wkt} "
131	# f" because {explain_validity(diff)}"
132	# )
133	# NOTE: this throws away the inner ring if we can't produce a valid difference. Not ideal, but we'd
134	# rather produce something that's valid than nothing.
135	if diff.is_valid:	5✔
136	poly = diff	5✔
137
138	assert poly.is_valid	5✔
139	if poly.geom_type == "MultiPolygon":	5✔
140	polygons.extend(poly.geoms)	5✔
141	else:
142	polygons.append(poly)	5✔
143	children = []	5✔
144
145	else:
146	# Check expectations: this branch gets executed if this node is not a hole, and has no contour. In that
147	# situation we'd expect that it has no children, as it would not be possible to subtract children from
148	# an empty outer contour.
149	assert len(children) == 0	5✔
150
151	return polygons, children	5✔
152
153
154	def _polytree_to_shapely(tree):	5✔
155	polygons, children = _polytree_node_to_shapely(tree)	5✔
156
157	# expect no left over children - should all be incorporated into polygons by the time recursion returns to the root.
158	assert len(children) == 0	5✔
159
160	union = unary_union(polygons)	5✔
161	assert union.is_valid	5✔
162	return union	5✔
163
164
165	def make_valid_pyclipper(shape):	5✔
166	"""
167	Use the pyclipper library to "union" a polygon on its own. This operation uses the even-odd rule to determine
168	which points are in the interior of the polygon, and can reconstruct the orientation of the polygon from that.
169	The pyclipper library is robust, and uses integer coordinates, so should not produce any additional degeneracies.
170
171	Before cleaning the polygon, we remove all degenerate inners. This is useful to remove inners which have
172	collapsed to points or lines, which can interfere with the cleaning process.
173	"""
174
175	# drop all degenerate inners
176	clean_shape = _drop_degenerate_inners(shape)	5✔
177
178	pc = pyclipper.Pyclipper()	5✔
179
180	try:	5✔
181	pc.AddPaths(_coords(clean_shape), pyclipper.PT_SUBJECT, True)	5✔
182
183	# note: Execute2 returns the polygon tree, not the list of paths
184	result = pc.Execute2(pyclipper.CT_UNION, pyclipper.PFT_EVENODD)	5✔
185
186	except pyclipper.ClipperException:	5✔
187	return MultiPolygon([])	5✔
188
189	return _polytree_to_shapely(result)	5✔
190
191
192	def make_valid_polygon(shape):	5✔
193	"""
194	Make a polygon valid. Polygons can be invalid in many ways, such as self-intersection, self-touching and
195	degeneracy. This process attempts to make a polygon valid while retaining as much of its extent or area as possible.
196
197	First, we call pyclipper to robustly union the polygon. Using this on its own appears to be good for "cleaning"
198	the polygon.
199
200	This might result in polygons which still have degeneracies according to the OCG standard of validity - as
201	pyclipper does not consider these to be invalid. Therefore, we follow by using the `buffer(0)` technique to
202	attempt to remove any remaining degeneracies.
203	"""
204	assert shape.geom_type == "Polygon"	5✔
205
206	shape = make_valid_pyclipper(shape)	5✔
207	assert shape.is_valid	5✔
208	return shape	5✔
209
210
211	def make_valid_multipolygon(shape):	5✔
212	new_g = []	5✔
213
214	for g in shape.geoms:	5✔
215	if g.is_empty:	5✔
216	continue	×
217
218	valid_g = make_valid_polygon(g)	5✔
219
220	if valid_g.geom_type == "MultiPolygon":	5✔
221	new_g.extend(valid_g.geoms)	×
222	else:
223	new_g.append(valid_g)	5✔
224
225	return MultiPolygon(new_g)	5✔
226
227
228	def make_it_valid(shape):	5✔
229	"""
230	Attempt to make any polygon or multipolygon valid.
231	"""
232	if shape.is_empty:	5✔
UNCOV 233	return shape	×
234
235	elif shape.geom_type == "MultiPolygon":	5✔
236	shape = make_valid_multipolygon(shape)	5✔
237
238	elif shape.geom_type == "Polygon":	5✔
239	shape = make_valid_polygon(shape)	5✔
240
241	return shape	5✔

tilezen / mapbox-vector-tile / 3751661366

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous