Skip to content

bugfix for PathSimplifier #28478

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 6 commits into from
Oct 22, 2024
Merged

bugfix for PathSimplifier #28478

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
b2802d1
bugfix for path simplifier
r3kste Jun 9, 2024
a4f36fd
simplified test
r3kste Jun 25, 2024
2491647
simplified test further
r3kste Jun 26, 2024
daf1090
enhanced tests
r3kste Jul 21, 2024
70d0a07
moved test and refactored code
r3kste Jul 23, 2024
5c6dde0
added test for edge case
r3kste Jul 23, 2024
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
51 changes: 51 additions & 0 deletions lib/matplotlib/tests/test_simplification.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -518,3 +518,54 @@ def test_clipping_full():
simplified = list(p.iter_segments(clip=[0, 0, 100, 100]))
assert ([(list(x), y) for x, y in simplified] ==
[([50, 40], 1)])


def test_simplify_closepoly():
# The values of the vertices in a CLOSEPOLY should always be ignored,
# in favor of the most recent MOVETO's vertex values
paths = [Path([(1, 1), (2, 1), (2, 2), (np.nan, np.nan)],
[Path.MOVETO, Path.LINETO, Path.LINETO, Path.CLOSEPOLY]),
Path([(1, 1), (2, 1), (2, 2), (40, 50)],
[Path.MOVETO, Path.LINETO, Path.LINETO, Path.CLOSEPOLY])]
expected_path = Path([(1, 1), (2, 1), (2, 2), (1, 1), (1, 1), (0, 0)],
[Path.MOVETO, Path.LINETO, Path.LINETO, Path.LINETO,
Path.LINETO, Path.STOP])

for path in paths:
simplified_path = path.cleaned(simplify=True)
assert_array_equal(expected_path.vertices, simplified_path.vertices)
assert_array_equal(expected_path.codes, simplified_path.codes)

# test that a compound path also works
path = Path([(1, 1), (2, 1), (2, 2), (np.nan, np.nan),
(-1, 0), (-2, 0), (-2, 1), (np.nan, np.nan)],
[Path.MOVETO, Path.LINETO, Path.LINETO, Path.CLOSEPOLY,
Path.MOVETO, Path.LINETO, Path.LINETO, Path.CLOSEPOLY])
expected_path = Path([(1, 1), (2, 1), (2, 2), (1, 1),
(-1, 0), (-2, 0), (-2, 1), (-1, 0), (-1, 0), (0, 0)],
[Path.MOVETO, Path.LINETO, Path.LINETO, Path.LINETO,
Path.MOVETO, Path.LINETO, Path.LINETO, Path.LINETO,
Path.LINETO, Path.STOP])

simplified_path = path.cleaned(simplify=True)
assert_array_equal(expected_path.vertices, simplified_path.vertices)
assert_array_equal(expected_path.codes, simplified_path.codes)

# test for a path with an invalid MOVETO
# CLOSEPOLY with an invalid MOVETO should be ignored
path = Path([(1, 0), (1, -1), (2, -1),
(np.nan, np.nan), (-1, -1), (-2, 1), (-1, 1),
(2, 2), (0, -1)],
[Path.MOVETO, Path.LINETO, Path.LINETO,
Path.MOVETO, Path.LINETO, Path.LINETO, Path.LINETO,
Path.CLOSEPOLY, Path.LINETO])
expected_path = Path([(1, 0), (1, -1), (2, -1),
(np.nan, np.nan), (-1, -1), (-2, 1), (-1, 1),
(0, -1), (0, -1), (0, 0)],
[Path.MOVETO, Path.LINETO, Path.LINETO,
Path.MOVETO, Path.LINETO, Path.LINETO, Path.LINETO,
Path.LINETO, Path.LINETO, Path.STOP])

simplified_path = path.cleaned(simplify=True)
assert_array_equal(expected_path.vertices, simplified_path.vertices)
assert_array_equal(expected_path.codes, simplified_path.codes)
31 changes: 31 additions & 0 deletions src/path_converters.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -644,6 +644,13 @@ class PathSimplifier : protected EmbeddedQueue<9>
m_after_moveto(false),
m_clipped(false),

// whether the most recent MOVETO vertex is valid
m_has_init(false),

// the most recent MOVETO vertex
m_initX(0.0),
m_initY(0.0),

// the x, y values from last iteration
m_lastx(0.0),
m_lasty(0.0),
Expand Down Expand Up @@ -754,6 +761,15 @@ class PathSimplifier : protected EmbeddedQueue<9>
_push(x, y);
}
m_after_moveto = true;

if (std::isfinite(*x) && std::isfinite(*y)) {
m_has_init = true;
m_initX = *x;
m_initY = *y;
} else {
m_has_init = false;
}

m_lastx = *x;
m_lasty = *y;
m_moveto = false;
Expand All @@ -768,6 +784,19 @@ class PathSimplifier : protected EmbeddedQueue<9>
}
m_after_moveto = false;

if(agg::is_close(cmd)) {
if (m_has_init) {
/* If we have a valid initial vertex, then
replace the current vertex with the initial vertex */
*x = m_initX;
*y = m_initY;
} else {
/* If we don't have a valid initial vertex, then
we can't close the path, so we skip the vertex */
continue;
Comment on lines +794 to +796
Copy link
Contributor

Choose a reason for hiding this comment

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

Could you add a test for this case as well?

What is the expected result if the second MOVETO of a compound path is (nan, nan)? Here it looks like we are still adding the inbetween LINETOs and just not starting/closing the path. Does it therefore merge into the first path in this case?

Copy link
Contributor Author

@r3kste r3kste Jul 23, 2024 •
edited
Loading

Choose a reason for hiding this comment

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

For a compound path such as:

p = Path([(1, 0), (1, -1), (2, -1),
          (np.nan, np.nan), (-1, -1), (-2, 1), (-1, 1),
          (2, 2), (0, -1)],
         [Path.MOVETO, Path.LINETO, Path.LINETO,
          Path.MOVETO, Path.LINETO, Path.LINETO, Path.LINETO,
          Path.CLOSEPOLY, Path.LINETO])

Here the second MOVETO is (nan, nan). I plotted this path without simplification to see what the intended plot should be like.

So it seems like, when plotting, if CLOSEPOLY is encountered without having a valid MOVETO vertex, it plots the point corresponding to the CLOSEPOLY (in this case, it is point 8 at (2, 2)) but doesn't close the polygon. After this, the LINETO to (0, -1) is continuous with the previously existing path.

Here it looks like we are still adding the inbetween LINETOs and just not starting/closing the path. Does it therefore merge into the first path in this case?

So yes, you are correct, and it seems to be the expected result as well.

Therefore, the simplified Path would be:

>>> p.cleaned(simplify=True)
Path(array([[ 1.,  0.],
       [ 1., -1.],
       [ 2., -1.],
       [nan, nan],
       [-1., -1.],
       [-2.,  1.],
       [-1.,  1.],
       [ 0., -1.],
       [ 0., -1.],
       [ 0.,  0.]]), array([1, 2, 2, 1, 2, 2, 2, 2, 2, 0], dtype=uint8))

Could you add a test for this case as well?

I think that the compound path discussed above will be good for the test.

}
}

/* NOTE: We used to skip this very short segments, but if
you have a lot of them cumulatively, you can miss
maxima or minima in the data. */
Expand Down Expand Up @@ -919,6 +948,8 @@ class PathSimplifier : protected EmbeddedQueue<9>
bool m_moveto;
bool m_after_moveto;
bool m_clipped;
bool m_has_init;
double m_initX, m_initY;
double m_lastx, m_lasty;

double m_origdx;
Expand Down
Loading