Implementieren des Hoey Shamos-Algorithmus mit C #
Okay, ich erhalte jetzt die korrekten Informationen von meinem aktuellen Algorithmus! Mit 700.000 zu überprüfenden Polygonen ist es jedoch viel zu langsam! Das vorherige Problem wurde behoben (Meine Line2D schneidet mit der falschen Methode)
Jetzt geht es darum, meinen Engpass zu identifizieren! Es wird angenommen, dass dieser Algorithmus O (nlog-n) ist, daher sollte er viel schneller sein. Meine intersectsWith-Methode sieht so aus, als könnte sie nicht schneller werden, ich werde jedoch den Code veröffentlichen, falls ich mich irre
BEARBEITEN: IComparable Schnittstelle hinzugefügt
Meine Methode zum Lesen von Liniensegmentschnittpunkten. Einige Codes wurden aus Gründen der Lesbarkeit weggelassen.
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;
}
}
}
}
Der Großteil meiner Algorithmusimplementierung besteht darin, dass eine Liste nicht die schnellste für einen Algorithmus ist, ich jedoch eine Indizierung benötige:
//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;
==========================================
UPDATE: 12. September: Das TreeSet von C5 implementiert, IComparable für meine Klassen implementiert und es noch weiter verlangsamt? Ich indiziere es immer noch, wenn das wichtig ist?
http://www.itu.dk/research/c5/
Code mit 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("");
}