我有三个例子，例如：
Start 194 171
Right 216 131
Left 216 203
我想要获取该三角形内的所有点。如何高效地实现这一目标？
获取三角形内的所有点
6
我想要获取该三角形内的所有点。如何高效地实现这一目标？
- Abanoub
3
2你尝试过什么？(http://whathaveyoutried.com) - Oliver Charlesworth
1看看这个是否适合你：http://stackoverflow.com/questions/2771670/calculate-pixels-within-a-polygon
我自己也面临着这个有趣的问题。 - MasterMastic
2你需要在谷歌搜索中使用关键词“光栅化”。搜索“三角形光栅化”会得到一些看起来不错的结果，如果有用的话。 - Stuart Golodetz
2个回答
6
查看z3nth10n的答案以获得更好的输入验证。
介绍：
总体思路是获取三角形每个x范围内的边缘（y值），然后你就有了三角形中每个单独x内存在的所有y值。通过简单的转换，这些点就变成了三角形内的所有点。
你可以将其看作将三角形切分成条纹，每个条纹宽度为1。例如，当X=0时，在A和B之间的线上，Y为6，在A和C之间的线上，Y为-2，因此您可以看到X=0处的条纹位于-2和6之间。因此，你可以知道(0, -2) (0, -1) (0, 0) ... (0, 5) (0, 6)都在三角形中。对于三角形内最小和最大的X，重复以上步骤，即可获得三角形中所有点！
速度：
对于三角形(0, 0) (1, 8) (4, 6)，找到16个点。
执行1000000次耗时3.68秒。
实现：
public IEnumerable<Point> PointsInTriangle(Point pt1, Point pt2, Point pt3)
{
if (pt1.Y == pt2.Y && pt1.Y == pt3.Y)
{
throw new ArgumentException("The given points must form a triangle.");
}
Point tmp;
if (pt2.X < pt1.X)
{
tmp = pt1;
pt1 = pt2;
pt2 = tmp;
}
if (pt3.X < pt2.X)
{
tmp = pt2;
pt2 = pt3;
pt3 = tmp;
if (pt2.X < pt1.X)
{
tmp = pt1;
pt1 = pt2;
pt2 = tmp;
}
}
var baseFunc = CreateFunc(pt1, pt3);
var line1Func = pt1.X == pt2.X ? (x => pt2.Y) : CreateFunc(pt1, pt2);
for (var x = pt1.X; x < pt2.X; x++)
{
int maxY;
int minY = GetRange(line1Func(x), baseFunc(x), out maxY);
for (var y = minY; y <= maxY; y++)
{
yield return new Point(x, y);
}
}
var line2Func = pt2.X == pt3.X ? (x => pt2.Y) : CreateFunc(pt2, pt3);
for (var x = pt2.X; x <= pt3.X; x++)
{
int maxY;
int minY = GetRange(line2Func(x), baseFunc(x), out maxY);
for (var y = minY; y <= maxY; y++)
{
yield return new Point(x, y);
}
}
}
private int GetRange(double y1, double y2, out int maxY)
{
if (y1 < y2)
{
maxY = (int)Math.Floor(y2);
return (int)Math.Ceiling(y1);
}
maxY = (int)Math.Floor(y1);
return (int)Math.Ceiling(y2);
}
private Func<int, double> CreateFunc(Point pt1, Point pt2)
{
var y0 = pt1.Y;
if (y0 == pt2.Y)
{
return x => y0;
}
var m = (double)(pt2.Y - y0) / (pt2.X - pt1.X);
return x => m * (x - pt1.X) + y0;
}
- SimpleVar
6
哈哈，这让我笑了。尊重。 - Kevin Wang
@KevinWang 哦，我看到你在第12个像素上找到了我的彩蛋？现在，真的，是什么？ - SimpleVar
很棒的东西！这帮助了我很多。 - Kyle G.
只是一个小修正：由于
pt1.X（例如）是一个double，因此for循环应该像这样开始：for (var x = Convert.ToInt32(pt1.X); x < pt2.X; x++)，因为line1Func(x)需要一个int。 - Kyle G.@SimpleVar - 我没看到彩蛋。当然，一旦指出来...就很明显了。 - tobeypeters
@tobeypeters 我也没有看到复活节彩蛋。我猜当时凯文觉得这很有趣。 - SimpleVar
3
@SimpleVar的回答很好，但是缺少一个好的有效三角形检查（这可能会导致溢出问题）。
因此，我为Unity3D编写了自己的实现：
public static IEnumerable<T> PointsInTriangle<T>(T pt1, T pt2, T pt3)
where T : IPoint
{
/*
// https://www.geeksforgeeks.org/check-whether-triangle-valid-not-sides-given/
a + b > c
a + c > b
b + c > a
*/
float a = Vector2.Distance(new Vector2(pt1.x, pt1.y), new Vector2(pt2.x, pt2.y)),
b = Vector2.Distance(new Vector2(pt2.x, pt2.y), new Vector2(pt3.x, pt3.y)),
c = Vector2.Distance(new Vector2(pt3.x, pt3.y), new Vector2(pt1.x, pt1.y));
if (a + b <= c || a + c <= b || b + c <= a)
{
Debug.LogWarning($"The given points must form a triangle. {{{pt1}, {pt2}, {pt3}}}");
yield break;
}
if (TriangleArea(pt1, pt2, pt3) <= 1)
{
Point center = GetTriangleCenter(pt1, pt2, pt3);
yield return (T)Activator.CreateInstance(typeof(T), center.x, center.y);
return;
}
T tmp;
if (pt2.x < pt1.x)
{
tmp = pt1;
pt1 = pt2;
pt2 = tmp;
}
if (pt3.x < pt2.x)
{
tmp = pt2;
pt2 = pt3;
pt3 = tmp;
if (pt2.x < pt1.x)
{
tmp = pt1;
pt1 = pt2;
pt2 = tmp;
}
}
var baseFunc = CreateFunc(pt1, pt3);
var line1Func = pt1.x == pt2.x ? (x => pt2.y) : CreateFunc(pt1, pt2);
for (var x = pt1.x; x < pt2.x; ++x)
{
int maxY;
int minY = GetRange(line1Func(x), baseFunc(x), out maxY);
for (int y = minY; y <= maxY; ++y)
yield return (T)Activator.CreateInstance(typeof(T), x, y);
}
var line2Func = pt2.x == pt3.x ? (x => pt2.y) : CreateFunc(pt2, pt3);
for (var x = pt2.x; x <= pt3.x; ++x)
{
int maxY;
int minY = GetRange(line2Func(x), baseFunc(x), out maxY);
for (int y = minY; y <= maxY; ++y)
yield return (T)Activator.CreateInstance(typeof(T), x, y);
}
}
private static int GetRange(float y1, float y2, out int maxY)
{
if (y1 < y2)
{
maxY = Mathf.FloorToInt(y2);
return Mathf.CeilToInt(y1);
}
maxY = Mathf.FloorToInt(y1);
return Mathf.CeilToInt(y2);
}
private static Func<int, float> CreateFunc<T>(T pt1, T pt2)
where T : IPoint
{
var y0 = pt1.y;
if (y0 == pt2.y)
return x => y0;
float m = (float)(pt2.y - y0) / (pt2.x - pt1.x);
return x => m * (x - pt1.x) + y0;
}
public static float TriangleArea<T>(T p1, T p2, T p3)
where T : IPoint
{
float a, b, c;
if (!CheckIfValidTriangle(p1, p2, p3, out a, out b, out c))
return 0;
return TriangleArea(a, b, c);
}
public static float TriangleArea(float a, float b, float c)
{
// Thanks to: http://james-ramsden.com/area-of-a-triangle-in-3d-c-code/
float s = (a + b + c) / 2.0f;
return Mathf.Sqrt(s * (s - a) * (s - b) * (s - c));
}
public static Point GetTriangleCenter<T>(T p0, T p1, T p2)
where T : IPoint
{
// Thanks to: https://dev59.com/jXRB5IYBdhLWcg3wv5tA
return new Point(p0.x + p1.x + p2.x / 3, p0.y + p1.y + p2.y / 3);
}
public static bool CheckIfValidTriangle<T>(T v1, T v2, T v3, out float a, out float b, out float c)
where T : IPoint
{
a = Vector2.Distance(new Vector2(v1.x, v1.y), new Vector2(v2.x, v2.y));
b = Vector2.Distance(new Vector2(v2.x, v2.y), new Vector2(v3.x, v3.y));
c = Vector2.Distance(new Vector2(v3.x, v3.y), new Vector2(v1.x, v1.y));
if (a + b <= c || a + c <= b || b + c <= a)
return false;
return true;
}
IPoint接口可以成为自己Point实现的好起点（例如Clipper、TessDotNet或Poly2Tri库）。您可以随时更改它（使用两个UnityEngine.Vector2或System.Drawing.Point）。
希望这可以帮助您！
编辑：我在此解决了所有错误：
同时，我回答了自己的问题，发问内容在这里：https://stackoverflow.com/a/53734816/3286975
- z3nth10n
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接