C#中如何判断直线是否与多边形相交?
-
12-09-2019 - |
题
我有一个与此非常相似的问题:
我正在寻找一种方法(在 C# 中)来判断一条线是否与任意多边形相交。
我觉得 Chris Marasti-Georg 的算法 非常有帮助,但缺少最重要的方法,即线与线的交点。
有谁知道线相交方法来完成 Chris Marasti-Georg 的代码或有类似的方法吗?
C# 中有这方面的内置代码吗?
此方法适用于通过禁区功能增强的 Bing 地图算法。生成的路径不得穿过禁区(任意多边形)。
解决方案
有用于内置在.NET框架边缘检测没有内置代码。
下面是已经做了你需要的东西(实际的算法是在comp.graphics.algorithms发现在谷歌组)代码(移植到C#):
public static PointF FindLineIntersection(PointF start1, PointF end1, PointF start2, PointF end2)
{
float denom = ((end1.X - start1.X) * (end2.Y - start2.Y)) - ((end1.Y - start1.Y) * (end2.X - start2.X));
// AB & CD are parallel
if (denom == 0)
return PointF.Empty;
float numer = ((start1.Y - start2.Y) * (end2.X - start2.X)) - ((start1.X - start2.X) * (end2.Y - start2.Y));
float r = numer / denom;
float numer2 = ((start1.Y - start2.Y) * (end1.X - start1.X)) - ((start1.X - start2.X) * (end1.Y - start1.Y));
float s = numer2 / denom;
if ((r < 0 || r > 1) || (s < 0 || s > 1))
return PointF.Empty;
// Find intersection point
PointF result = new PointF();
result.X = start1.X + (r * (end1.X - start1.X));
result.Y = start1.Y + (r * (end1.Y - start1.Y));
return result;
}
其他提示
有点偏离主题,但如果该行是 无穷 我认为有一个更简单的解决方案:
如果所有点都位于同一个多边形上,则该线不会穿过多边形 边 的线。
在这两个人的帮助下:
我得到了这个小宝石:
public class PointsAndLines
{
public static bool IsOutside(Point lineP1, Point lineP2, IEnumerable<Point> region)
{
if (region == null || !region.Any()) return true;
var side = GetSide(lineP1, lineP2, region.First());
return
side == 0
? false
: region.All(x => GetSide(lineP1, lineP2, x) == side);
}
public static int GetSide(Point lineP1, Point lineP2, Point queryP)
{
return Math.Sign((lineP2.X - lineP1.X) * (queryP.Y - lineP1.Y) - (lineP2.Y - lineP1.Y) * (queryP.X - lineP1.X));
}
}
这条看起来这将有助于
http://www.codeproject.com/KB/recipes/2dpolyclip.aspx
此代码是二维多边形修剪算法来决定精确其中符合一个多边形边界相交。此代码为完全任意的形状的凹入和凸多边形,并能够处理任何线取向。
不隶属于 StackOverflow