Алгоритм Бентли-Оттмана в Haskell?
Итак, я писал библиотеку вычислительной геометрии на Haskell, потому что не мог найти ее на Hackage, и подумал, что было бы весело сделать тем не мение. Тем не менее, я почти неделю застрял на одном конкретном алгоритме, который я просто не могу придать хорошей форме, подобной haskell. Этот алгоритм представляет собой алгоритм Бентли-Оттмана для поиска пересечений в наборе отрезков прямой. Если вы знакомы с алгоритмом, вы можете перейти к последнему абзацу для моей просьбы:)
Я предпочитаю реализовать эту функцию как функцию, которая принимает список сегментов линии и возвращает список точек, и отрезки линии, которые пересекаются в этой точке. Это позволяет нам иметь дело со случаем, когда несколько сегментов пересекаются в одной и той же точке.
bentleyOttmann :: [Segment] -> [(Point, [Segment])]
Алгоритм представляет собой алгоритм развертки линии. Мы представляем себе линию, проходящую по плоскости, выполняющую алгоритмическую работу в различных точках. Точки событий в алгоритме Бентли-Оттмана:
- Начальная конечная точка линейного сегмента.
- Конечная конечная точка линейного сегмента.
- Точка пересечения группы сегментов.
Обратите внимание, что точка события может быть связана с более чем одним сегментом линии более чем одним способом. Чтобы отслеживать, какие сегменты соответствуют каким конечным точкам, я использую карту из пакета контейнеров. Ключи этой карты - это точки, а значения - это списки сегментов, помеченных в зависимости от того, начинаются ли они в этой точке, заканчиваются в этой точке или пересекаются в этой точке.
Линия развертки определяет порядок точек. Представьте себе вертикальную линию, протягивающую самолет, останавливающуюся в точках события для выполнения работы. Точки событий упорядочиваются первыми по их значению x, причем в первую очередь обрабатываются меньшие точки. В общем, это все, что нам нужно. В вырожденных случаях точки событий могут иметь одинаковую координату x. Мы также упорядочиваем по их координатам y, точки событий с меньшими координатами y обрабатываются первыми, если есть связь по координате x.
Так что структура, которую я использую, естественно, является приоритетной очередью. Тот, который я использую, взят из пакета heaps от Hackage.
Какую работу мы выполняем в каждой точке события? Что ж, сначала мы проверяем, какие сегменты связаны с точкой события. Если их несколько, это точка пересечения. Мы можем добавить его в список найденных нами перекрестков.
А вот и сложная часть. Пока мы перемещаемся по плоскости, мы отслеживаем набор сегментов, упорядоченных по отношению к точке, где они пересекают линию развертки . Когда мы обрабатываем точку события, мы сначала удаляем все сегменты, которые заканчивались в этой точке события. Потом,все сегменты, которые пересекались в этой точке , меняются местами в порядке . Наконец, мы добавляем к упорядоченному набору сегменты, которые начинаются в этой точке события. Обратите внимание, что, поскольку все эти сегменты пересекаются в точке события, они должны быть упорядочены относительно линии развертки, которая слегка возмущена впереди.
В каждой точке события мы должны добавлять любые новые точки события, новые пересечения, которые происходят . Поскольку мы отслеживаем относительный порядок сегментов, пересекающих линию сдвига, мы делаем одно из двух:
Если мы поменяли местами два сегмента или добавили новый сегмент, мы находим самый нижний (относительно линии сдвига) измененный сегмент , самый верхний измененный сегмент, и проверить их на пересечение с их непосредственными немодифицированными соседями.
Если мы не поменяли местами или не добавили новые сегменты, то мы, по крайней мере, удалили сегмент, сделав его бывшие соседи теперь смежными. Мы проверяем этих новых соседей на пересечение.
Это ключ к алгоритму Бентли-Оттмана, поскольку мы перемещаемся по плоскости, мы проверяем только новые сегменты-кандидаты с их соседями. Это означает, что мы превосходим наивный алгоритм O (n ^ 2) при относительно небольшом количестве пересечений.
Моя проблема (наконец, извините, это слишком многословный) заключается в следующем: я не знаю, как реализовать это логика заказа. Я не могу использовать Data.Set, потому что порядок меняется при просмотре. Я пытаюсь реализовать свою собственную структуру данных, чтобы отслеживать информацию, но она шероховатая, глючная, возможно неэффективная и уродливая! Я ненавижу уродливый код.
Я знаю, что Haskell - это хороший код. Я также считаю, что если я не могу реализовать алгоритм красивым образом, это означает, что я действительно его не понимаю. Может ли кто-нибудь дать мне представление о том, как правильно реализовать этот алгоритм?
Изменить: Сейчас у меня есть «рабочая» реализация. Я намеревался работать с общим вводом, а также с несколькими сегментами, пересекающимися в одной точке, и вертикальными сегментами. Похоже, что эти входные данные работают с мизерными тестами, которые я провел. Это не работает, когда сегменты перекрываются. Я пока не знаю, как с ними бороться. Буду признателен за информацию о том, как их разместить. В настоящее время моя структура линий развертки отслеживает их в одном и том же узле, но в тестах пересечений будет использоваться только один из них, что может давать противоречивые результаты.
Я использую Data.Set для своей очереди событий, Data.Map для поиск, и реализация красно-черных деревьев с застежками-молниями, которую я взял за основу Окасаки в его книге. Если моему фрагменту недостаточно контекста, я могу добавить больше.
Я был бы признателен за советы по реструктуризации реализации, чтобы она ... менее уродливая. Я не могу сказать, насколько это правильно, и это заставляет меня нервничать.
Код можно найти на hpaste здесь