8000 Backport PR #16250: Fix zerolen intersect · matplotlib/matplotlib@ff04b25 · GitHub
[go: up one dir, main page]
Skip to content

Commit ff04b25

Browse files
jklymaktacaswell
jklymak
authored and
tacaswell
committed
Backport PR #16250: Fix zerolen intersect
Merge pull request #16250 from tacaswell/fix_zerolen_intersect Fix zerolen intersect Also re-factors some tests. Conflicts: lib/matplotlib/tests/test_path.py - unrelated change to test above new test. Kept old version of test and added new test
1 parent d10aacf commit ff04b25

File tree

2 files changed

+121
-71
lines changed

2 files changed

+121
-71
lines changed

‎lib/matplotlib/tests/test_path.py‎

Lines 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‎

Lines 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