用 C# 实现 Hoey Shamos 算法 [英] Implementing Hoey Shamos algorithm with C#
问题描述
好的，我现在从我当前的算法中获得了正确的信息！但是，要检查 700,000 个多边形，实在是太慢了！上一个问题已修复(我的 Line2D intersectsWith 方法不正确)
Okay, I am now getting the correct information from my current algorithm! However, with 700,000 polygons to check, it's just way too slow! The previous issue is fixed (My Line2D intersectsWith method was incorrect)
现在是确定我的瓶颈的问题！这个算法假设是 O(nlog-n) 所以它应该快得多.我的 intersectsWith 方法看起来不能更快了，但是我会发布它的代码，以防我错了
Now it's a matter of identifying my bottleneck! This algorithm is suppose to be O(nlog-n) so it should be much quicker. My intersectsWith method looks like it can't get any faster, however I will post its code, in case I'm wrong
添加了 IComparable 接口
我的读取线段交点的方法.为了便于阅读，省略了一些代码.
My method for reading line segment intersections. Some code has been omitted for readability.
public class Line2D : IComparable
{
public Line2D(XYPoints p1, XYPoints p2)
{
}
public bool intersectsLine(Line2D comparedLine)
{
if ((X2 == comparedLine.X1) && (Y2 == comparedLine.Y1)) return false;
if ((X1 == comparedLine.X2) && (Y1 == comparedLine.Y2)) return false;
if (X2 == comparedLine.X1 && Y2 == comparedLine.Y1)
{
return false;
}
if (X1 == comparedLine.X2 && Y1 == comparedLine.Y2)
{
return false;
}
double firstLineSlopeX, firstLineSlopeY, secondLineSlopeX, secondLineSlopeY;
firstLineSlopeX = X2 - X1;
firstLineSlopeY = Y2 - Y1;
secondLineSlopeX = comparedLine.getX2() - comparedLine.getX1();
secondLineSlopeY = comparedLine.getY2() - comparedLine.getY1();
double s, t;
s = (-firstLineSlopeY * (X1 - comparedLine.getX1()) + firstLineSlopeX * (getY1() - comparedLine.getY1())) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
t = (secondLineSlopeX * (getY1() - comparedLine.getY1()) - secondLineSlopeY * (getX1() - comparedLine.getX1())) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
{
return true;
}
return false; // No collision
}
int IComparable.CompareTo(object obj)
{
//return Y1.GetHashCode();
Line2D o1 = this;
Line2D o2 = (Line2D)obj;
if (o1.getY1() < o2.getY1())
{
return -1;
}
else if (o1.getY1() > o2.getY2())
{
return 1;
}
else
{
if (o1.getY2() < o2.getY2())
{
return -1;
}
else if (o1.getY2() > o2.getY2())
{
return 1;
}
else
{
return 0;
}
}
}
}
在我的大部分算法实现中，我意识到 List 并不是算法最快的，但是我需要索引！:
The bulk of my algorithm implementation, I realize a List isn't the fastest for an algorithm, however I need indexing!:
//Create a new list, sort by Y values.
List<AlgEvent> SortedList = events.OrderBy(o => o.getY()).ToList();
List<Line2D> sweepline = new List<Line2D>();
for (var g = 0; g < SortedList.Count; g++)
{
if (SortedList[g].isStart)
{
Line2D nl = SortedList[g].line;
Line2D above;
/* Start generating above */
try
{
//grab index in sweepline
int index = sweepline.IndexOf(nl);
//add 1 to get above line
if (index == -1)
{
above = null;
}
else
{
above = sweepline[index + 1];
}
}
catch (ArgumentOutOfRangeException)
{
above = null;
}
/* End generating above */
if (above != null)
{
if (above.intersectsLine(nl))
{
return true;
}
}
Line2D below;
/* Start generating below */
try
{
//grab index in sweepline
int index = sweepline.IndexOf(nl);
//add 1 to get above line
below = sweepline[index - 1];
}
catch (ArgumentOutOfRangeException)
{
below = null;
}
/* End generating below */
if (below != null)
{
if (below.intersectsLine(nl))
{
return true;
}
}
sweepline.Add(nl);
sweepline = sweepline.OrderBy(o => o.getY1()).ToList();
}
else
{
Line2D nl = SortedList[g].line;
Line2D above;
Line2D below;
/* Start generating above */
try
{
//grab index in sweepline
int index = sweepline.IndexOf(nl);
Console.Out.WriteLine("index:" + index);
//add 1 to get above line
above = sweepline[index + 1];
}
catch (ArgumentOutOfRangeException)
{
above = null;
}
/* End generating above */
/* Start generating below */
try
{
//grab index in sweepline
int index = sweepline.IndexOf(nl);
//add 1 to get above line
below = sweepline[index - 1];
}
catch (ArgumentOutOfRangeException)
{
below = null;
}
/* End generating below */
sweepline = sweepline.OrderBy(o => o.getY1()).ToList();
sweepline.Remove(nl);
if (above != null && below != null)
{
if (above.intersectsLine(below))
{
return true;
}
}
}
Console.WriteLine("");
}
} // end numofparts for-loop
return false;
============================================
============================================
更新:9 月 12 日:从 C5 中实现了 TreeSet，在我的类中实现了 IComparable，并进一步减慢了速度?如果这很重要，我还在索引它吗?
UPDATE: September 12th: Implemented the TreeSet from C5, implemented IComparable to my classes, and slowed it down even more? I am still indexing it if that matters?
http://www.itu.dk/research/c5/
使用 TreeSet 的代码:
Code using TreeSet:
TreeSet<Line2D> sweepline = new TreeSet<Line2D>();
for (var g = 0; g < SortedList.Count; g++)
{
if (SortedList[g].isStart)
{
Line2D nl = SortedList[g].line;
Line2D above;
/* Start generating above */
try
{
//grab index in sweepline
int index = sweepline.IndexOf(nl);
//add 1 to get above line
above = sweepline[index + 1];
}
catch (IndexOutOfRangeException)
{
above = null;
}
/* End generating above */
if (above != null)
{
if (above.intersectsLine(nl))
{
return false;
}
}
Line2D below;
/* Start generating below */
try
{
//grab index in sweepline
int index = sweepline.IndexOf(nl);
//add 1 to get above line
below = sweepline[index - 1];
}
catch (IndexOutOfRangeException)
{
below = null;
}
/* End generating below */
if (below != null)
{
if (below.intersectsLine(nl))
{
return false;
}
}
sweepline.Add(nl);
//sweepline = sweepline.OrderBy(o => o.getY1()).ToList();
}
else
{
Line2D nl = SortedList[g].line;
Line2D above;
Line2D below;
/* Start generating above */
try
{
//grab index in sweepline
int index = sweepline.IndexOf(nl);
//Console.Out.WriteLine("index:" + index);
//add 1 to get above line
above = sweepline[index + 1];
}
catch (IndexOutOfRangeException)
{
above = null;
}
/* End generating above */
/* Start generating below */
try
{
//grab index in sweepline
int index = sweepline.IndexOf(nl);
//add 1 to get above line
below = sweepline[index - 1];
}
catch (IndexOutOfRangeException)
{
below = null;
}
/* End generating below */
//sweepline = sweepline.OrderBy(o => o.getY1()).ToList();
sweepline.Remove(nl);
if (above != null && below != null)
{
if (above.intersectsLine(below))
{
return false;
}
}
}
//Console.WriteLine("");
}
推荐答案
首先，关于线的交点:你不需要实际的交点，只需要知道它们是否相交.请参阅 http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ 用于执行此操作的算法.
First, regarding the line intersection: you do not need the actual point of intersection, only to know if they intersect. See http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ for an algorithm that does just that.
关于List 实现:
在使用 List 的实现中，您在扫描线上调用 indexOf 以查找 nl.这会从头到尾搜索扫掠线.请参阅List(T).IndexOf.如果您要使用 BinarySearch方法，这应该会大大加快搜索速度.
In your implementation using Lists, you call indexOf on the sweepline to find nl. This searches the sweepline from start to end. See List(T).IndexOf. If you were to use the BinarySearch method, that ought to speed up the search considerably.
List 的文档 有一段称为性能注意事项.他们敦促您使用实现 IEquatable 和 IComparable 的值类型.所以，你的 Line2D 应该是一个 struct 并实现这些接口.
List's documentation has a paragraph called performance considerations. They urge you to use a value type that implements IEquatable<T> and IComparable<T>. So, your Line2D should probably be a struct and implement these interfaces.
如果您遵循该建议，从扫描线检索端点应该是 O(log n)，这足以满足您的目的，并且应该更有效地使用内存.
If you follow that advice, retrieval of the endpoint from the sweepline should be O(log n), which is sufficient for your purpose, and memory should be used more efficiently.
List 的插入和删除是 O(n)，导致底层数组需要在内存中移动.SortedSet 具有更快的插入和删除速度，但我不太明白如何在 O(log n) 中找到项目的邻居.任何人?(另请参见 为什么 SortedSet
Insertion and removal are O(n) for Lists, cause the underlying array needs to be moved around in memory. A SortedSet has faster insertion and removal, but I don't quite see how to find an item's neighbors in O(log n) there. Anyone? (See also Why SortedSet<T>.GetViewBetween isn't O(log N)?)
无论如何，C5 TreeSet 应该可以解决这个问题.
Anyways, the C5 TreeSet should solve this.
我在用户指南 并且它们都被列为 O(log n).所以这不应该是问题.可能还是有点快，但也不过是一个固定因素，在sweepline上调用寻找邻居的具体方法，即继任者和Predecessor，也是O(log n).
I looked up the performance of IndexOf and [i] in the user guide and they're both listed as O(log n). So that is not supposed to be the issue. It's still probably somewhat faster, but no more than a fixed factor, to call the specific methods for finding the neighbors on the sweepline, i.e. Successor and Predecessor, which are also O(log n).
所以
[...]
try
{
Line2D above = sweepline.Successor(nl);
if (above.intersectsLine(nl))
{
return false;
}
}
catch (NoSuchItemException ignore) { }
[...]
我不喜欢他们没有不抛出异常的方法，因为抛出异常非常昂贵.您的扫描线通常会很满，所以我最好的猜测是找不到一个的情况很少见，而调用 Successor 是最有效的方法.或者，您可以像现在一样继续调用 IndexOf，但在检索 [index + 1] 之前检查它是否等于 Count 减一，并且完全防止抛出异常:
I don't like that they do not have a method that doesn't throw the exception, since throwing exceptions is very expensive. Your sweep line will be pretty full generally so my best guess is that failure to find one will be rare and calling Successor is the most efficient way. Alternatively, you could keep calling IndexOf like you do now, but check if it equals Count minus one before retrieving [index + 1], and prevent the exception from being thrown at all:
[...]
int index = sweepline.IndexOf(nl);
if( index < sweepline.Count-1 )
{
Line2D above = sweepline[index + 1];
if (above.intersectsLine(nl))
{
return false;
}
}
[...]
手册的第二章描述 C5 集合的相等性和比较.在这里，至少你也必须实现 IEquatable 和 IComparable!
Chapter two of the manual describes equality and comparison for C5 collections. Here, too, at the very least you must implement IEquatable<T> and IComparable<T>!
还有一个想法:你报告给算法提供了 700000 行.您能否从计时开始，例如 1000、2500、5000、10000 行，然后看看算法如何针对它们不相交的情况进行缩放?
One more thought: you report feeding the algorithm 700000 lines. Could you start with timing for example 1000, 2500, 5000, 10000 lines and seeing how the algorithm scales for cases where they do not intersect?
关于如何比较扫描线上的线:
On how to compare the lines on the sweepline:
您需要为 Sweepline TreeSet 上的 Line2D 找到某种自然排序，因为 CompareTo 方法要求您将一个 Line2D 与另一个进行比较.其中一个 Line2D 已经位于 Sweepline TreeSet 中，另一个刚刚遇到并正在添加.
You need to find some sort of natural ordering for the Line2Ds on the Sweepline TreeSet, since the CompareTo method asks you to compare one Line2D to another. One of the Line2Ds already sits in the Sweepline TreeSet, the other has just been encountered and is being added.
我认为您的扫描线是从下到上的:
Your sweepline runs from bottom to top, I think:
List<AlgEvent> SortedList = events.OrderBy(o => o.getY()).ToList();
假设段 S1 在事件 1 中添加到 TreeSet，我们希望将其与 S2 进行比较，后者正在事件 2 中添加，现在.
So let's say segment S1 got added to the TreeSet at event 1, and we wish to compare it to S2, which is being added at event 2, right now.
线段可能在某个点相交，这会改变顺序，但算法会在插入它们后立即检查这一点，在上面和下面的检查中.想一想，这也许更好地称为左右检查.
The line segments could possibly intersect at some point, which would change the ordering, but the algorithm will check for this right after inserting them, in the above and below checks. Which would perhaps better be called the left and right checks, come to think of it.
无论如何......所以最简单的方法是比较两条线段的底部端点.左边较小，右边较大.但是，我们需要查看扫描线位置的排序，从那以后它们可能已经改变了位置，如图所示.
Anyways.. so the easiest would be to compare the bottom endpoints of both line segments. To the left is smaller, to the right is bigger. However, we need to look at the ordering at the position of the sweepline and they may have changed positions since then, like in the picture.
因此我们需要将 S2 的底部端点与 S1 上的红点进行比较，看看它位于该点的左侧还是右侧.它位于左侧，因此 S2 被认为小于 S1.
So we need to compare the bottom endpoint of S2 to the red point on S1, and see if it lies to the left or to the right of that point. It lies to the left so S2 is considered smaller than S1.
通常比这更简单:如果所有 S1 都位于 S2 底部端点的左侧，则 S1 小于 S2.如果所有 S1 都位于 S2 下端点的右侧，则 S1 大于 S2.
Usually it's simpler than this: If all of S1 lies to the left of S2's bottom endpoint, S1 is smaller than S2. If all of S1 lies to the right of S2's bottom endpoint, S1 is larger than S2.
我认为您正在寻找更安全的界面版本:
I think you're looking for the typesafer version of the interface:
public class Line2D : IComparable<Line2D>
假设有两个属性 BottomY(两个 Y 值中最低的一个)和 BottomX(最低端点的 X 值)，经过某种程度的测试:
Assuming two properties BottomY, the lowest of the two Y values, and BottomX, the X value of the lowest endpoint, a somewhat tested attempt:
int IComparable<Line2D>.CompareTo(Line2D other)
{
if( BottomY < other.BottomY )
{
return -other.CompareTo(this);
}
// we're the segment being added to the sweepline
if( BottomX >= other.X1 && BottomX >= other.X2 )
{
return 1;
}
if( BottomX <= other.X1 && BottomX <= other.X2 )
{
return -1;
}
if( other.Y2 == other.Y1 )
{
// Scary edge case: horizontal line that we intersect with. Return 0?
return 0;
}
// calculate the X coordinate of the intersection of the other segment
// with the sweepline
// double redX = other.X1 +
// (BottomY - other.Y1) * (other.X2 - other.X1) / (other.Y2 - other.Y1);
//
// return BottomX.CompareTo(redX);
// But more efficient, and more along the lines of the orientation comparison:
return Comparer<Double>.Default.Compare(
(BottomX - other.X1) * (other.Y2 - other.Y1),
(BottomY - other.Y1) * (other.X2 - other.X1) );
}
这篇关于用 C# 实现 Hoey Shamos 算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
