Skip to content

Simplify projection-of-point-on-polyline in contour.py. #17803

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
Jul 19, 2020
Merged

Simplify projection-of-point-on-polyline in contour.py. #17803

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
98 changes: 37 additions & 61 deletions lib/matplotlib/contour.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -599,31 +599,6 @@ def labels(self, inline, inline_spacing):
paths[:] = additions


def _find_closest_point_on_leg(p1, p2, p0):
"""Find the closest point to p0 on line segment connecting p1 and p2."""

# handle degenerate case
if np.all(p2 == p1):
d = np.sum((p0 - p1)**2)
return d, p1

d21 = p2 - p1
d01 = p0 - p1

# project on to line segment to find closest point
proj = np.dot(d01, d21) / np.dot(d21, d21)
if proj < 0:
proj = 0
if proj > 1:
proj = 1
pc = p1 + proj * d21

# find squared distance
d = np.sum((pc-p0)**2)

return d, pc


def _is_closed_polygon(X):
"""
Return whether first and last object in a sequence are the same. These are
Expand All @@ -633,39 +608,40 @@ def _is_closed_polygon(X):
return np.allclose(X[0], X[-1], rtol=1e-10, atol=1e-13)


def _find_closest_point_on_path(lc, point):
def _find_closest_point_on_path(xys, p):
"""
Parameters
----------
lc : coordinates of vertices
point : coordinates of test point
xys : (N, 2) array-like
Coordinates of vertices.
p : (float, float)
Coordinates of point.

Returns
-------
d2min : float
Minimum square distance of *p* to *xys*.
proj : (float, float)
Projection of *p* onto *xys*.
imin : (int, int)
Consecutive indices of vertices of segment in *xys* where *proj* is.
Segments are considered as including their end-points; i.e if the
closest point on the path is a node in *xys* with index *i*, this
returns ``(i-1, i)``. For the special case where *xys* is a single
point, this returns ``(0, 0)``.
"""

# find index of closest vertex for this segment
ds = np.sum((lc - point[None, :])**2, 1)
imin = np.argmin(ds)

dmin = np.inf
xcmin = None
legmin = (None, None)

closed = _is_closed_polygon(lc)

# build list of legs before and after this vertex
legs = []
if imin > 0 or closed:
legs.append(((imin-1) % len(lc), imin))
if imin < len(lc) - 1 or closed:
legs.append((imin, (imin+1) % len(lc)))

for leg in legs:
d, xc = _find_closest_point_on_leg(lc[leg[0]], lc[leg[1]], point)
if d < dmin:
dmin = d
xcmin = xc
legmin = leg

return (dmin, xcmin, legmin)
if len(xys) == 1:
return (((p - xys[0]) ** 2).sum(), xys[0], (0, 0))
dxys = xys[1:] - xys[:-1] # Individual segment vectors.
norms = (dxys ** 2).sum(axis=1)
norms[norms == 0] = 1 # For zero-length segment, replace 0/0 by 0/1.
rel_projs = np.clip( # Project onto each segment in relative 0-1 coords.
((p - xys[:-1]) * dxys).sum(axis=1) / norms,
0, 1)[:, None]
projs = xys[:-1] + rel_projs * dxys # Projs. onto each segment, in (x, y).
d2s = ((projs - p) ** 2).sum(axis=1) # Squared distances.
imin = np.argmin(d2s)
return (d2s[imin], projs[imin], (imin, imin+1))


docstring.interpd.update(contour_set_attributes=r"""
Expand Down Expand Up @@ -1341,8 +1317,8 @@ def find_nearest_contour(self, x, y, indices=None, pixel=True):
``(x, y)``.
xmin, ymin : float
The point in the contour plot that is closest to ``(x, y)``.
d : float
The distance from ``(xmin, ymin)`` to ``(x, y)``.
d2 : float
The squared distance from ``(xmin, ymin)`` to ``(x, y)``.
Copy link
Member

Choose a reason for hiding this comment

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

This seems to be public, so I'm not sure we should change this.

Copy link
Contributor Author

Choose a reason for hiding this comment

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

I'm just describing the actual behavior, not changing it.

"""

# This function uses a method that is probably quite
Expand All @@ -1356,7 +1332,7 @@ def find_nearest_contour(self, x, y, indices=None, pixel=True):
if indices is None:
indices = list(range(len(self.levels)))

dmin = np.inf
d2min = np.inf
conmin = None
segmin = None
xmin = None
Expand All @@ -1375,16 +1351,16 @@ def find_nearest_contour(self, x, y, indices=None, pixel=True):
if pixel:
lc = trans.transform(lc)

d, xc, leg = _find_closest_point_on_path(lc, point)
if d < dmin:
dmin = d
d2, xc, leg = _find_closest_point_on_path(lc, point)
if d2 < d2min:
d2min = d2
conmin = icon
segmin = segNum
imin = leg[1]
xmin = xc[0]
ymin = xc[1]

return (conmin, segmin, imin, xmin, ymin, dmin)
return (conmin, segmin, imin, xmin, ymin, d2min)


@docstring.dedent_interpd
Expand Down