10000 Backport PR #11553: Improved Code for Segments Intersect · matplotlib/matplotlib@bd3fd8f · GitHub
[go: up one dir, main page]
Skip to content

Commit bd3fd8f

Browse files
TarasKuzyoMeeseeksDev[bot]
TarasKuzyo
authored and
MeeseeksDev[bot]
committed
Backport PR #11553: Improved Code for Segments Intersect
1 parent 4141410 commit bd3fd8f

File tree

2 files changed

+109
-2
lines changed

2 files changed

+109
-2
lines changed

‎lib/matplotlib/tests/test_path.py

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -273,6 +273,83 @@ def test_path_deepcopy():
273273
copy.deepcopy(path2)
274274

275275

276+
def test_path_intersect_path():
277+
# 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])
280+
eps_array = [1e-5, 1e-8, 1e-10, 1e-12]
281+
282+
for phi in angles:
283+
284+
transform = transforms.Affine2D().rotate(np.deg2rad(phi))
285+
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+
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+
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+
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+
306+
# self-intersect
307+
assert a.intersects_path(a)
308+
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+
314+
# a and b are collinear but do not intersect
315+
a = transform.transform_path(Path([(0, 1), (0, 5)]))
316+
b = transform.transform_path(Path([(3, 0), (3, 3)]))
317+
assert not a.intersects_path(b) and not b.intersects_path(a)
318+
319+
# a and b are on the same line but do not intersect
320+
a = transform.transform_path(Path([(0, 1), (0, 5)]))
321+
b = transform.transform_path(Path([(0, 6), (0, 7)]))
322+
assert not a.intersects_path(b) and not b.intersects_path(a)
323+
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
346+
a = transform.transform_path(Path([(0, 1), (0, 5)]))
347+
b = transform.transform_path(Path([(0, 1), (0, 2), (0, 5)]))
348+
assert a.intersects_path(b) and b.intersects_path(a)
349+
350+
return
351+
352+
276353
@pytest.mark.parametrize('offset', range(-720, 361, 45))
277354
def test_full_arc(offset):
278355
low = offset

‎src/_path.h

Lines changed: 32 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -813,6 +813,14 @@ int count_bboxes_overlapping_bbox(agg::rect_d &a, BBoxArray &bboxes)
813813
return count;
814814
}
815815

816+
817+
inline bool isclose(double a, double b, double rtol, double atol)
818+
{
819+
// as per python's math.isclose
820+
return fabs(a-b) <= fmax(rtol * fmax(fabs(a), fabs(b)), atol);
821+
}
822+
823+
816824
inline bool segments_intersect(const double &x1,
817825
const double &y1,
818826
const double &x2,
@@ -822,8 +830,27 @@ inline bool segments_intersect(const double &x1,
822830
const double &x4,
823831
const double &y4)
824832
{
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;
837+
// determinant
825838
double den = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1));
826-
if (den == 0.0) {
839+
840+
if (isclose(den, 0.0, rtol, atol)) { // collinear segments
841+
if (x1 == x2 && x2 == x3) { // segments have infinite slope (vertical lines)
842+
// and lie on the same line
843+
return (fmin(y1, y2) <= fmin(y3, y4) && fmin(y3, y4) <= fmax(y1, y2)) ||
844+
(fmin(y3, y4) <= fmin(y1, y2) && fmin(y1, y2) <= fmax(y3, y4));
845+
}
846+
else {
847+
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+
return (fmin(x1, x2) <= fmin(x3, x4) && fmin(x3, x4) <= fmax(x1, x2)) ||
850+
(fmin(x3, x4) <= fmin(x1, x2) && fmin(x1, x2) <= fmax(x3, x4));
851+
}
852+
}
853+
827854
return false;
828855
}
829856

@@ -833,7 +860,10 @@ inline bool segments_intersect(const double &x1,
833860
double u1 = n1 / den;
834861
double u2 = n2 / den;
835862

836-
return (u1 >= 0.0 && u1 <= 1.0 && u2 >= 0.0 && u2 <= 1.0);
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)));
837867
}
838868

839869
template <class PathIterator1, class PathIterator2>

0 commit comments

Comments
 (0)
0