Алгоритм Бентли-Оттмана - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:35:35Z

rollbackEdits.php mass rollback

185.220.100.254 в 04:14, 1 сентября 2022

2022-09-01T04:14:34Z

185.38.208.133: /* Статус */

2018-07-14T17:39:38Z

‎Статус

188.162.64.87: /* Двоичное дерево поиска в качестве статуса */ мда $log$)))

2015-08-31T09:17:09Z

‎Двоичное дерево поиска в качестве статуса: мда $log$)))

Sementry: /* Постановка задачи */

2013-01-12T20:14:33Z

‎Постановка задачи

192.168.0.2: /* Сканирующая точка */

2012-01-21T03:46:00Z

‎Сканирующая точка

System29a: тире

2012-01-20T00:17:53Z

тире

Proshev в 17:32, 30 декабря 2011

2011-12-30T17:32:44Z

Pashkal: /* Сканирующая точка */

2011-12-09T04:00:45Z

‎Сканирующая точка

Pashkal в 03:59, 9 декабря 2011

2011-12-09T03:59:33Z

← Предыдущая		Версия 16:35, 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 Майкл Наки].
−	\|}
−
	Алгоритм Бентли-Оттмана(англ. Bentley-Ottmann) — алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются, при этом для каждой точки алгоритм выдает множество отрезков, пересекающихся в ней.		Алгоритм Бентли-Оттмана(англ. Bentley-Ottmann) — алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются, при этом для каждой точки алгоритм выдает множество отрезков, пересекающихся в ней.

← Предыдущая		Версия 04:14, 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 Майкл Наки].
		+	\|}
		+
	Алгоритм Бентли-Оттмана(англ. Bentley-Ottmann) — алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются, при этом для каждой точки алгоритм выдает множество отрезков, пересекающихся в ней.		Алгоритм Бентли-Оттмана(англ. Bentley-Ottmann) — алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются, при этом для каждой точки алгоритм выдает множество отрезков, пересекающихся в ней.

@@ Строка 24: / Строка 24: @@
 ===Статус===
 [[Файл:pic2.jpg|right|560|thumb|Иллюстрация определения статуса]]
-Назовем статусом множество, в которой содержатся все отрезки, пересекающие нашу сканирующую прямую. Важно, что эти отрезки должны быть упорядочены по возрастанию (или убыванию) координаты их пересечения с прямой. Заметим, что в процессе работы алгоритма отрезки могут добавляться в произвольные места этого упорядоченной множества, удаляться из произвольных мест или меняться местами друг с другом.
+Назовем статусом множество, в котором содержатся все отрезки, пересекающие нашу сканирующую прямую. Важно, что эти отрезки должны быть упорядочены по возрастанию (или убыванию) координаты их пересечения с прямой. Заметим, что в процессе работы алгоритма отрезки могут добавляться в произвольные места этого упорядоченного множества, удаляться из произвольных мест или меняться местами друг с другом.
 ===Важная мысль===

@@ Строка 66: / Строка 66: @@
 ==Реализация алгоритма==
 ===Двоичное дерево поиска в качестве статуса===
-Из определения статуса ясно, какую структуру удобно использовать в качестве статуса: двоичное дерево поиска. В нем удобно делать все необходимые операции, и выполняться они будут за <tex>O(log_2(n))</tex>.
+Из определения статуса ясно, какую структуру удобно использовать в качестве статуса: двоичное дерево поиска. В нем удобно делать все необходимые операции, и выполняться они будут за <tex>O(\log_2(n))</tex>.
 ===Реализация множества необработанных событий===

@@ Строка 5: / Строка 5: @@
 На плоскости лежит <tex>n</tex> отрезков, каждый из них задан координатами своих концов. Требуется по этим данным определить множество точек, в которых эти отрезки пересекаются. Однако, не всегда координаты точки можно абсолютно точно представить с помощью вещественных типов данных. Поэтому характеризовать каждую точку будем множеством отрезков, которые пересекаются в этой точке.
-Для упрощения понимания введем два ограничения на входные данные:
+Для упрощения понимания введем три ограничения на входные данные:
 * не существует вертикальных отрезков
 * не существует пары отрезков, имеющих более одной общей точки
 * никакие три отрезка не пересекаются в одной точке
-Как обрабатывать эти случаи будет объяснено позднее.
+Как обрабатывать эти случаи, будет объяснено позднее.
 ==Алгоритм==

@@ Строка 51: / Строка 51: @@
 [[Файл:anim2.gif|right|560|thumb|Сканирующая точка]]
-Слегка поменяем нашу концепцию. Сканирующая прямая теперь становится не совсем прямой. Теперь у нас появляется, скорее, сканирующая точка. Суть изменения в следующем: в случае, если несколько событий попадают на одну вертикальную прямую, мы их обрабатываем в порядке возрастания координаты по оси <tex>X</tex>. Внимательный читатель сейчас, наверное, воскликнет: "А как же тогда наш статус? Ведь отрезки не могут пересекать точку!". Однако и это не является проблемой. Если отрезок, который лежит в статусе, не вертикален, то он сортируется по своей координате <tex>Y</tex>, в которой он пересекается с вертикальной прямой, проведенной через нашу точку (да, это бывшая сканирующая прямая). А вот если отрезок вертикален, то его параметром является как раз ордината "сканирующей точки". <s>Если внимательно подумать, то все будет корректно.</s>
+Слегка поменяем нашу концепцию. Сканирующая прямая теперь становится не совсем прямой. Теперь у нас появляется, скорее, сканирующая точка. Суть изменения в следующем: в случае, если несколько событий попадают на одну вертикальную прямую, мы их обрабатываем в порядке возрастания координаты по оси <tex>Y</tex>. Внимательный читатель сейчас, наверное, воскликнет: "А как же тогда наш статус? Ведь отрезки не могут пересекать точку!". Однако и это не является проблемой. Если отрезок, который лежит в статусе, не вертикален, то он сортируется по своей координате <tex>Y</tex>, в которой он пересекается с вертикальной прямой, проведенной через нашу точку (да, это бывшая сканирующая прямая). А вот если отрезок вертикален, то его параметром является как раз ордината "сканирующей точки". <s>Если внимательно подумать, то все будет корректно.</s>
 ===Несколько отрезков в одной точке===

@@ Строка 1: / Строка 1: @@
-Алгоритм Бентли-Оттмана(англ. Bentley-Ottmann) - алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются, при этом для каждой точки алгоритм выдает множество отрезков, пересекающихся в ней.
+Алгоритм Бентли-Оттмана(англ. Bentley-Ottmann) — алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются, при этом для каждой точки алгоритм выдает множество отрезков, пересекающихся в ней.
 ==Постановка задачи==
@@ Строка 62: / Строка 62: @@
 ===СНМ вместо отрезков===
 '''Внимание! Этот раздел должен интересовать только <s>задротов</s> любознательных, так как он описывает разбор случая, который нам, по обещанию Ковалева, не встретится.'''
-Нам остался последний сложный случай: наложение двух или более отрезков друг для друга. Давайте теперь вместо просто отрезков будем класть в СНМ следующее: множество отрезков, которые на данном этапе накладываются друг на друга. Понятно, что при добавлении нового отрезка он или создает свое множество, или добавляется в уже существующее. При удалении удаляется из множества, если оно осталось пустым - удаляется и само множество. А при пересечении с другим множеством попарно пересекаются все отрезки из двух множеств. При этом важно, что все отрезки, накладывающиеся друг на друга, должны занимать в статусе одну ячейку, т. е. являться одним множеством.
+Нам остался последний сложный случай: наложение двух или более отрезков друг для друга. Давайте теперь вместо просто отрезков будем класть в СНМ следующее: множество отрезков, которые на данном этапе накладываются друг на друга. Понятно, что при добавлении нового отрезка он или создает свое множество, или добавляется в уже существующее. При удалении удаляется из множества, если оно осталось пустым — удаляется и само множество. А при пересечении с другим множеством попарно пересекаются все отрезки из двух множеств. При этом важно, что все отрезки, накладывающиеся друг на друга, должны занимать в статусе одну ячейку, т. е. являться одним множеством.
 ==Реализация алгоритма==
@@ Строка 70: / Строка 70: @@
 ===Реализация множества необработанных событий===
 ====Приоритетная очередь====
-Опять же, эта идея возникает в процессе описания этого множества. При этом понятно, что точки сравниваются сначала по абсциссе, в случае равенства - по ординате.
+Опять же, эта идея возникает в процессе описания этого множества. При этом понятно, что точки сравниваются сначала по абсциссе, в случае равенства — по ординате.
 ====Двоичное дерево поиска====
 В принципе, вполне себе вариант реализации упорядоченного множества. Но его стоит использовать только тогда, когда мы хотим рассматривать пересечение нескольких отрезков в одной точке в качестве отдельного случая, а не как несколько попарных пересечений. Заметим, что это существенно усложняет реализацию.

← Предыдущая		Версия 17:32, 30 декабря 2011
Строка 76:		Строка 76:
	===Наконец, абсолютная точность===		===Наконец, абсолютная точность===
	Заметим, что мы не умеем получать абсолютно точные координаты пересечения двух отрезков. Однако, мы умеем представлять эти координаты в качестве суммы произведений нескольких чисел (просто пересечение прямых и раскрытие скобок в верхней части дроби). А сами координаты нам и не требуются, нам необходимо только уметь сравнивать эти координаты друг с другом. Сравнивать же эти суммы произведений с другими такими же суммами и с обычными числами (в обобщенном представлении тоже такими же суммами) мы тоже умеем. Победа!		Заметим, что мы не умеем получать абсолютно точные координаты пересечения двух отрезков. Однако, мы умеем представлять эти координаты в качестве суммы произведений нескольких чисел (просто пересечение прямых и раскрытие скобок в верхней части дроби). А сами координаты нам и не требуются, нам необходимо только уметь сравнивать эти координаты друг с другом. Сравнивать же эти суммы произведений с другими такими же суммами и с обычными числами (в обобщенном представлении тоже такими же суммами) мы тоже умеем. Победа!
		+
		+	[[Категория: Вычислительная геометрия]]

@@ Строка 2: / Строка 2: @@
 ==Постановка задачи==
-[[Файл:pic1.jpg|right|391|thumb|Пример результата работы алгоритма]]
+[[Файл:pic1.jpg|right|560|thumb|Пример результата работы алгоритма]]
 На плоскости лежит <tex>n</tex> отрезков, каждый из них задан координатами своих концов. Требуется по этим данным определить множество точек, в которых эти отрезки пересекаются. Однако, не всегда координаты точки можно абсолютно точно представить с помощью вещественных типов данных. Поэтому характеризовать каждую точку будем множеством отрезков, которые пересекаются в этой точке.
@@ Строка 23: / Строка 23: @@
 ===Статус===
-[[Файл:pic2.jpg|right|391|thumb|Иллюстрация определения статуса]]
+[[Файл:pic2.jpg|right|560|thumb|Иллюстрация определения статуса]]
 Назовем статусом множество, в которой содержатся все отрезки, пересекающие нашу сканирующую прямую. Важно, что эти отрезки должны быть упорядочены по возрастанию (или убыванию) координаты их пересечения с прямой. Заметим, что в процессе работы алгоритма отрезки могут добавляться в произвольные места этого упорядоченной множества, удаляться из произвольных мест или меняться местами друг с другом.
@@ Строка 33: / Строка 33: @@
 ===В итоге===
-[[Файл:anim1.gif|right|391|thumb|Пример работы алгоритма]]
+[[Файл:anim1.gif|right|560|thumb|Пример работы алгоритма]]
 Изначально у нас есть только события вида "начался отрезок" и "закончился отрезок". События вида "пересекаются два отрезка" будут добавляться нами в множество еще не обработанных событий. Соответственно, алгоритм выглядит так: выбираем то событие из множества необработанных, у которого наименьшая координата <tex>X</tex>, обрабатываем, делаем так, пока множество необработанных событий непустое. Плюс, на протяжении всего алгоритма должен поддерживаться следующий инвариант: в множество необработанных событий уже добавлены все пересечения отрезков, которые в текущем статусе текущие.
@@ Строка 50: / Строка 50: @@
 Решим, для начала, вопрос с вертикальными отрезками. Важно, что заодно пропадет и проблема с обработкой событий, имеющих одинаковую координату по оси <tex>X</tex>.
-[[Файл:anim2.gif|right|391|thumb|Сканирующая точка]]
+[[Файл:anim2.gif|right|560|thumb|Сканирующая точка]]
 Слегка поменяем нашу концепцию. Сканирующая прямая теперь становится не совсем прямой. Теперь у нас появляется, скорее, сканирующая точка. Суть изменения в следующем: в случае, если несколько событий попадают на одну вертикальную прямую, мы их обрабатываем в порядке возрастания координаты по оси <tex>X</tex>. Внимательный читатель сейчас, наверное, воскликнет: "А как же тогда наш статус? Ведь отрезки не могут пересекать точку!". Однако и это не является проблемой. Если отрезок, который лежит в статусе, не вертикален, то он сортируется по своей координате <tex>Y</tex>, в которой он пересекается с вертикальной прямой, проведенной через нашу точку (да, это бывшая сканирующая прямая). А вот если отрезок вертикален, то его параметром является как раз ордината "сканирующей точки". <s>Если внимательно подумать, то все будет корректно.</s>Здесь должна быть анимашка, в которой показывается, что все будет корректно.