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