8000 Merge pull request #16305 from meeseeksmachine/auto-backport-of-pr-16… · matplotlib/matplotlib@039fcfe · GitHub
[go: up one dir, main page]
Skip to content

Commit 039fcfe

Browse files
timhoffmtimhoffm
authored
Merge pull request #16305 from meeseeksmachine/auto-backport-of-pr-16250-on-v3.2.x
Backport PR #16250 on branch v3.2.x (Fix zerolen intersect)
2 parents 7d958c6 + 9ab0b76 commit 039fcfe

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

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