Сократить время, необходимое для нахождения пересечения N линии
Есть N отрезки, которые являются горизонтальными или вертикальными. Теперь мне нужно узнать общее количество пересечений и общее количество пересечений на отрезок. N может пойти на 100000. Я пытался проверить каждую пару строк. Ответ правильный, но мне нужно сократить его время.
Вот мой код:
using namespace std;
typedef struct Point
{
long long int x;
long long int y;
} ;bool fun(Point p0, Point p1, Point p2, Point p3)
{
double s1_x, s1_y, s2_x, s2_y;
s1_x = p1.x - p0.x; s1_y = p1.y - p0.y;
s2_x = p3.x - p2.x; s2_y = p3.y - p2.y;
double s, t;
s = (-s1_y * (p0.x - p2.x) + s1_x * (p0.y - p2.y)) / (-s2_x * s1_y + s1_x * s2_y);
t = ( s2_x * (p0.y - p2.y) - s2_y * (p0.x - p2.x)) / (-s2_x * s1_y + s1_x * s2_y);
if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
{
return 1; // Collision detected
}
return 0; // No collision
}int main()
{
long long int n // number of line segments;
Point p[n],q[n]; // to store end points of line segments
for( long long int i=0;i<n;i++)
{
// line segments is defined by 2 points P(x1,y1) and Q(x2,y2)
p[i].x=x1;
p[i].y=y1;
q[i].x=x2;
q[i].y=y2;
}
for( long long int i=0;i<n-1;i++)
{
for( long long int j=i+1;j<n;j++)
{
if(fun(p[i],q[i],p[j],q[j]))
count++;
}
}
return 0;
}
Может ли кто-нибудь помочь мне в сокращении временной сложности этой программы?
Решение
Вот алгоритм времени O (n log n), который использует линию развертки с деревом Фенвика.
Шаг 0: переназначение координат
Сортируйте x-координаты и замените каждое значение целым числом в 0..n-1, чтобы сохранить порядок. Сделайте то же самое для y-координат. Свойства пересечения сохраняются, что упрощает реализацию алгоритмов, представленных ниже.
Шаг 1: параллельные отрезки
Я опишу этот шаг для горизонтальных сегментов. Повторите для вертикальных сегментов.
Сгруппируйте горизонтальные сегменты по координате y. Обрабатывайте по одной группе за раз, создавая события для линии развертки следующим образом. Каждый сегмент получает начальное событие в своей меньшей конечной точке и конечное событие в своей большей. Сортировка начинается до остановок, если вы хотите замкнуть отрезки. Разверните события в отсортированном порядке, отслеживая количество отрезков, которые в данный момент пересекают линию развертки, и количество обработанных стартовых событий. Число параллельных пересечений для сегмента равно (количество сегментов, пересекаемых во время запуска + количество событий запуска, обработанных во время остановки — количество событий запуска, обработанных во время запуска). (Смотрите также Учитывая набор интервалов, найдите интервал, который имеет максимальное количество пересечений. для моего предыдущего объяснения для этого.)
Шаг 2: перпендикулярные отрезки
Я опишу этот шаг с точки зрения подсчета для каждого отрезка горизонтальной линии, сколько отрезков вертикальной линии он пересекает.
Мы делаем еще один алгоритм стреловидности. События — это горизонтальные сегменты, вертикальные сегменты и горизонтальные сегменты, отсортированные в том порядке, предполагающем отрезки отрезков. Мы используем дерево Фенвика для отслеживания, для каждой координаты y, сколько вертикальных сегментов покрыло эту координату y до сих пор. Чтобы обработать горизонтальное начало, вычтите значение дерева для его координаты y из его числа пересечений. Чтобы обработать горизонтальную остановку, добавьте значение дерева для его координаты y к счетчику пересечений. Это означает, что количество увеличивается на разницу, которая представляет собой количество вертикальных сегментов, которые нанесли удар горизонтальному, когда он был активным. Чтобы обработать вертикальный сегмент, используйте мощность дерева Фенвика, чтобы быстро увеличить все значения между его меньшей координатой y и его большей (включая предполагаемые замкнутые сегменты).
Если вы хотите, эти алгоритмы стреловидности могут быть объединены. Я держал их отдельно по объяснительным причинам.
Другие решения
Других решений пока нет …