我有一些二维坐标点（蓝点）。
我想要得到这三个点，使它们构成一个三角形，并且这个三角形中包含D点（红点）。 如果没有这样的三角形，则可以抛出异常。
所以对于上面的图片，我想要得到黑色点：
目前我做过的事情： 我认为可以通过它们与D点的距离将这些点排序，然后从排序好的列表中取前三个点。但是问题在于，这三个最近的点可能组成一个不包括点D的三角形。这在下面的图片中显示：
除了得到错误的点之外，我还不能确定D是否位于找到的点的凸包内，因此无法确定是否存在包含点D的三角形。 这就是我卡住的地方。
获取形成三角形的最近点
9
- Rico-E
3
1请澄清条件是什么：应该最小化距离的总和还是三角形的面积？ - TaW
@TaW：嗯......实际上：我不知道。我想要得到“最等边三角形”。但事实上：我认为，无论哪个条件被满足都没有关系。 - Rico-E
1判断一个点是否在三角形内的算法可以在math.stackexchange上找到：http://math.stackexchange.com/questions/51326/determining-if-an-arbitrary-point-lies-inside-a-triangle-defined-by-three-points - Pieter Geerkens
3个回答
2
关键是要在寻找有效解决方案的同时，专注于最优解决方案：
对于每个点： - 存储到目标点的距离 - 存储相对于目标点的位置。
我会使用以下枚举来存储位置：
enum RelativePosition
{
ll,
le,
lg,
eg,
gg,
ge,
gl,
el,
ee
}
第一个字母表示点相对于目标点的x坐标，第二个字母表示点相对于目标点的y坐标。
l表示小于，g表示大于，e表示等于
按距离（升序）排序您的点以接近目标点。从最接近的点开始，根据相对位置获取一组候选点，这些候选点将在目标周围形成三角形。还要从这些候选项中选择与目标最接近的点，并以相同方式继续进行第三个点。
我现在在手机上，很难提供代码，但我将能够在一两个小时内编写它。
编辑：
抱歉耽搁了。以下是一些代码。
您会发现在ValidPositions方法中，我硬编码了所有相对于第一个和第二个点位置的有效位置。我知道它们之间存在数学关系并且可以生成，但让我们说我将其作为练习。：）
即使有了这种方法，也有些情况下您无法确定目标点是否在三角形区域内（请参见UncertainSolution方法）。但是，如果TriangleContainsPoint的数量减少，则测试次数会减少。
编辑2：修复了TriangleContainsPoint方法中的错误。
class Point2D
{
public double X { get; set; }
public double Y { get; set; }
}
enum RelPos2D
{
ll = 1,
le = 2,
lg = 3,
eg = 4,
gg = 5,
ge = 6,
gl = 7,
el = 8,
ee = 0
}
static class Tools2D
{
public static double Distance(Point2D Point1, Point2D Point2)
{
return Math.Sqrt(Math.Pow(Point1.X - Point2.X, 2) + Math.Pow(Point1.Y - Point2.Y, 2));
}
public static RelPos2D RelativePosition(Point2D Of, Point2D To)
{
int xRel = Of.X < To.X ? -1 : Of.X > To.X ? 1 : 0;
int yRel = Of.Y < To.Y ? -1 : Of.Y > To.Y ? 1 : 0;
switch (xRel)
{
case -1:
switch (yRel)
{
case -1: return RelPos2D.ll;
case 0: return RelPos2D.le;
case 1: return RelPos2D.lg;
}
break;
case 0:
switch (yRel)
{
case -1: return RelPos2D.el;
case 0: return RelPos2D.ee;
case 1: return RelPos2D.eg;
}
break;
case 1:
switch (yRel)
{
case -1: return RelPos2D.gl;
case 0: return RelPos2D.ge;
case 1: return RelPos2D.gg;
}
break;
}
return RelPos2D.ee; // never reached
}
public static double TriangleArea(Point2D Point1, Point2D Point2, Point2D Point3)
{
return 1 / 2d *
(
(Point1.X - Point3.X) * (Point2.Y - Point1.Y) -
(Point1.X - Point2.X) * (Point3.Y - Point1.Y)
);
}
public static bool TriangleContainsPoint(Point2D Point1, Point2D Point2, Point2D Point3, Point2D Target)
{
var s = Point1.Y * Point3.X - Point1.X * Point3.Y + (Point3.Y - Point1.Y) * Target.X + (Point1.X - Point3.X) * Target.Y;
var t = Point1.X * Point2.Y - Point1.Y * Point2.X + (Point1.Y - Point2.Y) * Target.X + (Point2.X - Point1.X) * Target.Y;
if ((s < 0) != (t < 0))
return false;
var area = TriangleArea(Point1, Point2, Point3);
var sign = area < 0 ? -1 : 1;
s *= sign;
t *= sign;
area *= sign;
return s > 0 && t > 0 && (s + t) < 2 * area;
}
}
class ProblemSolver
{
private static RelPos2D[] AllPositions = new RelPos2D[]
{
RelPos2D.ee,
RelPos2D.eg,
RelPos2D.el,
RelPos2D.ge,
RelPos2D.gg,
RelPos2D.gl,
RelPos2D.le,
RelPos2D.lg,
RelPos2D.ll,
};
private static RelPos2D[] NoPositions = new RelPos2D[0];
private static RelPos2D[] ValidPositions(RelPos2D Pos1, RelPos2D Pos2)
{
if (Pos1 == RelPos2D.ee || Pos2 == RelPos2D.ee)
return AllPositions;
switch (Pos1)
{
case RelPos2D.ll:
switch (Pos2)
{
case RelPos2D.ll:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gg };
case RelPos2D.le:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gg, RelPos2D.ge };
case RelPos2D.lg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gg, RelPos2D.ge, RelPos2D.gl };
case RelPos2D.eg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gg, RelPos2D.ge, RelPos2D.gl, RelPos2D.el };
case RelPos2D.gg:
return AllPositions;
case RelPos2D.ge:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.le, RelPos2D.lg, RelPos2D.eg, RelPos2D.gg };
case RelPos2D.gl:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.lg, RelPos2D.eg, RelPos2D.gg };
case RelPos2D.el:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.eg, RelPos2D.gg };
}
break;
case RelPos2D.le:
switch (Pos2)
{
case RelPos2D.ll:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gg, RelPos2D.ge };
case RelPos2D.le:
return NoPositions;
case RelPos2D.lg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.ge, RelPos2D.gl };
case RelPos2D.eg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.ge, RelPos2D.gl, RelPos2D.el };
case RelPos2D.gg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.ge, RelPos2D.gl, RelPos2D.el, RelPos2D.ll };
case RelPos2D.ge:
return AllPositions.Except(new RelPos2D[] { Pos1, Pos2 }).ToArray();
case RelPos2D.gl:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.lg, RelPos2D.eg, RelPos2D.gg };
case RelPos2D.el:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.eg, RelPos2D.gg };
}
break;
case RelPos2D.lg:
switch (Pos2)
{
case RelPos2D.ll:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gg, RelPos2D.ge, RelPos2D.gl };
case RelPos2D.le:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.ge, RelPos2D.gl };
case RelPos2D.lg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gl};
case RelPos2D.eg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gl, RelPos2D.el };
case RelPos2D.gg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gl, RelPos2D.el, RelPos2D.ll };
case RelPos2D.ge:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gl, RelPos2D.el, RelPos2D.ll, RelPos2D.le };
case RelPos2D.gl:
return AllPositions;
case RelPos2D.el:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.eg, RelPos2D.gg, RelPos2D.ge, RelPos2D.gl };
}
break;
case RelPos2D.eg:
switch (Pos2)
{
case RelPos2D.ll:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gg, RelPos2D.ge, RelPos2D.gl, RelPos2D.el };
case RelPos2D.le:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.ge, RelPos2D.gl, RelPos2D.el };
case RelPos2D.lg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gl, RelPos2D.el };
case RelPos2D.eg:
return NoPositions;
case RelPos2D.gg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.el, RelPos2D.ll };
case RelPos2D.ge:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.el, RelPos2D.ll, RelPos2D.le };
case RelPos2D.gl:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.el, RelPos2D.ll, RelPos2D.le, RelPos2D.lg };
case RelPos2D.el:
return AllPositions.Except(new RelPos2D[] { Pos1, Pos2}).ToArray();
}
break;
case RelPos2D.gg:
switch (Pos2)
{
case RelPos2D.ll:
return AllPositions;
case RelPos2D.le:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.ge, RelPos2D.gl, RelPos2D.el, RelPos2D.ll };
case RelPos2D.lg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gl, RelPos2D.el, RelPos2D.ll };
case RelPos2D.eg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.el, RelPos2D.ll };
case RelPos2D.gg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.ll };
case RelPos2D.ge:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.ll, RelPos2D.le};
case RelPos2D.gl:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.ll, RelPos2D.le, RelPos2D.lg };
case RelPos2D.el:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.ll, RelPos2D.le, RelPos2D.lg, RelPos2D.eg };
}
break;
case RelPos2D.ge:
switch (Pos2)
{
case RelPos2D.ll:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.le, RelPos2D.lg, RelPos2D.eg, RelPos2D.gg };
case RelPos2D.le:
return AllPositions.Except(new RelPos2D[] { Pos1, Pos2 }).ToArray();
case RelPos2D.lg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.gl, RelPos2D.el, RelPos2D.ll, RelPos2D.le };
case RelPos2D.eg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.el, RelPos2D.ll, RelPos2D.le };
case RelPos2D.gg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.ll, RelPos2D.le };
case RelPos2D.ge:
return NoPositions;
case RelPos2D.gl:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.le, RelPos2D.lg };
case RelPos2D.el:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.le, RelPos2D.lg, RelPos2D.eg };
}
break;
case RelPos2D.gl:
switch (Pos2)
{
case RelPos2D.ll:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.lg, RelPos2D.eg, RelPos2D.gg };
case RelPos2D.le:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.lg, RelPos2D.eg, RelPos2D.gg, RelPos2D.ge };
case RelPos2D.lg:
return AllPositions;
case RelPos2D.eg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.el, RelPos2D.ll, RelPos2D.le, RelPos2D.lg };
case RelPos2D.gg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.ll, RelPos2D.le, RelPos2D.lg };
case RelPos2D.ge:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.le, RelPos2D.lg};
case RelPos2D.gl:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.lg };
case RelPos2D.el:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.lg, RelPos2D.eg };
}
break;
case RelPos2D.el:
switch (Pos2)
{
case RelPos2D.ll:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.eg, RelPos2D.gg };
case RelPos2D.le:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.eg, RelPos2D.gg, RelPos2D.ge };
case RelPos2D.lg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.eg, RelPos2D.gg, RelPos2D.ge, RelPos2D.gl };
case RelPos2D.eg:
return AllPositions.Except(new RelPos2D[] { Pos1, Pos2 }).ToArray();
case RelPos2D.gg:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.ll, RelPos2D.le, RelPos2D.lg, RelPos2D.eg };
case RelPos2D.ge:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.le, RelPos2D.lg, RelPos2D.eg };
case RelPos2D.gl:
return new RelPos2D[] { RelPos2D.ee, RelPos2D.lg, RelPos2D.eg };
case RelPos2D.el:
return NoPositions;
}
break;
}
return NoPositions;
}
private static bool UncertainSolution(RelPos2D Pos1, RelPos2D Pos2, RelPos2D Pos3)
{
RelPos2D[] array = new RelPos2D[] { Pos1, Pos2, Pos3 };
return
(array.Contains(RelPos2D.ll) && array.Contains(RelPos2D.gg)) ||
(array.Contains(RelPos2D.lg) && array.Contains(RelPos2D.gl));
}
public Tuple<Point2D, Point2D, Point2D> Solve(Point2D Target, params Point2D[] Points)
{
Dictionary<Point2D, double> distanceToTarget = new Dictionary<Point2D, double>();
Dictionary<Point2D, RelPos2D> relativePosition = new Dictionary<Point2D,RelPos2D>();
List<int> visited = new List<int>();
Dictionary<RelPos2D, int> countPerPosition = new Dictionary<RelPos2D, int>()
{
{RelPos2D.ee,0},
{RelPos2D.eg,0},
{RelPos2D.el,0},
{RelPos2D.ge,0},
{RelPos2D.gg,0},
{RelPos2D.gl,0},
{RelPos2D.le,0},
{RelPos2D.lg,0},
{RelPos2D.ll,0}
};
foreach (var point in Points)
{
distanceToTarget.Add(point, Tools2D.Distance(point, Target));
RelPos2D position = Tools2D.RelativePosition(point, Target);
relativePosition.Add(point, position);
countPerPosition[position]++;
}
//check countPerPosition to see if there are solutions
int pointsCount = Points.Length;
bool noSolutions = false;
foreach (var key in countPerPosition.Keys)
{
if (countPerPosition[key] == pointsCount)
{
noSolutions = true;
break;
}
}
noSolutions = noSolutions ||
countPerPosition[RelPos2D.ll] + countPerPosition[RelPos2D.le] + countPerPosition[RelPos2D.lg] == pointsCount ||
countPerPosition[RelPos2D.lg] + countPerPosition[RelPos2D.eg] + countPerPosition[RelPos2D.gg] == pointsCount ||
countPerPosition[RelPos2D.gg] + countPerPosition[RelPos2D.ge] + countPerPosition[RelPos2D.gl] == pointsCount ||
countPerPosition[RelPos2D.ll] + countPerPosition[RelPos2D.el] + countPerPosition[RelPos2D.gl] == pointsCount;
if (noSolutions)
throw new Exception("No solutions.");
var orderedPoints = Points.OrderBy(point => distanceToTarget[point]);
bool found = false;
Point2D
Point1 = null,
Point2 = null,
Point3 = null;
RelPos2D PosPoint1,
PosPoint2,
PosPoint3;
foreach (var point1 in orderedPoints)
{
Point1 = point1;
PosPoint1 = relativePosition[Point1];
var point2Candidates = orderedPoints.Where(p => p != Point1)
.OrderBy(p => distanceToTarget[p]);
//this should not happen because we know that we have at least one solution
if (point2Candidates.Count() == 0)
continue;
foreach (var point2 in point2Candidates)
{
Point2 = point2;
PosPoint2 = relativePosition[Point2];
var point3ValidPositions = ValidPositions(PosPoint1, PosPoint2);
var point3Candidates = orderedPoints.Where(p => p != Point1 && p != Point2 && point3ValidPositions.Contains(relativePosition[p]))
.OrderBy(p => distanceToTarget[p]);
if (point3Candidates.Count() == 0)
continue;
foreach (var point3 in point3Candidates)
{
Point3 = point3;
PosPoint3 = relativePosition[Point3];
//check if already visited
//hash subject to conflicts
var hash = Point1.GetHashCode() *
Point2.GetHashCode() *
Point3.GetHashCode();
if (visited.Contains(hash))
continue;
if (UncertainSolution(PosPoint1, PosPoint2, PosPoint3))
{
found = Tools2D.TriangleContainsPoint(Point1, Point2, Point3, Target);
}
else
{
found = true;
}
if (found)
break;
visited.Add(hash);
}
if (found)
break;
}
if (found)
break;
}
if (found)
return new Tuple<Point2D, Point2D, Point2D>(Point1, Point2, Point3);
throw new Exception("No solutions.");
}
}
class Program
{
static void Main(string[] args)
{
ProblemSolver ps = new ProblemSolver();
Random r = new Random();
List<Point2D> points = new List<Point2D>();
Point2D target = new Point2D()
{
//X = r.NextDouble() * 10,
//Y = r.NextDouble() * 10
X = r.Next(11),
Y = r.Next(11)
};
for (int i = 0; i < 10; i++)
points.Add(new Point2D()
{
//X = r.NextDouble() * 10,
//Y = r.NextDouble() * 10
X = r.Next(11),
Y = r.Next(11)
});
Console.WriteLine("Target: {0}X: {1}{0}Y: {2}{0}", Environment.NewLine, target.X, target.Y);
Stopwatch sw = new Stopwatch();
sw.Start();
try
{
var solution = ps.Solve(target, points.ToArray());
Console.WriteLine("Solution: {0}X1: {1}{0}Y1: {2}{0}X2: {3}{0}Y2: {4}{0}X3: {5}{0}Y3: {6}{0}",
Environment.NewLine,
solution.Item1.X,
solution.Item1.Y,
solution.Item2.X,
solution.Item2.Y,
solution.Item3.X,
solution.Item3.Y
);
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
sw.Stop();
Console.WriteLine("Solved in {0} ms", sw.ElapsedMilliseconds);
Console.ReadLine();
}
- B0Andrew
3
听起来是个有趣的想法。我原本打算建议存储距离和角度列表，然后从小距离和足够大的角度差中选择。我也有一种直觉，认为需要进行一些试错，并且最佳解决方案不能通过直接方式找到。但这只是我的直觉。 - TaW
我同意TaW的观点，这听起来是一个非常好的主意。我期待着你的示例代码。 - Rico-E
也许从Delaunay三角剖分开始，并对相邻边进行角度排序，找到距离查询点最近的三角剖分点，可以帮助您减少平均搜索空间（O(log N)）。如果在同一组点上有许多查询点，则可能会减少您的搜索空间。 - Nuclearman
2
正如TaW在评论中正确指出的，基本形式下的以下算法并不总是能找到最佳解决方案或任何解决方案，因为它从两个最近的点开始贪心搜索。
但是可以通过重复算法来修复此问题：如果它无法找到三角形，则可以忽略第一个最接近的点重新迭代它。
如果您没有很多点，则始终可以针对不同的起始点重复算法，以确保找到最优解。
1）找到距离D最近的点，称之为A 2）找到距离D第二近的点，称之为B 3）找到穿过D和A的线的方程，称之为L1（缺少的点必须在L1的另一侧而不是B）
4）找到穿过D和B的线的方程，称之为L2（缺少的点必须在L2的另一侧而不是A）
5）筛选其余的点：只留下那些在L1的另一侧而不是B，并且在L2的另一侧而不是A的点
6）如果没有这样的点，则抛出异常（或使用不同的起始点重新迭代）
7）否则找到最接近的一个，称之为C 8）结果是三角形ABC 附加说明：
如果给定它们的坐标，则两点在线的不同侧，如果此方程式给出不同的符号，则X、Y、Z是线方程系数，通常使用A、B、C，但我不想将它们与上面的点标签混淆。
通过以下公式可以找到穿过具有坐标(V1x，V1y)和(V2x，V2y)的两个点的线的方程：
但是可以通过重复算法来修复此问题：如果它无法找到三角形，则可以忽略第一个最接近的点重新迭代它。
如果您没有很多点，则始终可以针对不同的起始点重复算法，以确保找到最优解。
1）找到距离D最近的点，称之为A 2）找到距离D第二近的点，称之为B 3）找到穿过D和A的线的方程，称之为L1（缺少的点必须在L1的另一侧而不是B）
4）找到穿过D和B的线的方程，称之为L2（缺少的点必须在L2的另一侧而不是A）
5）筛选其余的点：只留下那些在L1的另一侧而不是B，并且在L2的另一侧而不是A的点
6）如果没有这样的点，则抛出异常（或使用不同的起始点重新迭代）
7）否则找到最接近的一个，称之为C 8）结果是三角形ABC 附加说明：
如果给定它们的坐标，则两点在线的不同侧，如果此方程式给出不同的符号，则X、Y、Z是线方程系数，通常使用A、B、C，但我不想将它们与上面的点标签混淆。
通过以下公式可以找到穿过具有坐标(V1x，V1y)和(V2x，V2y)的两个点的线的方程：
这给出了直线方程系数的以下公式：
- BartoszKP
4
这确实可以找到两个最近的点。但不一定是三个最近的点或最小的三角形。即使存在解决方案，也不能保证找到任何解决方案。 - TaW
1但是我仍然喜欢它。也许应该重复下一个最接近的点，直到找到解决方案。我们还需要知道任何解决方案是否可行或如何进行优化。 - TaW
我测试了这个方法，必须承认对于1000次运行来说，它比我的方法稍微快一点（2.25%），但我认为我可以改进它。 - B0Andrew
@B0Andrew 考虑提前实现您的LINQ。您有两个
OrderBy调用，它们可能会被重复评估。 - BartoszKP0
你可以使用 Bowyer-Watson 算法，并修改它以查找红点。
- Micromega
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接