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

Fix zerolen intersect #16250

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 7 commits into from
Jan 23, 2020
Merged

Fix zerolen intersect #16250

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
7 commits
Select commit Hold shift + click to select a range
a06d8e9
TST: a 0 length segment does not intersect with all other segments
tacaswell Jan 18, 2020
f8181c9
FIX: when iterating through segments skip 0 length segments
tacaswell Jan 18, 2020
b3476a8
FIX: 0 length segment intersect
tacaswell Jan 18, 2020
9729ac2
MNT: make local variable const
tacaswell Jan 18, 2020
d5ae201
MNT: alternate method of identifying 0 length segments
tacaswell Jan 18, 2020
41fce6b
TST: use pytest.mark.parametrize instead of a for loop
tacaswell Jan 19, 2020
ffaf302
API/MNT: re-arrange 0 length segment detection
tacaswell Jan 21, 2020
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 150 lib/matplotlib/tests/test_path.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -265,81 +265,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 @@ -352,3 +349,46 @@ def test_full_arc(offset):
maxs = np.max(path.vertices, axis=0)
np.testing.assert_allclose(mins, -1)
np.testing.assert_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 42 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;
Copy link
Contributor

@anntzer anntzer Jan 20, 2020 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

if you're really going to do the check to zero-len both here and in segments_intersect (which seems weird as well, I'd rather not(?)) at least the check should be the same in both places (len < epsilon)?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

My logic was this:

  • computing == is cheaper
  • if trip the == condition, we will trigger the determinant condition, but the converse is not true.
  • do the cheaper, stricter thing here
  • do the more expensive looser thing where we have to (see my discussion with @timhoffm above)
  • keep all of the "isclose" logic together in the code so we are sure that the numbers don't get out of sync

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Well you could change the signature of isclose() to just isclose(a, b) and force atol and rtol as constants in the body of the function... I'm not going to block over that though.

}
if (segments_intersect(x11, y11, x12, y12, x21, y21, x22, y22)) {
return true;
}
Expand Down
Morty Proxy This is a proxified and sanitized view of the page, visit original site.