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