Skip to content

Commit 7c2a998

Browse files
havatvnyalldawson
havatv
authored and
nyalldawson
committedAug 9, 2018
[processing] Added isclose function to VoronoyPolygons.py to avoid numerical instability
Fixes #8002 - hopefully, and adds tests (cherry-picked from d2b71c3)
·
final-3_2_3final-3_2_2
1 parent 450f9f3 commit 7c2a998

File tree

4 files changed

+1570
-1
lines changed

4 files changed

+1570
-1
lines changed
 

‎python/plugins/processing/algs/qgis/VoronoiPolygons.py

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -197,6 +197,9 @@ def clip_voronoi(self, edges, c, width, height, extent, point, xyminmax):
197197
pt_y = point.y() - extent.yMinimum()
198198
(xmin, ymin, xmax, ymax) = xyminmax
199199

200+
def isclose(a, b, rel_tol=1e-9, abs_tol=0.0):
201+
return abs(a - b) <= max(rel_tol * max(abs(a), abs(b)), abs_tol)
202+
200203
def clip_line(x1, y1, x2, y2, w, h):
201204
if x1 < 0 and x2 < 0:
202205
# Completely to the left
@@ -210,6 +213,7 @@ def clip_line(x1, y1, x2, y2, w, h):
210213
if y1 > h and y2 > h:
211214
# Completely above
212215
return [0, 0, 0, 0]
216+
# Clip on the left envelope boundary
213217
if x1 < 0:
214218
# First point to the left
215219
y1 = (y1 * x2 - y2 * x1) / (x2 - x1)
@@ -218,6 +222,7 @@ def clip_line(x1, y1, x2, y2, w, h):
218222
# Last point to the left
219223
y2 = (y1 * x2 - y2 * x1) / (x2 - x1)
220224
x2 = 0
225+
# Clip on the right envelope boundary
221226
if x1 > w:
222227
# First point to the right
223228
y1 = y1 + (w - x1) * (y2 - y1) / (x2 - x1)
@@ -226,8 +231,9 @@ def clip_line(x1, y1, x2, y2, w, h):
226231
# Last point to the right
227232
y2 = y1 + (w - x1) * (y2 - y1) / (x2 - x1)
228233
x2 = w
229-
if x1 == x2 and y1 == y2:
234+
if isclose(x1, x2) and isclose(y1, y2):
230235
return [0, 0, 0, 0]
236+
# Clip on the bottom envelope boundary
231237
if y1 < 0:
232238
# First point below
233239
x1 = (x1 * y2 - x2 * y1) / (y2 - y1)
@@ -236,6 +242,7 @@ def clip_line(x1, y1, x2, y2, w, h):
236242
# Second point below
237243
x2 = (x1 * y2 - x2 * y1) / (y2 - y1)
238244
y2 = 0
245+
# Clip on the top envelope boundary
239246
if y1 > h:
240247
# First point above
241248
x1 = x1 + (h - y1) * (x2 - x1) / (y2 - y1)
@@ -244,6 +251,8 @@ def clip_line(x1, y1, x2, y2, w, h):
244251
# Second point above
245252
x2 = x1 + (h - y1) * (x2 - x1) / (y2 - y1)
246253
y2 = h
254+
if isclose(x1, x2) and isclose(y1, y2):
255+
return [0, 0, 0, 0]
247256
return [x1, y1, x2, y2]
248257

249258
bndpoints = []

‎python/plugins/processing/tests/testdata/airports.gml

Lines changed: 774 additions & 0 deletions
Large diffs are not rendered by default.

‎python/plugins/processing/tests/testdata/expected/airportsvoronoidiagram.gml

Lines changed: 774 additions & 0 deletions
Large diffs are not rendered by default.

‎python/plugins/processing/tests/testdata/qgis_algorithm_tests.yaml

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3570,6 +3570,18 @@ tests:
35703570
name: expected/pointsvoronoi1diagram.gml
35713571
type: vector
35723572

3573+
- algorithm: qgis:voronoipolygons
3574+
name: Vornoi with configuration that may cause numerical issues
3575+
params:
3576+
BUFFER: 0.0
3577+
INPUT:
3578+
name: airports.gml
3579+
type: vector
3580+
results:
3581+
OUTPUT:
3582+
name: expected/airportsvoronoidiagram.gml
3583+
type: vector
3584+
35733585
- algorithm: native:explodelines
35743586
name: Explode lines
35753587
params:

0 commit comments

Comments
 (0)
Please sign in to comment.