Tôi sẽ dẫn đầu với kết quả thử nghiệm của mình.
Các trường hợp kiểm tra mã và thực hiện là trong C#
public void ClosestPointToShouldWork()
{
var r = new Random(0);
double next() => r.NextDouble() * 5 - 1;
var t = new Triangle(new Vector3(0,0,0), new Vector3(3.5,2,0), new Vector3(3,0.0,0));
DrawTriangle(t);
var hash = new Vector3(0, 0, 0);
for (int i = 0; i < 800; i++)
{
var pt = new Vector3(next(), next(), 0);
var pc = t.ClosestPointTo(pt);
hash += pc;
DrawLine(pc,pt);
}
// Test the hash
// If it doesn't match then eyeball the visualization
// and see what has gone wrong
hash.ShouldBeApproximately(new Vector3(1496.28118561104,618.196568578824,0),1e-5 );
}
Mã thực hiện là khó sử dụng như tôi có một số khuôn khổ lớp học. Hy vọng rằng bạn có thể coi đây là mã giả và rút ra thuật toán. Các loại véc tơ thô là từ https://www.nuget.org/packages/System.DoubleNumerics/.
Lưu ý rằng một số thuộc tính của Tam giác có thể được lưu trong bộ nhớ cache để cải thiện hiệu suất.
Lưu ý rằng để trả lại điểm gần nhất không yêu cầu bất kỳ căn bậc hai nào và không yêu cầu chuyển sự cố sang 2D.
Thuật toán trước tiên sẽ nhanh chóng kiểm tra nếu điểm kiểm tra gần nhất với vùng điểm kết thúc. Nếu đó là không thuyết phục nó sau đó kiểm tra các khu vực cạnh bên ngoài từng người một. Nếu những kiểm tra đó thất bại thì điểm nằm trong tam giác. Lưu ý rằng đối với các điểm được chọn ngẫu nhiên cách xa tam giác, rất có thể điểm gần nhất sẽ là điểm góc của tam giác.
public class Triangle
{
public Vector3 A => EdgeAb.A;
public Vector3 B => EdgeBc.A;
public Vector3 C => EdgeCa.A;
public readonly Edge3 EdgeAb;
public readonly Edge3 EdgeBc;
public readonly Edge3 EdgeCa;
public Triangle(Vector3 a, Vector3 b, Vector3 c)
{
EdgeAb = new Edge3(a, b);
EdgeBc = new Edge3(b, c);
EdgeCa = new Edge3(c, a);
TriNorm = Vector3.Cross(a - b, a - c);
}
public Vector3[] Verticies => new[] {A, B, C};
public readonly Vector3 TriNorm;
private static readonly RangeDouble ZeroToOne = new RangeDouble(0,1);
public Plane TriPlane => new Plane(A, TriNorm);
// The below three could be pre-calculated to
// trade off space vs time
public Plane PlaneAb => new Plane(EdgeAb.A, Vector3.Cross(TriNorm, EdgeAb.Delta ));
public Plane PlaneBc => new Plane(EdgeBc.A, Vector3.Cross(TriNorm, EdgeBc.Delta ));
public Plane PlaneCa => new Plane(EdgeCa.A, Vector3.Cross(TriNorm, EdgeCa.Delta ));
public static readonly RangeDouble Zero1 = new RangeDouble(0,1);
public Vector3 ClosestPointTo(Vector3 p)
{
// Find the projection of the point onto the edge
var uab = EdgeAb.Project(p);
var uca = EdgeCa.Project(p);
if (uca > 1 && uab < 0)
return A;
var ubc = EdgeBc.Project(p);
if (uab > 1 && ubc < 0)
return B;
if (ubc > 1 && uca < 0)
return C;
if (ZeroToOne.Contains(uab) && !PlaneAb.IsAbove(p))
return EdgeAb.PointAt(uab);
if (ZeroToOne.Contains(ubc) && !PlaneBc.IsAbove(p))
return EdgeBc.PointAt(ubc);
if (ZeroToOne.Contains(uca) && !PlaneCa.IsAbove(p))
return EdgeCa.PointAt(uca);
// The closest point is in the triangle so
// project to the plane to find it
return TriPlane.Project(p);
}
}
Và cấu trúc cạnh
public struct Edge3
{
public readonly Vector3 A;
public readonly Vector3 B;
public readonly Vector3 Delta;
public Edge3(Vector3 a, Vector3 b)
{
A = a;
B = b;
Delta = b -a;
}
public Vector3 PointAt(double t) => A + t * Delta;
public double LengthSquared => Delta.LengthSquared();
public double Project(Vector3 p) => (p - A).Dot(Delta)/LengthSquared;
}
Và cấu trúc máy bay
public struct Plane
{
public Vector3 Point;
public Vector3 Direction;
public Plane(Vector3 point, Vector3 direction)
{
Point = point;
Direction = direction;
}
public bool IsAbove(Vector3 q) => Direction.Dot(q - Point) > 0;
}
kẹp tọa barycentric không cho chiếu trực giao với mép gần nhất và do đó không phải là khoảng cách đúng nếu một điểm trên các cạnh (không có đỉnh) là gần nhất. –