3746140319

Build Type

push

github

Committed by GitHub

Commit Message

Pre-commit tools (#121)

Run Details

74 of 96 new or added lines in 6 files covered. (77.08%)

2 existing lines in 1 file now uncovered.

558 of 727 relevant lines covered (76.75%)

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

tilezen / mapbox-vector-tile / 3746140319

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