Изменения

{{В разработке}} '''Алгоритм Балабана''' {{---}} детерминированный алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются . <br>

Методы поиска Решение задачи по поиску множества пересечений отрезков разделяются на детерминированные и недетерминированныеявляется одной из главных задач вычислительной геометрии. Рассмотрим несколько самых распространенных алгоритмов: # Тривиальный детерминированный алгоритм имеет временную сложность <tex>O(n^2)</tex> , и его суть его заключается в проверке попарного пересечения отрезков. # Сложнее, но эффективнее алгоритм Бентли-Отмена Оттмана <ref>[http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Бентли-Оттмана ''Алгоритм_БентлиАлгоритм Бентли-Оттмана'']</ref> с оценкой сложности <tex>O((n + k)\ log(n)+k)</tex>, в основе которого лежит метод заметающей прямой. # Алгоритм, предложенный Чазелле и Едельсбруннером <ref>[http://www.cs.princeton.edu/~chazelle/pubs/IntersectLineSegments.pdf ''An optimal algorithm for intersecting line segments in the plane'']</ref>, имеет лучшую оценку <tex>O(n \log n + k)</tex>, но в отличие от предыдущих методов требует квадратичной памяти.# Оптимальный детерминированный алгоритм был предложен Балабаном <ref>[http://www.cs.sfu.ca/~binay/813.2011/Balaban.pdf ''I.J. Balaban. An optimal algorithm for finding segments intersections. In Proceedings of the Eleventh Annual Symposium on Computational Geometry, ACM Press, New York, 1995. - pp. 211–219.'']</ref> с временной оценкой сложности <tex>O(n\ log(n) + k)</tex> и <tex>O(n)</tex> памяти, где К - число пересекающихся отрезков. При количестве отрезков от 2000, и большому количеству пересечений целесообразно использовать алгоритм Балабана. Однако в результате громоздкости и высокой сложности реализации алгоритма, в большинстве практических задач используется алгоритм заметающей прямой Бентли-Оттмана. ==Основные понятия== Введем некоторые обозначения. Пусть <tex>Int(S)</tex> - множество всех точек пересечения отрезков из множества <tex>S</tex>, а <tex>K = |Int(S)|</tex> - количество таких пересечений ;<br>Через <tex>\langle a, b \rangle</tex> обозначим вертикальную полосу, которая ограничена прямыми <tex>x = a</tex> и <tex>x = b</tex>, а через <tex>s</tex> {{---}} отрезок с вершинами в точках с абсциссами <tex>l</tex> и <tex>r</tex>.<br>Рассмотрим взаимное расположение вертикальной полосы <tex>\langle a, b \rangle</tex> и отрезка <tex>s</tex>.  {{Определение|definition=Будем говорить, что отрезок <tex>s</tex>, с вершинами в точках с абсциссами <tex>l</tex> и <tex>r</tex> :{{---}} '''охватывает''' (''span'') полосу <tex>\langle a, b \rangle</tex>, если <tex>l \le a \le b \le r</tex>; <br> {{---}} '''внутренний''' (''inner'') для полосы <tex>\langle a, b \rangle</tex>, если <tex>a < l < r < b</tex>; <br> {{---}} '''пересекает''' (''cross'') полосу <tex>\langle a, b \rangle</tex> в других случаях.}} {{Определение|definition=Два отрезка <tex>s_1</tex> и <tex>s_2</tex> называются ''пересекающимися внутри'' полосы <tex>\langle a, b \rangle</tex>, если их точка пересечения лежит в пределах этой полосы.<br> Для двух множеств отрезков <tex>S</tex> и <tex>S'</tex> определим множество <tex>Int(S, S')</tex> как <tex>\{ {s, s'} | (s \in S, s' \in S') \& (s \ intersect \ s') \}</tex>.}}[[Файл:Balaban_pic_1.png|280px|thumb|right|<tex>D = ((s_1, s_2, s_3), \langle a, b \rangle)</tex>, <tex>Loc(D, s_4) = 0</tex>, <tex>Loc(D, s_5) = 2</tex> или <tex>3</tex>, <tex>Int(D, \{s_4,\ s_5\}) = \{\{s_3,\ s_5\}\}</tex>]] Обозначения <tex>Int_{a, b}(S)</tex> и <tex>Int_{a, b}(S, S')</tex> будут использоваться для описания подмножеств <tex>Int(S)</tex> и <tex>Int(S, S')</tex>, состоящих из пересекающихся пар отрезков в пределах полосы <tex>\langle a, b \rangle</tex>. Далее фигурные скобки <tex>\{\}</tex> используются для определения неупорядоченных множеств, а круглые скобки <tex>()</tex> используются для определения упорядоченных множеств. {{Определение|neat=neat|definition=Введем отношение порядка на множестве отрезков <tex>s_1 <_a s_2</tex> если оба отрезка пересекают вертикальную линию<br> <tex>x = a</tex> и точка пересечения этой прямой с отрезком <tex>s_1</tex> лежит ниже точки пересечения с <tex>s_2</tex>.}} {{Определение|neat=neat|definition=''Лестница'' <tex>D</tex> — это пара <tex>(Q, \langle a, b \rangle)</tex>, в которой отрезки из множества <tex>Q</tex> удовлетворяют следующим условиям : {{---}} любой отрезок из <tex>Q</tex> охватывает полосу <tex>\langle a, b \rangle</tex>; <br>{{---}} нет пересечений отрезков внутри лестницы; <br>{{---}} <tex>Q</tex> упорядочена по отношению <tex><_a</tex>. Часть отрезков лестницы внутри полосы будем называть '''ступеньками'''.}} {{Определение|definition=Будем называть лестницу <tex>D</tex> '''полной''' относительно множества отрезков <tex>S</tex>, если каждый отрезок из <tex>S</tex> либо не охватывает полосу <tex>\langle a, b \rangle</tex>, либо пересекает хотя бы одну из ступенек из множества <tex>D</tex>.}} {{Лемма|id=lemma1|statement=Пусть лестница <tex>D</tex> полна относительно множества отрезков <tex>S</tex>, где <tex>S</tex> состоит из отрезков, пересекающих полосу <tex>\langle a, b \rangle</tex>, тогда <tex>|S| \le Ends_{a, b}(S) + |Int(D, S)|</tex>,<br>где <tex>Ends_{a, b}(S)</tex> это число вершин отрезков из <tex>S</tex>, находящихся в пределах полосы <tex>\langle a, b \rangle</tex>.}} {{Определение|definition=Если точка <tex>p</tex> отрезка <tex>s</tex> лежит между ступеньками <tex>i</tex> и <tex>i + 1</tex>, тогда число <tex>i</tex> называется ''местоположением'' <tex>s</tex> на лестнице <tex>D</tex> и обозначается как <tex>Loc(D, s)</tex>}} {{Утверждение|statement=Имея лестницу <tex>D = (Q, \langle a, b \rangle)</tex> и множество отрезков <tex>S</tex>, множество <tex>Int(D, S)</tex> можно найти за время <tex>O(|S| log|Q| + |Int(D, S)|)</tex>. <br>Однако, если <tex>S’</tex> упорядочено отношением <tex><_x</tex>, где <tex>x \in [a, b]</tex>, тогда можно найти <tex>Int(D, S)</tex> за время <tex>O(|S| + |Q| + |Int(D, S)|)</tex>.}}

[http://www.graphicon.ru/proceedings/2010/conference/RU/Se4/021.pdf ''Т.Вознюк, В.Терещенко {{---}} К построению эффективного решения задачи пересечения отрезков'']<br>[http://booksshare.net/books/math/preparata-f/1989/files/vichgeometr.pdf ''Ф.Препарата, М.Шеймос {{---}} Вычислительная геометрия'']<br>