8000 Backport PR #16250: Fix zerolen intersect by tacaswell · Pull Request #16322 · matplotlib/matplotlib · GitHub
[go: up one dir, main page]
Skip to content

Backport PR #16250: Fix zerolen intersect #16322

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Jan 26, 2020
Merged

Backport PR #16250: Fix zerolen intersect #16322

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
150 changes: 95 additions & 55 deletions lib/matplotlib/tests/test_path.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -273,81 +273,78 @@ def test_path_deepcopy():
copy.deepcopy(path2)


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

for phi in angles:
transform = transforms.Affine2D().rotate(np.deg2rad(phi))

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

# a and b intersect at angle phi
a = Path([(-2, 0), (2, 0)])
b = transform.transform_path(a)
assert a.intersects_path(b) and b.intersects_path(a)
# a and b touch at angle phi at (0, 0)
a = Path([(0, 0), (2, 0)])
b = transform.transform_path(a)
assert a.intersects_path(b) and b.intersects_path(a)

# a and b touch at angle phi at (0, 0)
a = Path([(0, 0), (2, 0)])
b = transform.transform_path(a)
assert a.intersects_path(b) and b.intersects_path(a)
# a and b are orthogonal and intersect at (0, 3)
a = transform.transform_path(Path([(0, 1), (0, 3)]))
b = transform.transform_path(Path([(1, 3), (0, 3)]))
assert a.intersects_path(b) and b.intersects_path(a)

# a and b are orthogonal and intersect at (0, 3)
a = transform.transform_path(Path([(0, 1), (0, 3)]))
b = transform.transform_path(Path([(1, 3), (0, 3)]))
assert a.intersects_path(b) and b.intersects_path(a)
# a and b are collinear and intersect at (0, 3)
a = transform.transform_path(Path([(0, 1), (0, 3)]))
b = transform.transform_path(Path([(0, 5), (0, 3)]))
assert a.intersects_path(b) and b.intersects_path(a)

# a and b are collinear and intersect at (0, 3)
a = transform.transform_path(Path([(0, 1), (0, 3)]))
b = transform.transform_path(Path([(0, 5), (0, 3)]))
assert a.intersects_path(b) and b.intersects_path(a)
# self-intersect
assert a.intersects_path(a)

# self-intersect
assert a.intersects_path(a)
# a contains b
a = transform.transform_path(Path([(0, 0), (5, 5)]))
b = transform.transform_path(Path([(1, 1), (3, 3)]))
assert a.intersects_path(b) and b.intersects_path(a)

# a contains b
a = transform.transform_path(Path([(0, 0), (5, 5)]))
b = transform.transform_path(Path([(1, 1), (3, 3)]))
assert a.intersects_path(b) and b.intersects_path(a)
# a and b are collinear but do not intersect
a = transform.transform_path(Path([(0, 1), (0, 5)]))
b = transform.transform_path(Path([(3, 0), (3, 3)]))
assert not a.intersects_path(b) and not b.intersects_path(a)

# a and b are on the same line but do not intersect
a = transform.transform_path(Path([(0, 1), (0, 5)]))
b = transform.transform_path(Path([(0, 6), (0, 7)]))
assert not a.intersects_path(b) and not b.intersects_path(a)

# Note: 1e-13 is the absolute tolerance error used for
# `isclose` function from src/_path.h

# a and b are collinear but do not intersect
# a and b are parallel but do not touch
for eps in eps_array:
a = transform.transform_path(Path([(0, 1), (0, 5)]))
b = transform.transform_path(Path([(3, 0), (3, 3)]))
b = transform.transform_path(Path([(0 + eps, 1), (0 + eps, 5)]))
assert not a.intersects_path(b) and not b.intersects_path(a)

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

# Note: 1e-13 is the absolute tolerance error used for
# `isclose` function from src/_path.h

# a and b are parallel but do not touch
for eps in eps_array:
a = transform.transform_path(Path([(0, 1), (0, 5)]))
b = transform.transform_path(Path([(0 + eps, 1), (0 + eps, 5)]))
assert not a.intersects_path(b) and not b.intersects_path(a)

# a and b are on the same line but do not intersect (really close)
for eps in eps_array:
a = transform.transform_path(Path([(0, 1), (0, 5)]))
b = transform.transform_path(Path([(0, 5 + eps), (0, 7)]))
assert not a.intersects_path(b) and not b.intersects_path(a)

# a and b are on the same line and intersect (really close)
for eps in eps_array:
a = transform.transform_path(Path([(0, 1), (0, 5)]))
b = transform.transform_path(Path([(0, 5 - eps), (0, 7)]))
assert a.intersects_path(b) and b.intersects_path(a)

# b is the same as a but with an extra point
# a and b are on the same line and intersect (really close)
for eps in eps_array:
a = transform.transform_path(Path([(0, 1), (0, 5)]))
b = transform.transform_path(Path([(0, 1), (0, 2), (0, 5)]))
b = transform.transform_path(Path([(0, 5 - eps), (0, 7)]))
assert a.intersects_path(b) and b.intersects_path(a)

return
# b is the same as a but with an extra point
a = transform.transform_path(Path([(0, 1), (0, 5)]))
b = transform.transform_path(Path([(0, 1), (0, 2), (0, 5)]))
assert a.intersects_path(b) and b.intersects_path(a)


@pytest.mark.parametrize('offset', range(-720, 361, 45))
Expand All @@ -360,3 +357,46 @@ def test_full_arc(offset):
maxs = np.max(path.vertices, axis=0)
np.testing.assert_allclose(mins, -1)
assert np.allclose(maxs, 1)


def test_disjoint_zero_length_segment():
this_path = Path(
np.array([
[824.85064295, 2056.26489203],
[861.69033931, 2041.00539016],
[868.57864109, 2057.63522175],
[831.73894473, 2072.89472361],
[824.85064295, 2056.26489203]]),
np.array([1, 2, 2, 2, 79], dtype=Path.code_type))

outline_path = Path(
np.array([
[859.91051028, 2165.38461538],
[859.06772495, 2149.30331334],
[859.06772495, 2181.46591743],
[859.91051028, 2165.38461538],
[859.91051028, 2165.38461538]]),
np.array([1, 2, 2, 2, 2],
dtype=Path.code_type))

assert not outline_path.intersects_path(this_path)
assert not this_path.intersects_path(outline_path)


def test_intersect_zero_length_segment():
this_path = Path(
np.array([
[0, 0],
[1, 1],
]))

outline_path = Path(
np.array([
[1, 0],
[.5, .5],
[.5, .5],
[0, 1],
]))

assert outline_path.intersects_path(this_path)
assert this_path.intersects_path(outline_path)
42 changes: 26 additions & 16 deletions src/_path.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -814,8 +814,13 @@ int count_bboxes_overlapping_bbox(agg::rect_d &a, BBoxArray &bboxes)
}


inline bool isclose(double a, double b, double rtol, double atol)
inline bool isclose(double a, double b)
{
// relative and absolute tolerance values are chosen empirically
// it looks the atol value matters here bacause of round-off errors
const double rtol = 1e-10;
const double atol = 1e-13;

// as per python's math.isclose
return fabs(a-b) <= fmax(rtol * fmax(fabs(a), fabs(b)), atol);
}
Expand All @@ -830,40 +835,36 @@ inline bool segments_intersect(const double &x1,
const double &x4,
const double &y4)
{
// relative and absolute tolerance values are chosen empirically
// it looks the atol value matters here bacause of round-off errors
const double rtol = 1e-10;
const double atol = 1e-13;
// determinant
double den = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1));

if (isclose(den, 0.0, rtol, atol)) { // collinear segments
if (isclose(den, 0.0)) { // collinear segments
if (x1 == x2 && x2 == x3) { // segments have infinite slope (vertical lines)
// and lie on the same line
return (fmin(y1, y2) <= fmin(y3, y4) && fmin(y3, y4) <= fmax(y1, y2)) ||
(fmin(y3, y4) <= fmin(y1, y2) && fmin(y1, y2) <= fmax(y3, y4));
}
else {
double intercept = (y1*x2 - y2*x1)*(x4 - x3) - (y3*x4 - y4*x3)*(x1 - x2);
if (isclose(intercept, 0.0, rtol, atol)) { // segments lie on the same line
if (isclose(intercept, 0.0)) { // segments lie on the same line
return (fmin(x1, x2) <= fmin(x3, x4) && fmin(x3, x4) <= fmax(x1, x2)) ||
(fmin(x3, x4) <= fmin(x1, x2) && fmin(x1, x2) <= fmax(x3, x4));
}
}

return false;
}

double n1 = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3));
double n2 = ((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3));
const double n1 = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3));
const double n2 = ((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3));

double u1 = n1 / den;
double u2 = n2 / den;
const double u1 = n1 / den;
const double u2 = n2 / den;

return ((u1 > 0.0 || isclose(u1, 0.0, rtol, atol)) &&
(u1 < 1.0 || isclose(u1, 1.0, rtol, atol)) &&
(u2 > 0.0 || isclose(u2, 0.0, rtol, atol)) &&
(u2 < 1.0 || isclose(u2, 1.0, rtol, atol)));
return ((u1 > 0.0 || isclose(u1, 0.0)) &&
(u1 < 1.0 || isclose(u1, 1.0)) &&
(u2 > 0.0 || isclose(u2, 0.0)) &&
(u2 < 1.0 || isclose(u2, 1.0)));
}

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

c1.vertex(&x11, &y11);
while (c1.vertex(&x12, &y12) != agg::path_cmd_stop) {
// if the segment in path 1 is (almost) 0 length, skip to next vertex
if ((isclose((x11 - x12) * (x11 - x12) + (y11 - y12) * (y11 - y12), 0))){
continue;
}
c2.rewind(0);
c2.vertex(&x21, &y21);

while (c2.vertex(&x22, &y22) != agg::path_cmd_stop) {
// if the segment in path 2 is (almost) 0 length, skip to next vertex
if ((isclose((x21 - x22) * (x21 - x22) + (y21 - y22) * (y21 - y22), 0))){
continue;
}
if (segments_intersect(x11, y11, x12, y12, x21, y21, x22, y22)) {
return true;
}
Expand Down
0