Реализация алгоритма Hoey Shamos с C #
Хорошо, теперь я получаю правильную информацию из моего текущего алгоритма! Однако, с проверкой 700 000 полигонов,просто слишком медленно! Предыдущая проблема исправлена (My 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 = 0 && t o.getY()).ToList();
List sweepline = new List();
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;
============================================
ОБНОВЛЕНИЕ: 12 сентября: Реализовал TreeSet из C5, реализовал IComparable для моих классов и еще больше замедлил его? Я все еще индексирую это, если это имеет значение?
http://www.itu.dk/research/c5/
Код с использованием TreeSet:}
TreeSet sweepline = new TreeSet();
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("");