如何判断一条线是否与 C# 中的多边形相交？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1119451/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to tell if a line intersects a polygon in C#?
提问by svanerik
I have a question very similar to this:
我有一个与此非常相似的问题：
I am searching for a method (in C#) that tells if a line is intersecting an arbitrary polygon.
我正在寻找一种方法（在 C# 中）可以判断一条线是否与任意多边形相交。
I think the algorithm by Chris Marasti-Georgwas very helpful, but missing the most important method, i.e. line to line intersection.
我认为Chris Marasti-Georg的算法非常有帮助，但缺少最重要的方法，即线与线相交。
Does anyone know of a line intersection method to complete Chris Marasti-Georg's code or have anything similar?
有没有人知道完成 Chris Marasti-Georg 代码的线交叉方法或有类似的方法？
Is there a built-in code for this in C#?
在 C# 中是否有内置代码？
This method is for use with the Bing Maps algorithm enhanced with a forbidden area feature. The resulting path must not pass through the forbidden area (the arbitrary polygon).
此方法用于通过禁用区域功能增强的 Bing 地图算法。生成的路径不得穿过禁区（任意多边形）。
采纳答案by Mike J
There is no builtin code for edge detection built into the .NET framework.
.NET 框架中没有用于边缘检测的内置代码。
Here's code (ported to C#) that does what you need (the actual algorithm is found at comp.graphics.algorithms on Google groups) :
这是可以满足您需要的代码（移植到 C#）（实际算法可在 Google 群组的 comp.graphics.algorithms 中找到）：
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;
}
回答by Lou Franco
This article looks like it will help
这篇文章看起来会有所帮助
http://www.codeproject.com/KB/recipes/2dpolyclip.aspx
http://www.codeproject.com/KB/recipes/2dpolyclip.aspx
This code is a two-dimensional polygon-clipping algorithm that determines precisely where a line intersects with a polygon border. This code works for both concave and convex polygons of completely arbitrary shape and is able to handle any line orientation.
此代码是一种二维多边形裁剪算法，可精确确定线与多边形边界相交的位置。此代码适用于完全任意形状的凹面和凸面多边形，并且能够处理任何线方向。
回答by D.Rosado
To detect collisions between polygons in our silverlight map project, we're using clipper library:
为了检测 Silverlight 地图项目中多边形之间的碰撞，我们使用了 Clipper 库：
Free for commercial use, small size, great performance and very easy to use.
免费用于商业用途，体积小，性能好，非常易于使用。
回答by jdpilgrim
Slightly off topic, but if the line is infiniteI think there's a much simpler solution:
稍微偏离主题，但如果这条线是无限的，我认为有一个更简单的解决方案：
The line does not go through the polygon if all the point lie on the same sideof the line.
如果所有点都位于线的同一侧，则线不会穿过多边形。
With help from these two:
在这两个人的帮助下：
- Using linq or otherwise, how do check if all list items have the same value and return it, or return an “otherValue” if they don't?
- Determine which side of a line a point lies
I got this little gem:
我得到了这个小宝石：
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));
}
}
