jb.*_*jb. 35 .net c# algorithm
我正在尝试确定一个点是否在多边形内.Polygon由Point对象数组定义.我可以很容易地弄清楚该点是否在多边形的有界框内,但我不知道如何判断它是否在实际多边形内.如果可能的话,我只想使用C#和WinForms.我宁愿不打电话给OpenGL或其他什么来做这个简单的任务.
这是我到目前为止的代码:
private void CalculateOuterBounds()
{
//m_aptVertices is a Point[] which holds the vertices of the polygon.
// and X/Y min/max are just ints
Xmin = Xmax = m_aptVertices[0].X;
Ymin = Ymax = m_aptVertices[0].Y;
foreach(Point pt in m_aptVertices)
{
if(Xmin > pt.X)
Xmin = pt.X;
if(Xmax < pt.X)
Xmax = pt.X;
if(Ymin > pt.Y)
Ymin = pt.Y;
if(Ymax < pt.Y)
Ymax = pt.Y;
}
}
public bool Contains(Point pt)
{
bool bContains = true; //obviously wrong at the moment :)
if(pt.X < Xmin || pt.X > Xmax || pt.Y < Ymin || pt.Y > Ymax)
bContains = false;
else
{
//figure out if the point is in the polygon
}
return bContains;
}
小智 58
我在这里检查了代码并且都有问题.
最好的方法是:
/// <summary>
/// Determines if the given point is inside the polygon
/// </summary>
/// <param name="polygon">the vertices of polygon</param>
/// <param name="testPoint">the given point</param>
/// <returns>true if the point is inside the polygon; otherwise, false</returns>
public static bool IsPointInPolygon4(PointF[] polygon, PointF testPoint)
{
bool result = false;
int j = polygon.Count() - 1;
for (int i = 0; i < polygon.Count(); i++)
{
if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y)
{
if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X)
{
result = !result;
}
}
j = i;
}
return result;
}
Kei*_*ith 26
在我的项目中,接受的答案对我不起作用.我最终使用了这里找到的代码.
public static bool IsInPolygon(Point[] poly, Point p)
{
Point p1, p2;
bool inside = false;
if (poly.Length < 3)
{
return inside;
}
var oldPoint = new Point(
poly[poly.Length - 1].X, poly[poly.Length - 1].Y);
for (int i = 0; i < poly.Length; i++)
{
var newPoint = new Point(poly[i].X, poly[i].Y);
if (newPoint.X > oldPoint.X)
{
p1 = oldPoint;
p2 = newPoint;
}
else
{
p1 = newPoint;
p2 = oldPoint;
}
if ((newPoint.X < p.X) == (p.X <= oldPoint.X)
&& (p.Y - (long) p1.Y)*(p2.X - p1.X)
< (p2.Y - (long) p1.Y)*(p.X - p1.X))
{
inside = !inside;
}
oldPoint = newPoint;
}
return inside;
}
Sae*_*iri 11
见这是在C++中,可以在C#中的相同方式进行.
凸多边形太容易了:
如果多边形是凸的,则可以将多边形视为来自第一个顶点的"路径".如果该点始终位于构成路径的所有线段的同一侧,则该点位于此多边形的内部.
给定P0(x0,y0)和P1(x1,y1)之间的线段,另一个点P(x,y)与线段具有以下关系.计算(y - y0)(x1 - x0) - (x - x0)(y1 - y0)
如果它小于0,则P位于线段的右侧,如果大于0则位于左侧,如果等于0,则它位于线段上.
这是c#中的代码,我没有检查边缘情况.
public static bool IsInPolygon(Point[] poly, Point point)
{
var coef = poly.Skip(1).Select((p, i) =>
(point.Y - poly[i].Y)*(p.X - poly[i].X)
- (point.X - poly[i].X) * (p.Y - poly[i].Y))
.ToList();
if (coef.Any(p => p == 0))
return true;
for (int i = 1; i < coef.Count(); i++)
{
if (coef[i] * coef[i - 1] < 0)
return false;
}
return true;
}
我用简单的矩形测试它很好:
Point[] pts = new Point[] { new Point { X = 1, Y = 1 },
new Point { X = 1, Y = 3 },
new Point { X = 3, Y = 3 },
new Point { X = 3, Y = 1 } };
IsInPolygon(pts, new Point { X = 2, Y = 2 }); ==> true
IsInPolygon(pts, new Point { X = 1, Y = 2 }); ==> true
IsInPolygon(pts, new Point { X = 0, Y = 2 }); ==> false
关于linq查询的说明:
poly.Skip(1)==>创建一个新的列表,从位置开始1的的poly名单,然后由
(point.Y - poly[i].Y)*(p.X - poly[i].X) - (point.X - poly[i].X) * (p.Y - poly[i].Y)我们要计算(这在引用的段落中提到的方向).类似的例子(与另一个操作):
lst = 2,4,8,12,7,19
lst.Skip(1) ==> 4,8,12,7,19
lst.Skip(1).Select((p,i)=>p-lst[i]) ==> 2,4,4,-5,12
您可以使用光线投射算法.在维基百科页面中详细描述了Point in polygon问题.
它就像计算从外部到该点的光线接触多边形边界的次数一样简单.如果触摸偶数次,则该点在多边形之外.如果触及奇数次,则该点在内部.
要计算光线接触的次数,请检查光线与所有多边形边之间的交点.
小智 7
meowNET anwser 不包括多边形中的多边形顶点，并且精确地指向水平边缘。如果您需要一个精确的“包含”算法：
public static bool IsInPolygon(this Point point, IEnumerable<Point> polygon)
{
bool result = false;
var a = polygon.Last();
foreach (var b in polygon)
{
if ((b.X == point.X) && (b.Y == point.Y))
return true;
if ((b.Y == a.Y) && (point.Y == a.Y) && (a.X <= point.X) && (point.X <= b.X))
return true;
if ((b.Y < point.Y) && (a.Y >= point.Y) || (a.Y < point.Y) && (b.Y >= point.Y))
{
if (b.X + (point.Y - b.Y) / (a.Y - b.Y) * (a.X - b.X) <= point.X)
result = !result;
}
a = b;
}
return result;
}
我的回答取自这里：链接
我将 C 代码转换为 C# 并使其工作
static bool pnpoly(PointD[] poly, PointD pnt )
{
int i, j;
int nvert = poly.Length;
bool c = false;
for (i = 0, j = nvert - 1; i < nvert; j = i++)
{
if (((poly[i].Y > pnt.Y) != (poly[j].Y > pnt.Y)) &&
(pnt.X < (poly[j].X - poly[i].X) * (pnt.Y - poly[i].Y) / (poly[j].Y - poly[i].Y) + poly[i].X))
c = !c;
}
return c;
}
您可以通过以下示例进行测试：
PointD[] pts = new PointD[] { new PointD { X = 1, Y = 1 },
new PointD { X = 1, Y = 2 },
new PointD { X = 2, Y = 2 },
new PointD { X = 2, Y = 3 },
new PointD { X = 3, Y = 3 },
new PointD { X = 3, Y = 1 }};
List<bool> lst = new List<bool>();
lst.Add(pnpoly(pts, new PointD { X = 2, Y = 2 }));
lst.Add(pnpoly(pts, new PointD { X = 2, Y = 1.9 }));
lst.Add(pnpoly(pts, new PointD { X = 2.5, Y = 2.5 }));
lst.Add(pnpoly(pts, new PointD { X = 1.5, Y = 2.5 }));
lst.Add(pnpoly(pts, new PointD { X = 5, Y = 5 }));
我对整数上的 PointInPolygon 函数的业务关键实现（正如 OP 似乎正在使用的那样）针对水平线、垂直线和对角线进行了单元测试，线上的点包含在测试中（函数返回 true）。
这似乎是一个老问题，但之前所有的跟踪示例都有一些缺陷：不考虑水平或垂直多边形线、多边形边界线或边的顺序（顺时针、逆时针）。
以下函数通过了我提出的测试（正方形、菱形、对角线十字，总共 124 次测试），点位于边、顶点以及内部和外部边和顶点上。
该代码对每对连续的多边形坐标执行以下操作：
如有必要，算法可以轻松适应浮点数和双精度数。
作为旁注 - 我想知道在过去近 10 年里创建了多少软件来检查多边形中的点并在某些情况下失败。
public static bool IsPointInPolygon(Point point, IList<Point> polygon)
{
var intersects = new List<int>();
var a = polygon.Last();
foreach (var b in polygon)
{
if (b.X == point.X && b.Y == point.Y)
{
return true;
}
if (b.X == a.X && point.X == a.X && point.X >= Math.Min(a.Y, b.Y) && point.Y <= Math.Max(a.Y, b.Y))
{
return true;
}
if (b.Y == a.Y && point.Y == a.Y && point.X >= Math.Min(a.X, b.X) && point.X <= Math.Max(a.X, b.X))
{
return true;
}
if ((b.Y < point.Y && a.Y >= point.Y) || (a.Y < point.Y && b.Y >= point.Y))
{
var px = (int)(b.X + 1.0 * (point.Y - b.Y) / (a.Y - b.Y) * (a.X - b.X));
intersects.Add(px);
}
a = b;
}
intersects.Sort();
return intersects.IndexOf(point.X) % 2 == 0 || intersects.Count(x => x < point.X) % 2 == 1;
}