Get point on a path or polyline which is closest to a disconnected point

Question

I have a point and a path, polyline, or set of points to create lines.

How can I find the point on my path which closest to another disconnected point?

It's easy to store or transfer my path / polyline as any of the WPF geometry controls, but do any of these controls come with GetDistanceFrom type methods? Is there any simply way to achieve this goal?

Answer 1

Here is the algorithm that I've implemented as a solution. There's nothing 'non-obvious' in here if you've spent more than ten minutes thinking about it.

I'll reference the distance algorithm which you can find here: https://stackoverflow.com/a/1501725/146077

1. Collect the Polyline as a set of ordered lines
2. Traverse this set, testing the distance from the target point to each line
3. Once the closest line has been identified run the below to identify the closest point on the line.

The answer linked above uses a projection to test if the point is closest to either end of the interval than any other point. I've modified the function from that answer to return the point's position on that projection. Beware that this answer might not make any sense if you haven't read the linked answer!

private Point GetClosestPointOnLine(Point start, Point end, Point p)
{
    var length = (start - end).LengthSquared;

    if (length == 0.0)
        return start; 

    // Consider the line extending the segment, parameterized as v + t (w - v).
    // We find projection of point p onto the line. 
    // It falls where t = [(p-v) . (w-v)] / |w-v|^2
    var t = (p - start) * (end - start) / length;

    if (t < 0.0)
        return start; // Beyond the 'v' end of the segment
    else if (t > 1.0)
        return end;   // Beyond the 'w' end of the segment

    // Projection falls on the segment
    var projection = start + t * (end - start);  
    return projection;
}

Answer 2

The following method GetClosestPointOnPath() is a generalization of @KirkBroadhurst's GetClosestPointOnLine() method, i.e. it works with any path geometry, i.e. lines, curves, ellipses, etc.

public Point GetClosestPointOnPath(Point p, Geometry geometry)
{
    PathGeometry pathGeometry = geometry.GetFlattenedPathGeometry();

    var points = pathGeometry.Figures.Select(f => GetClosestPointOnPathFigure(f, p))
        .OrderBy(t => t.Item2).FirstOrDefault();
    return (points == null) ? new Point(0, 0) : points.Item1;
}

private Tuple<Point, double> GetClosestPointOnPathFigure(PathFigure figure, Point p)
{
    List<Tuple<Point, double>> closePoints = new List<Tuple<Point,double>>();
    Point current = figure.StartPoint;
    foreach (PathSegment s in figure.Segments)
    {
        PolyLineSegment segment = s as PolyLineSegment;
        LineSegment line = s as LineSegment;
        Point[] points;
        if (segment != null)
        {
            points = segment.Points.ToArray();
        }
        else if (line != null)
        {
            points = new[] { line.Point };
        }
        else
        {
            throw new InvalidOperationException("Unexpected segment type");
        }
        foreach (Point next in points)
        {
            Point closestPoint = GetClosestPointOnLine(current, next, p);
            double d = (closestPoint - p).LengthSquared;
            closePoints.Add(new Tuple<Point, double>(closestPoint, d));
            current = next;
        }
    }
    return closePoints.OrderBy(t => t.Item2).First();
}

private Point GetClosestPointOnLine(Point start, Point end, Point p)
{
    double length = (start - end).LengthSquared;
    if (length == 0.0)
    {
        return start;
    }
    Vector v = end - start;
    double param = (p - start) * v / length;
    return (param < 0.0) ? start : (param > 1.0) ? end : (start + param * v);
}

Here is a small sample program that demonstrates how to use this method:

MainWindow.xaml:

<Window x:Class="PathHitTestSample.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        Title="MainWindow" Height="350" Width="525">
    <Canvas x:Name="canvas">
        <TextBlock Text="Left-click into this window" Margin="10" Foreground="Gray"/>
        <Path x:Name="path"
              Data="M96,63 C128,122 187,133 275,95 L271,158 C301,224 268,240 187,218 L74,218 95,270 384,268 C345,148 376,106 456,120 494,64 314,60 406,4 A10,10 30 0 1 300,20"
              Stroke="Black" StrokeThickness="1"
              HorizontalAlignment="Left" VerticalAlignment="Top"/>
        <Rectangle x:Name="marker" Fill="Red" Canvas.Left="0" Canvas.Top="0" Width="10" Height="10" Margin="-5,-5,0,0"
                   Visibility="Hidden"/>
    </Canvas>
</Window>

MainWindow.xaml.cs:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;

namespace PathHitTestSample
{
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();
        }

        protected override void OnMouseLeftButtonDown(MouseButtonEventArgs e)
        {
            Point p = e.GetPosition(canvas);
            Point pointOnPath = GetClosestPointOnPath(p, path.Data);
            marker.Visibility = Visibility.Visible;
            Canvas.SetLeft(marker, pointOnPath.X);
            Canvas.SetTop(marker, pointOnPath.Y);
        }

        ... add above methods here ...
    }
}