好的，我现在正在从我的当前算法中获取正确信息！然而，有700,000个多边形需要检查，速度太慢了！先前的问题已经解决（我的Line2D intersectsWith方法不正确）。
现在问题在于确定我的瓶颈在哪里！这个算法应该是O(nlog-n)，所以应该更快。我的intersectsWith方法看起来无法更快，但是我会发布它的代码，以防我错了。
编辑：添加了IComparable接口
我的方法用于读取线段相交。一些代码已被省略以提高可读性。
现在问题在于确定我的瓶颈在哪里！这个算法应该是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;
}
}
}
}
我意识到在算法实现中，List 不是最快的算法，但我需要索引！
//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("");
}
