c# - 用C#实现Hoey Shamos算法

Question

好的，我现在从我当前的算法中得到正确的信息！然而，有700000个多边形要检查，这太慢了！上一个问题已修复（我的line2d intersectswith方法不正确）
现在我要确定我的瓶颈了！该算法假设为o（nlog-n），因此应该快得多。我的intersectswith方法看起来不能再快了，但是我会发布它的代码，以防我错了
编辑：添加了IComparable接口
我的线段交点的读取方法。为了可读性，有些代码被省略了。

    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;
            }
        } 
    }


}

我的算法实现大部分，我知道一个列表不是一个算法最快的，但是我需要索引！：

//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，并使它更慢？如果这很重要，我还在索引它呢？
http://www.itu.dk/research/c5/
使用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("");

}

Answer 1

首先，关于线的交点：你不需要实际的交点，只需要知道它们是否相交。请参见http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/以获取一个这样做的算法。
关于List实现：
在使用Lists的实现中，可以在扫描线上调用indexOf来查找nl。这将从头到尾搜索扫掠线。见List(T).IndexOf。如果你要使用BinarySearch方法，这应该会大大加快搜索速度。
List's documentation有一段叫做性能考虑。他们敦促您使用实现IEquatable<T>和IComparable<T>的值类型。所以，您的Line2D应该是struct并实现这些接口。
如果您遵循这个建议，那么从扫描线中检索端点应该是o（log n），这对于您的目的来说已经足够了，并且应该更有效地使用内存。
对于列表，插入和删除都是o（n），因为底层数组需要在内存中移动。aSortedSet具有更快的插入和删除速度，但我不太明白如何在o（log n）中找到项目的邻居。有人吗？（另请参见Why SortedSet<T>.GetViewBetween isn't O(log N)?）
无论如何，c5TreeSet应该能解决这个问题。
我在user guide中查找了indexof和[i]的性能，它们都被列为o（log n）。所以这不应该是问题所在。调用在扫描线上查找邻居的特定方法（即Successor和Predecessor，也就是o（log n））可能会更快，但不超过一个固定因子。
所以

[...]
try 
{
    Line2D above = sweepline.Successor(nl);
    if (above.intersectsLine(nl))
    {
        return false;
    }
}
catch (NoSuchItemException ignore) { }
[...]

我不喜欢他们没有不抛出异常的方法，因为抛出异常非常昂贵。你的扫描线通常会很满，所以我最好的猜测是，找不到一个是很少见的，而调用 Successor是最有效的方法。或者，您可以像现在一样继续调用 IndexOf，但在检索 Count之前检查它是否等于 [index + 1]减1，并防止抛出异常：

[...]
int index = sweepline.IndexOf(nl);
if( index < sweepline.Count-1 )
{
    Line2D above = sweepline[index + 1];
    if (above.intersectsLine(nl))
    {
        return false;
    }
}
[...]

manual的第二章描述了c5集合的相等和比较。在这里，至少你必须实现 IEquatable<T>和 IComparable<T>！
还有一个想法：你报告给算法输入了700000行。你能不能先从计时开始，比如1000，2500，5000，10000条线，看看算法在不相交的情况下是如何缩放的？
关于如何比较扫掠线上的线：
您需要在扫描线树集上为line2ds找到某种自然排序，因为compare to方法要求您将一个line2d与另一个进行比较。其中一个line2ds已经位于sweepline treeset中，另一个刚刚遇到并正在添加。
你的清扫线自下而上，我想：

List<AlgEvent> SortedList = events.OrderBy(o => o.getY()).ToList();

假设s1段在事件1中被添加到treeset中，我们希望将它与s2进行比较，s2现在正在事件2中被添加。
线段可能会在某个点相交，这会改变顺序，但是算法会在插入线段后立即在上面和下面的检查中检查。想想看，这也许更适合称为左右支票。
无论如何..因此，最简单的方法是比较两条线段的下端点。左边比较小，右边比较大。但是，我们需要查看扫描线位置的顺序，从那时起，它们可能已经改变了位置，如图中所示。
所以我们需要比较s2的下端点和s1上的红点，看看它是在那个点的左边还是右边。它位于左侧，因此认为s2小于s1。
通常比这个简单：如果所有s1都位于s2的底端点左侧，则s1小于s2。如果所有s1都位于s2底部端点的右侧，则s1大于s2。
我想你在找一个更安全的界面：

public class Line2D : IComparable<Line2D>

假设两个属性 BottomY（两个y值中的最低值）和 BottomX（最低端点的x值），这是一个经过测试的尝试：

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) );

}