在知道一個使用兩個點表示的線段，和另一個點，求另一個點是否在線段上
本文演算法屬于通用的演算法，可以在 WPF 和 UWP 和 Xamarin 等上運行，基本上所有的 .NET 平臺都能執行
如下圖，如果點在線段上，那么修改線段顏色
假定有線段的定義如下
public record Line
{
public Point APoint { get; init; }
public Point BPoint { get; init; }
}
以上代碼使用了 .NET 5 加 C# 9.0 的新語法
在傳入一個點，求這個點是否在線段上，最簡單理解的演算法是根據兩點之間直線距離最短，只需要求 P 點和線段的 AB 兩點的距離是否等于 AB 的距離，如果相等，那么證明 P 點在線段 AB 上，代碼如下
private static bool CheckIsPointOnLine(Point point, Line line, double epsilon = 0.1)
{
// 最簡單理解的演算法是根據兩點之間直線距離最短，只需要求 P 點和線段的 AB 兩點的距離是否等于 AB 的距離，如果相等，那么證明 P 點在線段 AB 上
var ap = point - line.APoint;
var bp = point - line.BPoint;
var ab = line.BPoint - line.APoint;
// 只不過求 Length 內部需要用到一次 Math.Sqrt 性能會比較差
if (Math.Abs(ap.Length + bp.Length - ab.Length) < epsilon)
{
return true;
}
else
{
return false;
}
}
不使用 Vector 類，可以替換為如下計算方法，上面代碼的 ap 等變數是使用 WPF 的兩個點的相減能拿到 Vectore 類，而在 Vectore 類里面有 Length 屬性而優化代碼的，其實核心計算和下面代碼相同，下面代碼是 Tone ?koda 提供的，詳細請看 https://stackoverflow.com/a/56850069/6116637
public static double CalcDistanceBetween2Points(double x1, double y1, double x2, double y2)
{
return Math.Sqrt(Math.Pow (x1 - x2, 2) + Math.Pow (y1 - y2, 2));
}
public static bool PointLinesOnLine (double x, double y, double x1, double y1, double x2, double y2, double allowedDistanceDifference)
{
double dist1 = CalcDistanceBetween2Points(x, y, x1, y1);
double dist2 = CalcDistanceBetween2Points(x, y, x2, y2);
double dist3 = CalcDistanceBetween2Points(x1, y1, x2, y2);
return Math.Abs(dist3 - (dist1 + dist2)) <= allowedDistanceDifference;
}
以下是另一個方法，以下方法性能比上面一個好
根據點和任意線段端點連接的線段和當前線段斜率相同，同時點在兩個端點中間，就可以認為點在線段內
(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1)
因為乘法性能更高，因此計算方法可以如下
(x - x1) * (y2 - y1) = (y - y1) * (x2 - x1)
(x - x1) * (y2 - y1) - (y - y1) * (x2 - x1) = 0
但是乘法的誤差很大，因此還是繼續使用除法
另外，需要判斷點在兩個端點中間
x1 < x < x2, assuming x1 < x2
y1 < y < y2, assuming y1 < y2
以下是代碼
if (EqualPoint(point, line.APoint, epsilon) || EqualPoint(point, line.BPoint, epsilon))
{
return true;
}
// 乘法性能更高，誤差大，請試試在回傳 true 的時候，看看 crossProduct 的值，可以發現這個值依然很大
var crossProduct = (point.X - line.APoint.X) * (line.BPoint.Y - line.APoint.Y) -
(point.Y - line.APoint.Y) * (line.BPoint.X - line.APoint.X);
if (Math.Abs((point.X - line.APoint.X) / (line.BPoint.X - line.APoint.X) - (point.Y - line.APoint.Y) / (line.BPoint.Y - line.APoint.Y)) < epsilon)
{
var minX = Math.Min(line.APoint.X, line.BPoint.X);
var maxX = Math.Max(line.APoint.X, line.BPoint.X);
var minY = Math.Min(line.APoint.Y, line.BPoint.Y);
var maxY = Math.Max(line.APoint.Y, line.BPoint.Y);
if (minX < point.X && point.X < maxX && minY < point.Y && point.Y < maxY)
{
return true;
}
else
{
return false;
}
}
else
{
return false;
}
上面代碼的 crossProduct 是不用使用的，只是為了告訴大家，盡管乘法性能比較好，但是誤差比較大
當然以上演算法有漏洞，在于如果 A 和 B 兩個點的 Y 坐標相同或 X 坐標相同的時候，那么以上演算法不適合，可以先判斷 crossProduct 的值，如果是等于零，那么證明有 A 和 B 兩個點的 Y 坐標相同或 X 坐標相同
var crossProduct = (point.X - line.APoint.X) * (line.BPoint.Y - line.APoint.Y) -
(point.Y - line.APoint.Y) * (line.BPoint.X - line.APoint.X);
// 先判斷 crossProduct 是否等于 0 可以解決 A 和 B 兩個點的 Y 坐標相同或 X 坐標相同的時候，使用除法的坑
if (crossProduct == 0 || Math.Abs((point.X - line.APoint.X) / (line.BPoint.X - line.APoint.X) - (point.Y - line.APoint.Y) / (line.BPoint.Y - line.APoint.Y)) < epsilon)
{
var minX = Math.Min(line.APoint.X, line.BPoint.X);
var maxX = Math.Max(line.APoint.X, line.BPoint.X);
var minY = Math.Min(line.APoint.Y, line.BPoint.Y);
var maxY = Math.Max(line.APoint.Y, line.BPoint.Y);
if (minX <= point.X && point.X <= maxX && minY <= point.Y && point.Y <= maxY)
{
return true;
}
else
{
return false;
}
}
else
{
return false;
}
以上代碼放在 github 和 gitee 歡迎小伙伴訪問
以上方法的計算有些重復，其實加上了 crossProduct 只是為了水平和垂直的線段，其實可以做特殊處理，如下面代碼
public static class Math2DExtensions
{
public static bool CheckIsPointOnLineSegment(Point point, Line line, double epsilon = 0.1)
{
// 以下是另一個方法，以下方法性能比上面一個好
// 根據點和任意線段端點連接的線段和當前線段斜率相同，同時點在兩個端點中間
// (x - x1) / (x2 - x1) = (y - y1) / (y2 - y1)
// x1 < x < x2, assuming x1 < x2
// y1 < y < y2, assuming y1 < y2
// 但是需要額外處理 X1 == X2 和 Y1 == Y2 的計算
var minX = Math.Min(line.APoint.X, line.BPoint.X);
var maxX = Math.Max(line.APoint.X, line.BPoint.X);
var minY = Math.Min(line.APoint.Y, line.BPoint.Y);
var maxY = Math.Max(line.APoint.Y, line.BPoint.Y);
if (!(minX <= point.X) || !(point.X <= maxX) || !(minY <= point.Y) || !(point.Y <= maxY))
{
return false;
}
// 以下處理水平和垂直線段
if (Math.Abs(line.APoint.X - line.BPoint.X) < epsilon)
{
// 如果 X 坐標是相同，那么只需要判斷點的 X 坐標是否相同
// 因為在上面代碼已經判斷了 點的 Y 坐標是在線段兩個點之內
return Math.Abs(line.APoint.X - point.X) < epsilon || Math.Abs(line.BPoint.X - point.X) < epsilon;
}
if (Math.Abs(line.APoint.Y - line.BPoint.Y) < epsilon)
{
return Math.Abs(line.APoint.Y - point.Y) < epsilon || Math.Abs(line.BPoint.Y - point.Y) < epsilon;
}
if (Math.Abs((point.X - line.APoint.X) / (line.BPoint.X - line.APoint.X) - (point.Y - line.APoint.Y) / (line.BPoint.Y - line.APoint.Y)) < epsilon)
{
return true;
}
else
{
return false;
}
}
}
public record Line
{
public Point APoint { get; init; }
public Point BPoint { get; init; }
}
以上代碼放在 github 和 gitee 歡迎小伙伴訪問
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/270477.html
標籤：WPF
上一篇：WPF之影片