Пересечение множества отрезков - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:42:26Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:28, 1 сентября 2022

2022-09-01T03:28:02Z

Dima: /* Доказательство корректности */

2014-03-14T12:00:20Z

‎Доказательство корректности

Dima в 11:56, 14 марта 2014

2014-03-14T11:56:45Z

Dima в 11:55, 14 марта 2014

2014-03-14T11:55:46Z

Dima: /* Описание алгоритма */

2014-03-14T10:29:40Z

‎Описание алгоритма

Gromak: Пофиксил псевдокод

2014-01-29T18:27:42Z

Пофиксил псевдокод

Gromak: /* Объём памяти */

2014-01-29T16:42:58Z

‎Объём памяти

194.85.161.2: /* Доказательство корректности */

2014-01-21T07:33:58Z

‎Доказательство корректности

Gr1n: /* Доказательство корректности */

2014-01-17T14:58:38Z

‎Доказательство корректности

← Предыдущая		Версия 16:42, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	Пусть дано множество из <tex>n</tex> отрезков и требуется найти все точки их пересечения. Очевидно, что задачу можно решить полным перебором за <tex>O(n^2)</tex>; ясно также, что любой алгоритм будет в худшем случае работать за <tex>\Theta(n^2)</tex> (нетрудно привести пример, когда количество пересечений квадратично, а алгоритм обязан сообщить о каждом пересечении). Однако существуют алгоритмы, которые оптимальнее, если количество точек пересечения отрезков невелико. Так алгоритм Бентли-Оттмана (англ. Bentley-Ottmann) позволяет решить задачу о пересечении отрезков, используя <tex>O((n+I)\log{n})</tex> времени и <tex>O(n)</tex> памяти, где <tex>I</tex> {{---}} количество пересечений.		Пусть дано множество из <tex>n</tex> отрезков и требуется найти все точки их пересечения. Очевидно, что задачу можно решить полным перебором за <tex>O(n^2)</tex>; ясно также, что любой алгоритм будет в худшем случае работать за <tex>\Theta(n^2)</tex> (нетрудно привести пример, когда количество пересечений квадратично, а алгоритм обязан сообщить о каждом пересечении). Однако существуют алгоритмы, которые оптимальнее, если количество точек пересечения отрезков невелико. Так алгоритм Бентли-Оттмана (англ. Bentley-Ottmann) позволяет решить задачу о пересечении отрезков, используя <tex>O((n+I)\log{n})</tex> времени и <tex>O(n)</tex> памяти, где <tex>I</tex> {{---}} количество пересечений.

← Предыдущая		Версия 03:28, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	Пусть дано множество из <tex>n</tex> отрезков и требуется найти все точки их пересечения. Очевидно, что задачу можно решить полным перебором за <tex>O(n^2)</tex>; ясно также, что любой алгоритм будет в худшем случае работать за <tex>\Theta(n^2)</tex> (нетрудно привести пример, когда количество пересечений квадратично, а алгоритм обязан сообщить о каждом пересечении). Однако существуют алгоритмы, которые оптимальнее, если количество точек пересечения отрезков невелико. Так алгоритм Бентли-Оттмана (англ. Bentley-Ottmann) позволяет решить задачу о пересечении отрезков, используя <tex>O((n+I)\log{n})</tex> времени и <tex>O(n)</tex> памяти, где <tex>I</tex> {{---}} количество пересечений.		Пусть дано множество из <tex>n</tex> отрезков и требуется найти все точки их пересечения. Очевидно, что задачу можно решить полным перебором за <tex>O(n^2)</tex>; ясно также, что любой алгоритм будет в худшем случае работать за <tex>\Theta(n^2)</tex> (нетрудно привести пример, когда количество пересечений квадратично, а алгоритм обязан сообщить о каждом пересечении). Однако существуют алгоритмы, которые оптимальнее, если количество точек пересечения отрезков невелико. Так алгоритм Бентли-Оттмана (англ. Bentley-Ottmann) позволяет решить задачу о пересечении отрезков, используя <tex>O((n+I)\log{n})</tex> времени и <tex>O(n)</tex> памяти, где <tex>I</tex> {{---}} количество пересечений.

@@ Строка 103: / Строка 103: @@
 {{Лемма
 |statement=Пусть <tex>p</tex> {{---}} точка пересечения нескольких отрезков, причем <tex>p</tex> не совпадает ни с одним из концов отрезков, участвующих в пересечении. Отсортируем отезки по углу вокруг <tex>p</tex> и пусть отрезки <tex>s_i</tex> и <tex>s_j</tex> окажутся соседними в сортировке. Тогда существует событие <tex>q</tex> с приоритетом выше, чем у <tex>p</tex>, такое что при обработке этого события <tex>s_i</tex> и <tex>s_j</tex> будут соседними в статусе.
-||proof=Рассмотрим событие <tex>q</tex> которое будет обработано непосредственно перед <tex>p</tex>. Предположим, что при обработке этого события <tex>s_i</tex> и <tex>s_j</tex> не будут соседними в статусе. Это возможно только если между ними есть третий отрезок <tex>s</tex>. Но тогда или <tex>s</tex> пересекает какой-то из отрезков <tex>s_i, s_j</tex> в точке с приоритетом выше, чем у <tex>p</tex>, но ниже, чем у <tex>q</tex>; или <tex>s</tex> пересекает их оба в точке <tex>p</tex>, что противоречит тому, что они соседние в сортировке по углу; или конец отрезка имеет приоритет выше, чем <tex> p </tex>, но ниже, чем <tex> q </tex> и отрезок не пересекает <tex>s_i, s_j</tex>. Тогда в последнем случае нарушается тот факт, что <tex>q</tex> идет непосредственно перед <tex>p</tex>. Следовательно при обработке <tex>q</tex> <tex>s_i</tex> и <tex>s_j</tex> будут соседними в статусе.
+||proof=Рассмотрим событие <tex>q</tex> которое будет обработано непосредственно перед <tex>p</tex>. Предположим, что при обработке этого события <tex>s_i</tex> и <tex>s_j</tex> не будут соседними в статусе. Это возможно только если между ними есть третий отрезок <tex>s</tex>. Но тогда или <tex>s</tex> пересекает какой-то из отрезков <tex>s_i, s_j</tex> в точке с приоритетом выше, чем у <tex>p</tex>, но ниже, чем у <tex>q</tex>; или <tex>s</tex> пересекает их оба в точке <tex>p</tex>, что противоречит тому, что они соседние в сортировке по углу. Следовательно при обработке <tex>q</tex> <tex>s_i</tex> и <tex>s_j</tex> будут соседними в статусе.
 }}

← Предыдущая		Версия 11:56, 14 марта 2014
Строка 131:		Строка 131:

	Очевидно, что статус в худшем случае занимает <tex>O(n)</tex> памяти, однако очередь событий может занимать <tex>O(n + I)</tex> памяти. Если модифицировать алгоритм так, что в очереди будут храниться только точки пересечения отрезков, соседних в статусе, то объём используемой памяти сократится до <tex>O(n)</tex>. Для этого нужно удалять точки пересечения отрезков, которые перестали быть соседними. Перед тем, как мы дойдём до точки удаленной точки, обязательно найдётся соседняя в статусе пара отрезков, которые пересекаются в этой точке, и она снова будет вставлена в очередь. Ясно, что такая оптимизация не влияет на время работы алгоритма.		Очевидно, что статус в худшем случае занимает <tex>O(n)</tex> памяти, однако очередь событий может занимать <tex>O(n + I)</tex> памяти. Если модифицировать алгоритм так, что в очереди будут храниться только точки пересечения отрезков, соседних в статусе, то объём используемой памяти сократится до <tex>O(n)</tex>. Для этого нужно удалять точки пересечения отрезков, которые перестали быть соседними. Перед тем, как мы дойдём до точки удаленной точки, обязательно найдётся соседняя в статусе пара отрезков, которые пересекаются в этой точке, и она снова будет вставлена в очередь. Ясно, что такая оптимизация не влияет на время работы алгоритма.
−
−	~~== См. также ==~~
−	* [[Алгоритм Бентли-Оттмана]]

	== Источники ==		== Источники ==

@@ Строка 21: / Строка 21: @@
 Нам потребуется две структуры данных.
-Во-первых, мы будем хранить очередь событий <tex>Q</tex> в виде сбалансированного бинарного дерева поиска, что позволит извлекать следующее событие и вставлять новое событие в очередь за <tex>\log{m}</tex>, где <tex>m</tex> {{---}} количество элементов в очереди. Дерево будет отсортировано согласно порядку, введённому выше. Причём вместе с каждым событием мы будем хранить список отрезков, верхней точкой которых он является.
+Во-первых, мы будем хранить очередь событий <tex>Q</tex> в виде сбалансированного бинарного дерева поиска, что позволит извлекать следующее событие и вставлять новое событие в очередь за <tex>O(\log{m})</tex>, где <tex>m</tex> {{---}} количество элементов в очереди. Дерево будет отсортировано согласно порядку, введённому выше. Причём вместе с каждым событием мы будем хранить список отрезков, верхней точкой которых он является.
 Во вторых, будем хранить статус <tex>T</tex> заметающей прямой: множество отрезков, пересекающих заметающую прямую в данный момент времени, упорядоченных слева направо. От статуса нам потребуется оптимальные вставка и удаление отрезков, поэтому по-прежнему удобно воспользоваться бинарным деревом поиска.

@@ Строка 7: / Строка 7: @@
 == Описание алгоритма ==
-В основу алгоритма положен метод заметающей прямой (sweep line), которая будет расположена горизонтально и двигаться вниз (в сторону уменьшения y-координаты). Нас будут интересовать события (events, event points) трёх типов:
+[[Файл:Status_line.png|200px|thumb|right|Заметающая прямая и события]]
 * верхний конец отрезка,
 * нижний конец отрезка,
 * точка пересечения пары отрезков;
-причем о событиях первых двух типов мы знаем заранее, а события, являющиеся пересечением отрезков, будут обнаружены и добавлены в множество необработанных событий динамически. Будем считать, что если у двух точек равные ординаты, то выше та, что лежит левее. Таким образом верхним концом горизонтального отрезка, в силу введенного порядка, является его левый конец. Это даст нам корректную обработку вырожденного случая, когда отрезок горизонтален. Можно представить, что заметающая прямая не горизонтальна, а повернута на малый угол против часовой стрелки, поэтому не существует такой конфигурации, что на ней лежит больше одного события (мы, для удобства, считаем точку пересечения трёх или более отрезков одним событием), а события с равными ординатами обрабатываются слева направо.
+причем о событиях первых двух типов мы знаем заранее, а события, являющиеся пересечением отрезков, будут обнаружены и добавлены в множество необработанных событий динамически. Будем считать, что если у двух точек равные ординаты, то выше та, что лежит левее. Таким образом верхним концом горизонтального отрезка, в силу введенного порядка, является его левый конец. Это даст нам корректную обработку вырожденного случая, когда отрезок горизонтален.
 Нам потребуется две структуры данных.
@@ Строка 18: / Строка 24: @@
 Во вторых, будем хранить статус <tex>T</tex> заметающей прямой: множество отрезков, пересекающих заметающую прямую в данный момент времени, упорядоченных слева направо. От статуса нам потребуется оптимальные вставка и удаление отрезков, поэтому по-прежнему удобно воспользоваться бинарным деревом поиска.
 Главная идея заключается в том, что мы будем проверять, пересекаются ли два отрезка, если они являются соседними в статусе. Это означает, что каждый отрезок мы будем проверять на пересечение с его левым и правым соседями в статусе. Далее, по ходу выполнения алгоритма, у отрезка могут измениться соседи; когда это происходит мы снова проверяем, не пересекает ли отрезок его новых соседей в статусе?
@@ Строка 39: / Строка 51: @@
 * Нижний конец отрезка. В этом случае мы удалим отрезок из статуса и проверим пару отрезков ставших соседними на пересечение. Как и в предыдущем случае, обнаруженные пересечения могут уже находиться в очереди.
-Как было сказано выше, мы интерпретируем пересечение более двух отрезков в одной точке как одно событие. В этом случае обработка несколько сложнее (стоит посмотреть пристально на псевдокод и убедиться, что алгоритм корректно обрабатывает такие события). Псевдокод функции обработки события:
+{|border="0" cellpadding="5" width=30% align=center
   handleEventPoint(p)
@@ Строка 73: / Строка 91: @@
         Q.insert(x) // должно работать корректно, если x уже есть в Q
-Описанный алгоритм обрабатывает корректно горизонтальные отрезки и точки пересечения трёх и более отрезков, но не справляется с перекрывающимися отрезками. Об этом вскользь упомянуто здесь: [[Алгоритм Бентли-Оттмана]].
+{|border="0" cellpadding="5" width=30% align=center
 == Доказательство корректности ==

@@ Строка 48: / Строка 48: @@
      '''if''' <tex> \vert L(p) \cup C(p) \cup U(p) \vert > 1</tex>
         report(p, <tex>L(p) \cup C(p) \cup U(p)</tex>) // сообщить о p как о точки пересечения отрезков <tex>L(p) \cup C(p) \cup U(p)</tex>
-       T.remove(<tex>L(p) \cup C(p)</tex>)
+    T.remove(<tex>L(p) \cup C(p)</tex>)
-       T.insert(<tex>C(p) \cup U(p)</tex>)
+    T.insert(<tex>C(p) \cup U(p)</tex>)
-       // отрезки должны быть вставлены в порядке,
+    // отрезки должны быть вставлены в порядке,
-       // в котором они пересекают горизонтальную линию,
+    // в котором они пересекают горизонтальную линию,
-       // лежащую немного ниже заметающей прямой
+    // лежащую немного ниже заметающей прямой
-       // (при удалении-вставке отрезков из C(p) - те поменяют порядок на обратный
+    // (при удалении-вставке отрезков из C(p) - те поменяют порядок на обратный
-       '''if''' <tex>C(p) \cup U(p) = \emptyset</tex>
+    '''if''' <tex>C(p) \cup U(p) = \emptyset</tex>
-          s_l = левый сосед p в T
+       s_l = левый сосед p в T
-          s_r = правый сосед p в T
+       s_r = правый сосед p в T
-          findIntersection(s_l, s_r, p)
+       findIntersection(s_l, s_r, p)
-       '''else'''
+    '''else'''
-          s1 = самый левый отрезок из <tex>C(p) \cup U(p)</tex> в T
+       s1 = самый левый отрезок из <tex>C(p) \cup U(p)</tex> в T
-          s_l = левый сосед s1 в T
+       s_l = левый сосед s1 в T
-          findIntersection(s_l, s1, p)
+       findIntersection(s_l, s1, p)
-          s2 = самый правый отрезок из <tex>C(p) \cup U(p)</tex> в T
+       s2 = самый правый отрезок из <tex>C(p) \cup U(p)</tex> в T
-          s_r = правый сосед s2 в T
+       s_r = правый сосед s2 в T
-          findIntersection(s2, s_r, p)
+       findIntersection(s2, s_r, p)
   findIntersection(s_l, s_r, p)

@@ Строка 110: / Строка 110: @@
 == Объём памяти ==
-Очевидно, что статус в худшем случае занимает <tex>O(n)</tex> памяти, однако очередь событий может занимать <tex>O(n + I)</tex> памяти. Если модифицировать алгоритм так, что в очереди будут храниться только точки пересечения торезков, соседних в статусе, то объём используемой памяти сократиться до <tex>O(n)</tex>. Для этого нужно удалять точки пересечения отрезков, которые перестали быть соседними. Перед тем, как мы дойдём до точки удаленной точки, обязательно найдется соседняя в статусе пара отрезков, которая пересекается в этой точке, и она снова будет вставлена в очередь. Ясно, что такая оптимизация не влияет на время работы алгоритма.
+Очевидно, что статус в худшем случае занимает <tex>O(n)</tex> памяти, однако очередь событий может занимать <tex>O(n + I)</tex> памяти. Если модифицировать алгоритм так, что в очереди будут храниться только точки пересечения отрезков, соседних в статусе, то объём используемой памяти сократится до <tex>O(n)</tex>. Для этого нужно удалять точки пересечения отрезков, которые перестали быть соседними. Перед тем, как мы дойдём до точки удаленной точки, обязательно найдётся соседняя в статусе пара отрезков, которые пересекаются в этой точке, и она снова будет вставлена в очередь. Ясно, что такая оптимизация не влияет на время работы алгоритма.
 == См. также ==

@@ Строка 88: / Строка 88: @@
 {{Теорема
 |statement=Алгоритм сообщает о всех точках пересечения
-||proof=Воспользуемся индукцией по событиям, отсортированным в порядке, введённом выше (<tex>p < q \Leftrightarrow p_y < q_y \lor p_y = q_y \land p_x < q_x</tex> {{---}} точка пересечения). Пусть <tex>p</tex> {{---}} точка пересечения. Предположим что все события <tex>q, q < p</tex> были обработаны корректно. Тогда <tex>p</tex> будет обнаружена.
+||proof=Воспользуемся индукцией по событиям, отсортированным в порядке, введённом выше (<tex>p < q \Leftrightarrow p_y < q_y \lor p_y = q_y \land p_x < q_x</tex>). Пусть <tex>p</tex> {{---}} точка пересечения. Предположим что все события <tex>q, q < p</tex> были обработаны корректно. Тогда <tex>p</tex> будет обнаружена.
 Действительно, если <tex>p</tex> {{---}} конец некоторого отрезка, то <tex>p</tex> добавлена в очередь событий в начале работы. Все содержащие её отрезки из статуса, который будет текущим при обработке <tex>p</tex> будут найдены. Для остальных отрезков, содержащих <tex>p</tex>, верно, что <tex>p</tex> {{---}} их верхний конец, и они будут найдены, т.к. мы храним их вместе с <tex>p</tex> в очереди.