Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 0447ad4

Browse filesBrowse files
timhoffmtimhoffm
authored
Merge pull request #16322 from tacaswell/auto-backport-of-pr-16250-on-v3.1.x
Backport PR #16250: Fix zerolen intersect
2 parents d48ab05 + ff04b25 commit 0447ad4
Copy full SHA for 0447ad4

File tree

Expand file treeCollapse file tree

2 files changed

+121
-71
lines changed
Filter options
Expand file treeCollapse file tree

2 files changed

+121
-71
lines changed

‎lib/matplotlib/tests/test_path.py

Copy file name to clipboardExpand all lines: lib/matplotlib/tests/test_path.py
+95-55Lines changed: 95 additions & 55 deletions
Original file line numberDiff line numberDiff line change
@@ -273,81 +273,78 @@ def test_path_deepcopy():
273273
copy.deepcopy(path2)
274274

275275

276-
def test_path_intersect_path():
276+
@pytest.mark.parametrize('phi', np.concatenate([
277+
np.array([0, 15, 30, 45, 60, 75, 90, 105, 120, 135]) + delta
278+
for delta in [-1, 0, 1]]))
279+
def test_path_intersect_path(phi):
277280
# test for the range of intersection angles
278-
base_angles = np.array([0, 15, 30, 45, 60, 75, 90, 105, 120, 135])
279-
angles = np.concatenate([base_angles, base_angles + 1, base_angles - 1])
280281
eps_array = [1e-5, 1e-8, 1e-10, 1e-12]
281282

282-
for phi in angles:
283+
transform = transforms.Affine2D().rotate(np.deg2rad(phi))
283284

284-
transform = transforms.Affine2D().rotate(np.deg2rad(phi))
285+
# a and b intersect at angle phi
286+
a = Path([(-2, 0), (2, 0)])
287+
b = transform.transform_path(a)
288+
assert a.intersects_path(b) and b.intersects_path(a)
285289

286-
# a and b intersect at angle phi
287-
a = Path([(-2, 0), (2, 0)])
288-
b = transform.transform_path(a)
289-
assert a.intersects_path(b) and b.intersects_path(a)
290+
# a and b touch at angle phi at (0, 0)
291+
a = Path([(0, 0), (2, 0)])
292+
b = transform.transform_path(a)
293+
assert a.intersects_path(b) and b.intersects_path(a)
290294

291-
# a and b touch at angle phi at (0, 0)
292-
a = Path([(0, 0), (2, 0)])
293-
b = transform.transform_path(a)
294-
assert a.intersects_path(b) and b.intersects_path(a)
295+
# a and b are orthogonal and intersect at (0, 3)
296+
a = transform.transform_path(Path([(0, 1), (0, 3)]))
297+
b = transform.transform_path(Path([(1, 3), (0, 3)]))
298+
assert a.intersects_path(b) and b.intersects_path(a)
295299

296-
# a and b are orthogonal and intersect at (0, 3)
297-
a = transform.transform_path(Path([(0, 1), (0, 3)]))
298-
b = transform.transform_path(Path([(1, 3), (0, 3)]))
299-
assert a.intersects_path(b) and b.intersects_path(a)
300+
# a and b are collinear and intersect at (0, 3)
301+
a = transform.transform_path(Path([(0, 1), (0, 3)]))
302+
b = transform.transform_path(Path([(0, 5), (0, 3)]))
303+
assert a.intersects_path(b) and b.intersects_path(a)
300304

301-
# a and b are collinear and intersect at (0, 3)
302-
a = transform.transform_path(Path([(0, 1), (0, 3)]))
303-
b = transform.transform_path(Path([(0, 5), (0, 3)]))
304-
assert a.intersects_path(b) and b.intersects_path(a)
305+
# self-intersect
306+
assert a.intersects_path(a)
305307

306-
# self-intersect
307-
assert a.intersects_path(a)
308+
# a contains b
309+
a = transform.transform_path(Path([(0, 0), (5, 5)]))
310+
b = transform.transform_path(Path([(1, 1), (3, 3)]))
311+
assert a.intersects_path(b) and b.intersects_path(a)
308312

309-
# a contains b
310-
a = transform.transform_path(Path([(0, 0), (5, 5)]))
311-
b = transform.transform_path(Path([(1, 1), (3, 3)]))
312-
assert a.intersects_path(b) and b.intersects_path(a)
313+
# a and b are collinear but do not intersect
314+
a = transform.transform_path(Path([(0, 1), (0, 5)]))
315+
b = transform.transform_path(Path([(3, 0), (3, 3)]))
316+
assert not a.intersects_path(b) and not b.intersects_path(a)
317+
318+
# a and b are on the same line but do not intersect
319+
a = transform.transform_path(Path([(0, 1), (0, 5)]))
320+
b = transform.transform_path(Path([(0, 6), (0, 7)]))
321+
assert not a.intersects_path(b) and not b.intersects_path(a)
322+
323+
# Note: 1e-13 is the absolute tolerance error used for
324+
# `isclose` function from src/_path.h
313325

314-
# a and b are collinear but do not intersect
326+
# a and b are parallel but do not touch
327+
for eps in eps_array:
315328
a = transform.transform_path(Path([(0, 1), (0, 5)]))
316-
b = transform.transform_path(Path([(3, 0), (3, 3)]))
329+
b = transform.transform_path(Path([(0 + eps, 1), (0 + eps, 5)]))
317330
assert not a.intersects_path(b) and not b.intersects_path(a)
318331

319-
# a and b are on the same line but do not intersect
332+
# a and b are on the same line but do not intersect (really close)
333+
for eps in eps_array:
320334
a = transform.transform_path(Path([(0, 1), (0, 5)]))
321-
b = transform.transform_path(Path([(0, 6), (0, 7)]))
335+
b = transform.transform_path(Path([(0, 5 + eps), (0, 7)]))
322336
assert not a.intersects_path(b) and not b.intersects_path(a)
323337

324-
# Note: 1e-13 is the absolute tolerance error used for
325-
# `isclose` function from src/_path.h
326-
327-
# a and b are parallel but do not touch
328-
for eps in eps_array:
329-
a = transform.transform_path(Path([(0, 1), (0, 5)]))
330-
b = transform.transform_path(Path([(0 + eps, 1), (0 + eps, 5)]))
331-
assert not a.intersects_path(b) and not b.intersects_path(a)
332-
333-
# a and b are on the same line but do not intersect (really close)
334-
for eps in eps_array:
335-
a = transform.transform_path(Path([(0, 1), (0, 5)]))
336-
b = transform.transform_path(Path([(0, 5 + eps), (0, 7)]))
337-
assert not a.intersects_path(b) and not b.intersects_path(a)
338-
339-
# a and b are on the same line and intersect (really close)
340-
for eps in eps_array:
341-
a = transform.transform_path(Path([(0, 1), (0, 5)]))
342-
b = transform.transform_path(Path([(0, 5 - eps), (0, 7)]))
343-
assert a.intersects_path(b) and b.intersects_path(a)
344-
345-
# b is the same as a but with an extra point
338+
# a and b are on the same line and intersect (really close)
339+
for eps in eps_array:
346340
a = transform.transform_path(Path([(0, 1), (0, 5)]))
347-
b = transform.transform_path(Path([(0, 1), (0, 2), (0, 5)]))
341+
b = transform.transform_path(Path([(0, 5 - eps), (0, 7)]))
348342
assert a.intersects_path(b) and b.intersects_path(a)
349343

350-
return
344+
# b is the same as a but with an extra point
345+
a = transform.transform_path(Path([(0, 1), (0, 5)]))
346+
b = transform.transform_path(Path([(0, 1), (0, 2), (0, 5)]))
347+
assert a.intersects_path(b) and b.intersects_path(a)
351348

352349

353350
@pytest.mark.parametrize('offset', range(-720, 361, 45))
@@ -360,3 +357,46 @@ def test_full_arc(offset):
360357
maxs = np.max(path.vertices, axis=0)
361358
np.testing.assert_allclose(mins, -1)
362359
assert np.allclose(maxs, 1)
360+
361+
362+
def test_disjoint_zero_length_segment():
363+
this_path = Path(
364+
np.array([
365+
[824.85064295, 2056.26489203],
366+
[861.69033931, 2041.00539016],
367+
[868.57864109, 2057.63522175],
368+
[831.73894473, 2072.89472361],
369+
[824.85064295, 2056.26489203]]),
370+
np.array([1, 2, 2, 2, 79], dtype=Path.code_type))
371+
372+
outline_path = Path(
373+
np.array([
374+
[859.91051028, 2165.38461538],
375+
[859.06772495, 2149.30331334],
376+
[859.06772495, 2181.46591743],
377+
[859.91051028, 2165.38461538],
378+
[859.91051028, 2165.38461538]]),
379+
np.array([1, 2, 2, 2, 2],
380+
dtype=Path.code_type))
381+
382+
assert not outline_path.intersects_path(this_path)
383+
assert not this_path.intersects_path(outline_path)
384+
385+
386+
def test_intersect_zero_length_segment():
387+
this_path = Path(
388+
np.array([
389+
[0, 0],
390+
[1, 1],
391+
]))
392+
393+
outline_path = Path(
394+
np.array([
395+
[1, 0],
396+
[.5, .5],
397+
[.5, .5],
398+
[0, 1],
399+
]))
400+
401+
assert outline_path.intersects_path(this_path)
402+
assert this_path.intersects_path(outline_path)

‎src/_path.h

Copy file name to clipboardExpand all lines: src/_path.h
+26-16Lines changed: 26 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -814,8 +814,13 @@ int count_bboxes_overlapping_bbox(agg::rect_d &a, BBoxArray &bboxes)
814814
}
815815

816816

817-
inline bool isclose(double a, double b, double rtol, double atol)
817+
inline bool isclose(double a, double b)
818818
{
819+
// relative and absolute tolerance values are chosen empirically
820+
// it looks the atol value matters here bacause of round-off errors
821+
const double rtol = 1e-10;
822+
const double atol = 1e-13;
823+
819824
// as per python's math.isclose
820825
return fabs(a-b) <= fmax(rtol * fmax(fabs(a), fabs(b)), atol);
821826
}
@@ -830,40 +835,36 @@ inline bool segments_intersect(const double &x1,
830835
const double &x4,
831836
const double &y4)
832837
{
833-
// relative and absolute tolerance values are chosen empirically
834-
// it looks the atol value matters here bacause of round-off errors
835-
const double rtol = 1e-10;
836-
const double atol = 1e-13;
837838
// determinant
838839
double den = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1));
839840

840-
if (isclose(den, 0.0, rtol, atol)) { // collinear segments
841+
if (isclose(den, 0.0)) { // collinear segments
841842
if (x1 == x2 && x2 == x3) { // segments have infinite slope (vertical lines)
842843
// and lie on the same line
843844
return (fmin(y1, y2) <= fmin(y3, y4) && fmin(y3, y4) <= fmax(y1, y2)) ||
844845
(fmin(y3, y4) <= fmin(y1, y2) && fmin(y1, y2) <= fmax(y3, y4));
845846
}
846847
else {
847848
double intercept = (y1*x2 - y2*x1)*(x4 - x3) - (y3*x4 - y4*x3)*(x1 - x2);
848-
if (isclose(intercept, 0.0, rtol, atol)) { // segments lie on the same line
849+
if (isclose(intercept, 0.0)) { // segments lie on the same line
849850
return (fmin(x1, x2) <= fmin(x3, x4) && fmin(x3, x4) <= fmax(x1, x2)) ||
850851
(fmin(x3, x4) <= fmin(x1, x2) && fmin(x1, x2) <= fmax(x3, x4));
851852
}
852853
}
853-
854+
854855
return false;
855856
}
856857

857-
double n1 = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3));
858-
double n2 = ((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3));
858+
const double n1 = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3));
859+
const double n2 = ((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3));
859860

860-
double u1 = n1 / den;
861-
double u2 = n2 / den;
861+
const double u1 = n1 / den;
862+
const double u2 = n2 / den;
862863

863-
return ((u1 > 0.0 || isclose(u1, 0.0, rtol, atol)) &&
864-
(u1 < 1.0 || isclose(u1, 1.0, rtol, atol)) &&
865-
(u2 > 0.0 || isclose(u2, 0.0, rtol, atol)) &&
866-
(u2 < 1.0 || isclose(u2, 1.0, rtol, atol)));
864+
return ((u1 > 0.0 || isclose(u1, 0.0)) &&
865+
(u1 < 1.0 || isclose(u1, 1.0)) &&
866+
(u2 > 0.0 || isclose(u2, 0.0)) &&
867+
(u2 < 1.0 || isclose(u2, 1.0)));
867868
}
868869

869870
template <class PathIterator1, class PathIterator2>
@@ -887,9 +888,18 @@ bool path_intersects_path(PathIterator1 &p1, PathIterator2 &p2)
887888

888889
c1.vertex(&x11, &y11);
889890
while (c1.vertex(&x12, &y12) != agg::path_cmd_stop) {
891+
// if the segment in path 1 is (almost) 0 length, skip to next vertex
892+
if ((isclose((x11 - x12) * (x11 - x12) + (y11 - y12) * (y11 - y12), 0))){
893+
continue;
894+
}
890895
c2.rewind(0);
891896
c2.vertex(&x21, &y21);
897+
892898
while (c2.vertex(&x22, &y22) != agg::path_cmd_stop) {
899+
// if the segment in path 2 is (almost) 0 length, skip to next vertex
900+
if ((isclose((x21 - x22) * (x21 - x22) + (y21 - y22) * (y21 - y22), 0))){
901+
continue;
902+
}
893903
if (segments_intersect(x11, y11, x12, y12, x21, y21, x22, y22)) {
894904
return true;
895905
}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.