Алгоритм Бентли — Оттманна (1979) позволяет найти все точки пересечений прямолинейных отрезков на плоскости. В нем применяется метод выметающей прямой[1] (заметающей прямой[2], движущейся прямой[3], сканирующей линии[4]; англ. sweeping line). В методе используется вертикальная выметающая прямая движущаяся слева направо, при этом отрезки, которые она пересекает при данной координате , можно упорядочить по координате , тем самым их можно сравнивать между собой (какой выше, какой ниже). Это сравнение можно осуществить, например, используя уравнение прямой, проходящей через две точки (отрезки заданы двумя своими конечными точками): , где , и , — координаты, соответственно, первой и второй точек отрезка. Выметающая прямая перемещается по так называемым точкам событиям (левым и правым концам отрезков, а также точкам пересечения отрезков). После точки пересечения отрезки следует менять местами, так как, например, самый верхний из пересекающихся отрезков после точки пересечения становится самым нижним. Приведенный ниже алгоритм не рассчитан на случай, когда два отрезка пересекаются больше, чем в одной точке.
NB Выметающую прямую можно также представить как горизонтальную, движущуюся сверху вниз по координате , и сравнивать пересекающие её отрезки по координате .
Возникает проблема с вертикальным отрезком в том смысле как его сравнивать на выше/ниже с пересекающими отрезками. Для этого можно, например, считать, что если точка пересечения вертикального с не вертикальным отрезков находится ниже текущей координаты точки события, то вертикальный отрезок находится выше, если точка пересечения выше текущей координаты точки события, то вертикальный отрезок считается ниже пересекающего его. Если текущая координата равна координате точки события, то при удалении отрезка считать, что вертикальный отрезок ниже, при вставке же считать, что он выше.
В худшем случае, когда, например, все отрезки, пересекаясь между собой, образуют прямоугольную сетку, будет точек пересечений, которые надо будет хранить. Чтобы избежать использования квадрата памяти в алгоритме, можно удалять точку пересечения отрезков, которые временно перестают быть соседними при данном положении выметающей прямой. Эти точки все равно будут снова найдены при последующих шагах алгоритма, когда данные отрезки снова станут соседними (Печ, Шерир 1991).
В приведенном ниже псевдокоде используются:
segmentsIntersections(points[]) 1) Инициализируются Q и T. В Q заносятся все концы отрезков, упорядоченные по координате x, при этом, если две точки совпали, то левая конечная точка отрезка помещается перед правой. Если совпали только x, то точка с меньшим y является меньшей. T ← ∅ 2) while Q != ∅ q ← min(Q); processPoint(q);
processPoint(q) 1) Найти в Q все отрезки, содержащие q; // они в Q будут соседними, так как точки события, которые содержатся в этих отрезках, имеют одинаковые координаты; 2) if (|L(q)| + |R(q)| + |I(q)| > 1) ИЛИ (|I(q)| > 0) then Выдать в ответ точку q; 3) if (|I(q)| = 0) И (|L(q)|+|R(q)| > 0) // в рассматриваемой точке все отрезки только начинаются или заканчиваются; then I(q) ← I(q) ∪ L(q) ∪ R(q); // добавить в I(q) L(q) и R(q) 4) Удалить из T R(q) и I(q); 5) Вставить в T I(q) и L(q); // из T были удалены все отрезки из множества I(q), теперь же вставляются обратно в измененном порядке после точки пересечения; 6) if (L(q)∪I(q) = ∅) ИЛИ (|I(q)| = |R(q)| - 1) then Найти в T верхнего и нижнего соседей q su и sl; newq = findIntersect(su, sl); if newq != NULL then add(Q, newq); 7) else Пусть s′ — самый верхний отрезок из L(q)∪I(q); Пусть su — верхний сосед s′ в T; Пусть s′′ — самый нижний отрезок из L(q)∪ I(q); Пусть sl — нижний сосед s′′ в T; newq = findIntersect(su, s′); if newq != NULL then add(Q, newq); newq = findIntersect(sl, s′′); if newq != NULL then add(Q, newq); // далее убираем квадрат памяти; newq = findIntersect(sl, su); if newq != NULL then delete(Q, newq); newq = findIntersect(s′′, su); if newq != NULL then delete(Q, newq); newq = findIntersect(sl, s′); if newq != NULL then delete(Q, newq);
findIntersect(sl, su) if sl и su пересекаются правее заметающей прямой (или на заметающей прямой выше текущей точки события) then return newq; else return NULL;
Пусть — число отрезков, — число отрезков, пересекающих точку . Тогда время на инициализацию Q равно , на инициализацию T — . На поиск всех отрезков, проходящих через точку и обновление Q, требуется времени. На обновление T также времени. Суммарно: , где — число точек пересечения . .
Память , благодаря тому, что удаляются точки пересечения отрезков, которые перестали быть соседними, иначе было бы , где .
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .