Прежде чем мы пойдем искать углы, давайте сделаем шаг назад.Что вы пытаетесь сделать?
У меня есть неупорядоченный список горизонтальных / вертикальных сегментов длиной 1, которые строят один или несколько полигонов.Теперь мне нужно найти список всех связанных углов в каждом многоугольнике.
«Поиск» и «неупорядоченные списки» на самом деле не сходятся, как я уверен, вы понимаете!Это верно даже для простых поисков, но это еще хуже для того, что вы делаете, что концептуально ближе к поиску дубликатов, поскольку требует корреляции элементов коллекции друг с другом, вместо того, чтобы проверять каждый из них независимо.
Итак, вы определенно захотите чего-то более структурированного.Одним из вариантов было бы более семантически значимое представление в терминах полных многоугольников, позволяющее простой обход непрерывного периметра, но я предполагаю, что у вас нет этой информации (например, если вы пытаетесь создайте такую структуру здесь).
Теперь, в комментарии вы сказали:
Причина этого в том, что сегменты были сохранены в "Set" sдо того, чтобы удалить перекрывающиеся сегменты.Это представление гарантирует, что существует только один сегмент (x, y) - (x + 1, y).
Это заслуживает дальнейшего рассмотрения.Как работает Data.Set и почему лучше удалять дубликаты, чем неупорядоченный список?Этот последний бит является чем-то вроде раздачи, потому что Data.Set - это в точности упорядоченная коллекция , поэтому, предоставляя каждому элементу уникальное представление, вы получаете комбинированные преимущества автоматического удаления дубликатов и быстрого поиска.
Как уже упоминалось выше, ваша настоящая проблема концептуально похожа на поиск дубликатов;вместо того, чтобы находить перекрывающиеся сегменты, вам нужны соседние.Может ли использование Data.Set помочь вам и здесь?
Увы, не может.Чтобы понять почему, подумайте о том, как работает сортировка.Учитывая два элемента X и Y, существует три возможных сравнения: X Y. Если отдельные смежные элементы отличаются на минимально возможное количество, вы можете безопасно исследовать только те элементы, которые смежны вотсортированная коллекция.Но это не может быть обобщено на линейные сегменты по нескольким причинам, самое простое из которых состоит в том, что до четырех различных элементов могут быть смежными, что не может быть описано в отсортированной последовательности.
Надеюсь, я был достаточно властен с моиминамекает на то, что вам сейчас интересно, как будет выглядеть отсортированная коллекция, которая делает , позволяющая смежным четырем отдельным элементам выглядеть, и позволит ли она легко искать способ, которым Data.Set делает.
Ответ на последний вопрос - да, абсолютно , а ответ на первый: дерево многомерного поиска .Простое двоичное дерево поиска выглядит примерно так:
data Tree a = Leaf | Branch a (Tree a) (Tree a)
... где вы гарантируете, что в любой ветви все значения листьев в левой половине меньше, чем в правой.Простое двумерное дерево поиска вместо этого будет выглядеть примерно так:
data Tree a = Leaf | Branch a (Tree a) (Tree a) (Tree a) (Tree a)
... где каждая ветвь представляет квадрант , сортируя путем сравнения по двум осям независимо.В противном случае он работает так же, как знакомые одномерные деревья поиска, с прямыми переводами многих стандартных алгоритмов, и с учетом определенного сегмента линии вы можете быстро найти любые соседние сегменты.
Редактировать : Оглядываясь назад, я слишком увлекся экспозицией и забыл дать ссылки.Это совсем не новая концепция, и она имеет много существующих вариантов:
То, что я описал, будет называться point Quadtree и является простым расширением бинарного поиска.деревья, как Data.Set.
Та же концепция может быть реализована с регионами вместо дискретных точек с поиском, заканчивающимся в областях, которые либо полностью включены, либо исключены.Это аналогичные расширения попытки , например Data.IntSet.
Вариант, называемый R-деревья , похож на B-деревья иимеют полезные рабочие характеристики для некоторых целей.
Концепции также распространяются и на более высокие измерения.Структуры данных по этим линиям используются для рендеринга и обнаружения столкновений в симуляциях и видеоиграх, пространственных базах данных с поиском «ближайшего соседа», а также в более абстрактных приложениях, о которых вы обычно не думаете геометрически, где разреженные точки данных могут быть отсортированы вдольнесколько осей и некоторое объединенное понятие «расстояние» имеет смысл.
Как ни странно, я не смог найти какой-либо реализации таких структур данных в Hackage, кроме одного неполного и, казалось бы, заброшенного пакета.