用于检测自交的多边形实施蛮力算法 [英] Implementing a brute force algorithm for detecting a self-intersecting polygon
问题描述
我最初实施的霍伊 - Shamos算法，但它是为未来的可维护性太复杂（我在这没有发言权），它没有正确的报告，所以一个优化的蛮力算法就是我要去。使用
I initially implemented the Hoey-Shamos algorithm, however it is too complex for future maintainability (I have no say in this), and it wasn't reporting correctly, so an optimized brute force algorithm is what I'm going to use.
我的问题是：如何优化此代码是可用的。
My question is: How can I optimize this code to be usable?
既然这样，我的代码包含嵌套循环，迭代相同的列表两次。
As it stands, my code contains a nested for loop, iterating the same list twice.
编辑：原来行到HashSet的，并使用了两个foreach循环......剃光约45秒关闭扫描10,000。它仍然是不够的。
Turned lines into a HashSet and used two foreach loops... shaved about 45 seconds off scanning 10,000. It's still not enough.
foreach (Line2D g in lines)
{
foreach (Line2D h in lines)
{
if (g.intersectsLine(h))
{
return false;
}
}
} // end 'lines' for each loop
//结束线
如果我强迫我的intersectsLine（）方法返回false（用于测试目的），它仍然需要8秒，扫描10000条记录（我有70万条记录）。这是太长了，所以我需要优化这段代码。
If I force my "intersectsLine()" method to return false (for testing purposes) it still takes 8 seconds to scan 10,000 records (I have 700,000 records). This is too long, so I need to optimize this piece of code.
我想它已经相比，所有其他行后从列表中删除线，但是有一个精度的问题（不知道为什么）和速度的提高几乎没有明显的。
I tried removing lines from the List after it's been compared to all the other lines, however there's an accuracy issue (no idea why) and the speed increase is barely noticeable.
下面是我的intersectsLine方法。我发现了一个替代方法 rel=\"nofollow\">但它看起来像这将会是所有的方法调用和诸如此类的东西慢。计算坡度似乎并没有对我来说，它会花费太多的计算（纠正我，如果我错了？）
Here is my intersectsLine method. I found an alternate approach here but it looks like it'd be slower with all the method calls and whatnot. Calculating the slope doesn't seem to me like it'd take too much computing (Correct me if I'm wrong?)
public bool intersectsLine(Line2D comparedLine)
{
//tweakLine(comparedLine);
if (this.Equals(comparedLine) ||
P2.Equals(comparedLine.P1) ||
P1.Equals(comparedLine.P2))
{
return false;
}
double firstLineSlopeX, firstLineSlopeY, secondLineSlopeX, secondLineSlopeY;
firstLineSlopeX = X2 - X1;
firstLineSlopeY = Y2 - Y1;
secondLineSlopeX = comparedLine.X2 - comparedLine.X1;
secondLineSlopeY = comparedLine.Y2 - comparedLine.Y1;
double s, t;
s = (-firstLineSlopeY * (X1 - comparedLine.X1) + firstLineSlopeX * (Y1 - comparedLine.Y1)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
t = (secondLineSlopeX * (Y1 - comparedLine.Y1) - secondLineSlopeY * (X1 - comparedLine.X1)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
{
//console.WriteLine("s = {0}, t = {1}", s, t);
//console.WriteLine("this: " + this);
//console.WriteLine("other: " + comparedLine);
return true;
}
return false; // No collision */
}
编辑：的主要瓶颈是大多边形！我排除的多边形运行超过100行，它运行的所有700,000+多边形5:10。这是在可接受的范围内！肯定有一个方法，如果一个多边形是值得运行此代码之前计算？我有机会获得XMIN，喷射Xmax，YMIN与YMAX特性是否有帮助？
The major bottleneck is the big polygons! I excluded running polygons with more than 100 lines, and it ran all 700,000+ polygons in 5:10. Which is in the acceptable range! Surely there's a way to see if a polygon is worth calculating before running this code? I have access to the XMin, Xmax, YMin, and YMax properties if that helps?
冉另一个测试，每下1000行限制多边形。它花了一点了一个多小时。
Ran another test, limiting polygons to under 1000 lines each. It took a little over an hour.
我删除了所有限制的多边形，而且它已经运行了36个小时，现在......还没有结果。
I removed all limiting of polygons, and it's been running for 36 hours now... still no results.
一对夫妇的想法，我有：
- 当我生成我行的HashSet ，还有一个HashSet的/目录有交点的候选人。我只想补充线到此列表中，如果有相交的机会。但我怎么消除/添加的可能性？如果只有三行可能可能与其他人相交，我对3进行比较，4000线，而不是单单4000这可以使一个巨大的差异。
-When I generate my lines hashset, have another hashset/List that has candidates for intersection. I would only add lines to this list if there's a chance for intersection. But how do I eliminate/add possibilities? If there's only three lines that could possibly intersect with others, I'd be comparing 4000 lines against 3 instead of 4000. This alone could make a HUGE difference.
- 如果相同点发生了两次，除了第一个和最后一个点，省略运行嵌套循环。
-If the same point occurs twice, except the first and last point, omit running the nested for loop.
编辑：
有关的多边形信息：
700 000
Information about the polygons: 700,000 total
有四千多多边形与1000点以上。
There is over four thousand polygons with 1,000 or more points
有2多边形与70000分以上。
There is 2 polygons with 70,000 or more points
我认为这是可能的一点创造力。得到这个下来到十五分钟左右
I think it's possible to get this down to fifteen or so minutes with a bit of creativity.
推荐答案
您当前的蛮力算法是O（n ^ 2）。对于只是你的2个7行多边形几乎10亿次运算的一些因素，更不用说700,000其他多边形的说。显然，没有单纯的代码优化量将是不够的，所以你需要某种算法优化，能够比为O（n ^ 2）不至于过分复杂。
Your current Brute-Force algorithm is O(n^2). For just your two 70,000 line polygons that's some factor of almost 10 Billion operations, to say nothing of the 700,000 other polygons. Obviously, no amount of mere code optimization is going to be enough, so you need some kind algorithmic optimization that can lower that O(n^2) without being unduly complicated.
在为O（n ^ 2）来自于蛮力算法嵌套循环，即分别由 N 。所以我们需要找到一些方法来订货或重新排序行内部列表来核对，这样只有完整列表的一部分外行需要进行扫描。
The O(n^2) comes from the nested loops in the brute-force algorithm that are each bounded by n, making it O(n*n). The simplest way to improve this would be to find some way to reduce the inner loop so that it is not bound by or dependent on n. So what we need to find is some way to order or re-order the inner list of lines to check the outer line against so that only a part of the full list needs to be scanned.
这我正在的方法利用这样的事实，如果两个线段相交，则它们的X值的范围必须彼此重叠的优势。你要知道，这并不意味着他们的不的相交，但如果它们的X-范围不重叠，那么他们的无法的是相交所以世界上没有其他需要检查他们反对彼此。 （这是Y值的真正的范围还，但你只能利用在一维时间）。
The approach that I am taking takes advantage of the fact that if two line segments intersect, then the range of their X values must overlap each other. Mind you, this doesn't mean that they do intersect, but if their X ranges don't overlap, then they cannot be intersecting so theres no need to check them against each other. (this is true of the Y value ranges also, but you can only leverage one dimension at a time).
这种方法的好处是，那些X范围可以是用于排序可以反过来被用作起始的线的端点和停止点哪些行要检查的交叉口。
The advantage of this approach is that these X ranges can be used to order the endpoints of the lines which can in turn be used as the starting and stopping points for which lines to check against for intersection.
所以具体是什么，我们要做的是定义一个自定义类（ endpointEntry ）表示高或直线的两个点低的X值。这些端点都放进同一个目录结构，然后根据他们的X值排序。
So specifically what we do is to define a custom class (endpointEntry) that represents the High or Low X values of the line's two points. These endpoints are all put into the same List structure and then sorted based on their X values.
然后，我们实现一个外环，我们扫描整个列表，就像在蛮力算法。但是我们的内循环是相当不同的。而不是重新在扫描线的整个列表检查路口，我们相当的启动的扫描下从外环的线的高X值端点排序端点列表，并结束它，当我们通过下面的同一线路的低X值端点。通过这种方式，我们只检查其x值的范围重叠外循环的路线行
Then we implement an outer loop where we scan the entire list just as in the brute-force algorithm. However our inner loop is considerably different. Instead of re-scanning the entire list for lines to check for intersection, we rather start scanning down the sorted endpoint list from the high X value endpoint of the outer loop's line and end it when we pass below that same line's low X value endpoint. In this way, we only check the lines whose range of X values overlap the outer loop's line.
确定，这里是一个C＃类证明我的方法：
OK, here's a c# class demonstrating my approach:
class CheckPolygon2
{
// internal supporting classes
class endpointEntry
{
public double XValue;
public bool isHi;
public Line2D line;
public double hi;
public double lo;
public endpointEntry fLink;
public endpointEntry bLink;
}
class endpointSorter : IComparer<endpointEntry>
{
public int Compare(endpointEntry c1, endpointEntry c2)
{
// sort values on XValue, descending
if (c1.XValue > c2.XValue) { return -1; }
else if (c1.XValue < c2.XValue) { return 1; }
else // must be equal, make sure hi's sort before lo's
if (c1.isHi && !c2.isHi) { return -1; }
else if (!c1.isHi && c2.isHi) { return 1; }
else { return 0; }
}
}
public bool CheckForCrossing(List<Line2D> lines)
{
List<endpointEntry> pts = new List<endpointEntry>(2 * lines.Count);
// Make endpoint objects from the lines so that we can sort all of the
// lines endpoints.
foreach (Line2D lin in lines)
{
// make the endpoint objects for this line
endpointEntry hi, lo;
if (lin.P1.X < lin.P2.X)
{
hi = new endpointEntry() { XValue = lin.P2.X, isHi = true, line = lin, hi = lin.P2.X, lo = lin.P1.X };
lo = new endpointEntry() { XValue = lin.P1.X, isHi = false, line = lin, hi = lin.P1.X, lo = lin.P2.X };
}
else
{
hi = new endpointEntry() { XValue = lin.P1.X, isHi = true, line = lin, hi = lin.P1.X, lo = lin.P2.X };
lo = new endpointEntry() { XValue = lin.P2.X, isHi = false, line = lin, hi = lin.P2.X, lo = lin.P1.X };
}
// add them to the sort-list
pts.Add(hi);
pts.Add(lo);
}
// sort the list
pts.Sort(new endpointSorter());
// sort the endpoint forward and backward links
endpointEntry prev = null;
foreach (endpointEntry pt in pts)
{
if (prev != null)
{
pt.bLink = prev;
prev.fLink = pt;
}
prev = pt;
}
// NOW, we are ready to look for intersecting lines
foreach (endpointEntry pt in pts)
{
// for every Hi endpoint ...
if (pt.isHi)
{
// check every other line whose X-range is either wholly
// contained within our own, or that overlaps the high
// part of ours. The other two cases of overlap (overlaps
// our low end, or wholly contains us) is covered by hi
// points above that scan down to check us.
// scan down for each lo-endpoint below us checking each's
// line for intersection until we pass our own lo-X value
for (endpointEntry pLo = pt.fLink; (pLo != null) && (pLo.XValue >= pt.lo); pLo = pLo.fLink)
{
// is this a lo-endpoint?
if (!pLo.isHi)
{
// check its line for intersection
if (pt.line.intersectsLine(pLo.line))
return true;
}
}
}
}
return false;
}
}
我不能肯定什么这真正执行的复杂性算法，但我怀疑对大多数非病理性的多边形将接近O（N * SQRT（N））应该是足够快的。
I am not certain what the true execution complexity of this algorithm is, but I suspect that for most non-pathological polygons it will be close to O(n*SQRT(n)) which should be fast enough.
内环简单的扫描以相同的排序顺序为外循环端点列表。但它将<青霉>启动的从那里从那里外环目前是在列表中（这是一些直线的HIX点），以及外环将只扫描直到端点值扫描低于相应同一行的LOX值。
The Inner Loop simply scans the endPoints list in the same sorted order as the outer loop. But it will start scanning from where the outer loop from where the outer loop currently is in the list (which is the hiX point of some line), and will only scan until the endPoint values drop below the corresponding loX value of that same line.
什么是棘手的这里，是，这不能与枚举（即的foreach（来完成。在PTS） 外循环），因为没有办法来枚举列表的子表，也开始基于另一个枚举当前位置的枚举。所以不是我所做的是使用正向和反向链接（弗林克和闪烁）特性使该保留列表的排序顺序一个双向链表结构，但是，我可以增量不枚举列表扫描：
What's tricky here, is that this cannot be done with an Enumerator (the foreach(..in pts) of the outer loop) because there's no way to enumerate a sublist of a list, nor to start the enumeration based on another enumerations current position. So instead what I did was to use the Forward and Backward Links (fLink and bLink) properties to make a doubly-linked list structure that retains the sorted order of the list, but that I can incrementally scan without enumerating the list:
for (endpointEntry pLo = pt.fLink; (pLo != null) && (pLo.XValue >= pt.lo); pLo = pLo.fLink)
打破下来，旧式的为循环说明有三个部分：初始化，条件和增量递减。初始化表达式， endpointEntry巴解组织= pt.fLink; 初始化 PLO 与当前点列表中的前向链路。即，在列表中的下一个点，按降序排序顺序
Breaking this down, the old-style for loop specifier has three parts: initialization, condition, and increment-decrement. The initialization expression, endpointEntry pLo = pt.fLink; initializes pLo with the forward Link of the current point in the list. That is, the next point in the list, in descending sorted order.
接着的内循环体被执行。然后递增递减巴解组织= pLo.fLink 被应用，它只是设置了内部循环的当前点（ PLO ）使用它下一个更低的点是前向链路（ pLo.fLink ），从而推动循环。
Then the body of the inner loop gets executed. Then the increment-decrement pLo = pLo.fLink gets applied, which simply sets the inner loop's current point (pLo) to the next lower point using it's forward-link (pLo.fLink), thus advancing the loop.
最后，它测试循环条件后循环（巴解组织！= NULL）及和放大器; （pLo.XValue> = pt.lo）哪些循环，只要新一点不为空（这将意味着我们在列表的末尾），因此只要新点的 XValue 仍大于或等于外环的当前点低X值。这第二个条件保证了内部循环只着眼于重叠外循环的终点行线。
Finally, it loops after testing the loop condition (pLo != null) && (pLo.XValue >= pt.lo) which loops so long as the new point isn't null (which would mean that we were at the end of the list) and so long as the new point's XValue is still greater than or equal to the low X value of the outer loop's current point. This second condition insures that the inner loop only looks at lines that are overlapping the line of the outer loop's endpoint.
什么为更清楚我现在是，我可能已经解决这个整个弗林克一眨不眨笨拙通过将端点列表作为数组，而不是得到：
What is clearer to me now, is that I probably could have gotten around this whole fLink-bLink clumsiness by treating the endPoints List as an array instead:
- 外环通过降序排列，使用索引的迭代器（列表
I），而不是的foreach枚举 - （A）内蒙古河套通过列表中，使用的是第二个迭代器（
Ĵ），从I键，当它通过下面结束pt.Lo。
<李>填写了端点
- Fill up the list with endPoints
- Sort the List by XValue
- Outer Loop through the list in descending order, using an index iterator (
i), instead of aforeachenumerator - (A) Inner Loop through the list, using a second iterator (
j), starting atiand ending when it passed belowpt.Lo.
这是我觉得会简单得多。我可以张贴简化版本这样，如果你想要的。
That I think would be much simpler. I can post a simplified version like that, if you want.
这篇关于用于检测自交的多边形实施蛮力算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
