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 7e1a47c

Browse filesBrowse files
jklymakjklymak
authored
Merge pull request #16250 from tacaswell/fix_zerolen_intersect
Fix zerolen intersect
2 parents cd580da + ffaf302 commit 7e1a47c
Copy full SHA for 7e1a47c

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
@@ -265,81 +265,78 @@ def test_path_deepcopy():
265265
copy.deepcopy(path2)
266266

267267

268-
def test_path_intersect_path():
268+
@pytest.mark.parametrize('phi', np.concatenate([
269+
np.array([0, 15, 30, 45, 60, 75, 90, 105, 120, 135]) + delta
270+
for delta in [-1, 0, 1]]))
271+
def test_path_intersect_path(phi):
269272
# test for the range of intersection angles
270-
base_angles = np.array([0, 15, 30, 45, 60, 75, 90, 105, 120, 135])
271-
angles = np.concatenate([base_angles, base_angles + 1, base_angles - 1])
272273
eps_array = [1e-5, 1e-8, 1e-10, 1e-12]
273274

274-
for phi in angles:
275+
transform = transforms.Affine2D().rotate(np.deg2rad(phi))
275276

276-
transform = transforms.Affine2D().rotate(np.deg2rad(phi))
277+
# a and b intersect at angle phi
278+
a = Path([(-2, 0), (2, 0)])
279+
b = transform.transform_path(a)
280+
assert a.intersects_path(b) and b.intersects_path(a)
277281

278-
# a and b intersect at angle phi
279-
a = Path([(-2, 0), (2, 0)])
280-
b = transform.transform_path(a)
281-
assert a.intersects_path(b) and b.intersects_path(a)
282+
# a and b touch at angle phi at (0, 0)
283+
a = Path([(0, 0), (2, 0)])
284+
b = transform.transform_path(a)
285+
assert a.intersects_path(b) and b.intersects_path(a)
282286

283-
# a and b touch at angle phi at (0, 0)
284-
a = Path([(0, 0), (2, 0)])
285-
b = transform.transform_path(a)
286-
assert a.intersects_path(b) and b.intersects_path(a)
287+
# a and b are orthogonal and intersect at (0, 3)
288+
a = transform.transform_path(Path([(0, 1), (0, 3)]))
289+
b = transform.transform_path(Path([(1, 3), (0, 3)]))
290+
assert a.intersects_path(b) and b.intersects_path(a)
287291

288-
# a and b are orthogonal and intersect at (0, 3)
289-
a = transform.transform_path(Path([(0, 1), (0, 3)]))
290-
b = transform.transform_path(Path([(1, 3), (0, 3)]))
291-
assert a.intersects_path(b) and b.intersects_path(a)
292+
# a and b are collinear and intersect at (0, 3)
293+
a = transform.transform_path(Path([(0, 1), (0, 3)]))
294+
b = transform.transform_path(Path([(0, 5), (0, 3)]))
295+
assert a.intersects_path(b) and b.intersects_path(a)
292296

293-
# a and b are collinear and intersect at (0, 3)
294-
a = transform.transform_path(Path([(0, 1), (0, 3)]))
295-
b = transform.transform_path(Path([(0, 5), (0, 3)]))
296-
assert a.intersects_path(b) and b.intersects_path(a)
297+
# self-intersect
298+
assert a.intersects_path(a)
297299

298-
# self-intersect
299-
assert a.intersects_path(a)
300+
# a contains b
301+
a = transform.transform_path(Path([(0, 0), (5, 5)]))
302+
b = transform.transform_path(Path([(1, 1), (3, 3)]))
303+
assert a.intersects_path(b) and b.intersects_path(a)
300304

301-
# a contains b
302-
a = transform.transform_path(Path([(0, 0), (5, 5)]))
303-
b = transform.transform_path(Path([(1, 1), (3, 3)]))
304-
assert a.intersects_path(b) and b.intersects_path(a)
305+
# a and b are collinear but do not intersect
306+
a = transform.transform_path(Path([(0, 1), (0, 5)]))
307+
b = transform.transform_path(Path([(3, 0), (3, 3)]))
308+
assert not a.intersects_path(b) and not b.intersects_path(a)
309+
310+
# a and b are on the same line but do not intersect
311+
a = transform.transform_path(Path([(0, 1), (0, 5)]))
312+
b = transform.transform_path(Path([(0, 6), (0, 7)]))
313+
assert not a.intersects_path(b) and not b.intersects_path(a)
314+
315+
# Note: 1e-13 is the absolute tolerance error used for
316+
# `isclose` function from src/_path.h
305317

306-
# a and b are collinear but do not intersect
318+
# a and b are parallel but do not touch
319+
for eps in eps_array:
307320
a = transform.transform_path(Path([(0, 1), (0, 5)]))
308-
b = transform.transform_path(Path([(3, 0), (3, 3)]))
321+
b = transform.transform_path(Path([(0 + eps, 1), (0 + eps, 5)]))
309322
assert not a.intersects_path(b) and not b.intersects_path(a)
310323

311-
# a and b are on the same line but do not intersect
324+
# a and b are on the same line but do not intersect (really close)
325+
for eps in eps_array:
312326
a = transform.transform_path(Path([(0, 1), (0, 5)]))
313-
b = transform.transform_path(Path([(0, 6), (0, 7)]))
327+
b = transform.transform_path(Path([(0, 5 + eps), (0, 7)]))
314328
assert not a.intersects_path(b) and not b.intersects_path(a)
315329

316-
# Note: 1e-13 is the absolute tolerance error used for
317-
# `isclose` function from src/_path.h
318-
319-
# a and b are parallel but do not touch
320-
for eps in eps_array:
321-
a = transform.transform_path(Path([(0, 1), (0, 5)]))
322-
b = transform.transform_path(Path([(0 + eps, 1), (0 + eps, 5)]))
323-
assert not a.intersects_path(b) and not b.intersects_path(a)
324-
325-
# a and b are on the same line but do not intersect (really close)
326-
for eps in eps_array:
327-
a = transform.transform_path(Path([(0, 1), (0, 5)]))
328-
b = transform.transform_path(Path([(0, 5 + eps), (0, 7)]))
329-
assert not a.intersects_path(b) and not b.intersects_path(a)
330-
331-
# a and b are on the same line and intersect (really close)
332-
for eps in eps_array:
333-
a = transform.transform_path(Path([(0, 1), (0, 5)]))
334-
b = transform.transform_path(Path([(0, 5 - eps), (0, 7)]))
335-
assert a.intersects_path(b) and b.intersects_path(a)
336-
337-
# b is the same as a but with an extra point
330+
# a and b are on the same line and intersect (really close)
331+
for eps in eps_array:
338332
a = transform.transform_path(Path([(0, 1), (0, 5)]))
339-
b = transform.transform_path(Path([(0, 1), (0, 2), (0, 5)]))
333+
b = transform.transform_path(Path([(0, 5 - eps), (0, 7)]))
340334
assert a.intersects_path(b) and b.intersects_path(a)
341335

342-
return
336+
# b is the same as a but with an extra point
337+
a = transform.transform_path(Path([(0, 1), (0, 5)]))
338+
b = transform.transform_path(Path([(0, 1), (0, 2), (0, 5)]))
339+
assert a.intersects_path(b) and b.intersects_path(a)
343340

344341

345342
@pytest.mark.parametrize('offset', range(-720, 361, 45))
@@ -352,3 +349,46 @@ def test_full_arc(offset):
352349
maxs = np.max(path.vertices, axis=0)
353350
np.testing.assert_allclose(mins, -1)
354351
np.testing.assert_allclose(maxs, 1)
352+
353+
354+
def test_disjoint_zero_length_segment():
355+
this_path = Path(
356+
np.array([
357+
[824.85064295, 2056.26489203],
358+
[861.69033931, 2041.00539016],
359+
[868.57864109, 2057.63522175],
360+
[831.73894473, 2072.89472361],
361+
[824.85064295, 2056.26489203]]),
362+
np.array([1, 2, 2, 2, 79], dtype=Path.code_type))
363+
364+
outline_path = Path(
365+
np.array([
366+
[859.91051028, 2165.38461538],
367+
[859.06772495, 2149.30331334],
368+
[859.06772495, 2181.46591743],
369+
[859.91051028, 2165.38461538],
370+
[859.91051028, 2165.38461538]]),
371+
np.array([1, 2, 2, 2, 2],
372+
dtype=Path.code_type))
373+
374+
assert not outline_path.intersects_path(this_path)
375+
assert not this_path.intersects_path(outline_path)
376+
377+
378+
def test_intersect_zero_length_segment():
379+
this_path = Path(
380+
np.array([
381+
[0, 0],
382+
[1, 1],
383+
]))
384+
385+
outline_path = Path(
386+
np.array([
387+
[1, 0],
388+
[.5, .5],
389+
[.5, .5],
390+
[0, 1],
391+
]))
392+
393+
assert outline_path.intersects_path(this_path)
394+
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.