Nano Hash - криптовалюты, майнинг, программирование

Алгоритм Бентли-Оттмана для двух групп отрезков прямых

Алгоритм Бентли-Оттмана используется для вычисления пересечения отрезков прямой.

Однако вместо того, чтобы находить точки пересечения всех линий между собой, я хочу найти точки пересечения между двумя группами линий. Это означает, что для каждой строки в группе строк A я хочу знать точки пересечения между этими линиями и линиями в группе B.

Могу ли я в любом случае расширить для этого алгоритм Bentley-Ottmann? У меня уже реализован существующий алгоритм Бентли-Оттмана ( в библиотеке CGAL), и я не собираюсь его изменять. Однако я очень хочу найти способы его повторного использования и расширения.

Изменить: любые другие алгоритмы (не обязательно основанные на Bentley-Ottmann) приветствуются. Было бы лучше, если бы эти алгоритмы уже были реализованы в существующей библиотеке.

algorithm geometry computational-geometry line-intersection
29.12.2010

Ответы:


1

Вы можете найти все пересечения между всеми строками в A+B, а затем удалить пересечения между строками в одном наборе. Вы не сильно увеличиваете сложность, и это позволяет вам использовать библиотечную функцию CGAL без изменений, используя только простую функцию-оболочку.

30.12.2010
  • @ Спасибо, marcog, связанный с этим вопрос: есть ли другой алгоритм, который делает это? Желательно, чтобы он находился в существующей библиотеке вычислительной геометрии. 30.12.2010
  • @Ngu Я не знаю ничего такого же эффективного. Ваше добавленное условие не облегчает решение. Даже если вы попытаетесь адаптировать bentley-otterman, вам все равно придется обрабатывать события, когда линии из одного и того же набора пересекаются, чтобы отсортировать их по y. 30.12.2010

    • 2

    Там, где Bentley-Ottman хранит дерево отрезков, упорядоченных по их текущему положению по вертикали, не могли бы вы сохранить два дерева, по одному для групп A и B? Затем, когда исходный алгоритм проверяет соседей выше и ниже текущей точки, вы должны проверять соседа A выше с соседом B ниже, и наоборот.

    Это основано на беглом просмотре статьи в Википедии; Я не писал много геометрического кода в последнее десятилетие.

    02.02.2011

    3

    Добавление этого ответа для полноты, хотя это может быть не самый эффективный метод для 2 измерений.

    В 3D-графике это обычно для 2 KD-деревьев, которые можно использовать для обнаружения всех перекрывающихся узлов (можно использовать для логических операций над геометрией).

    Рабочий пример (код C). https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b$1089

    Если есть много небольших сегментов (например, путь нарисованной от руки линии), это будет достаточно эффективно. Однако, если есть много длинных ребер (например, пикапы)... это будет плохо работать, и вы захотите разделить конечные узлы в дереве BVH, чтобы повысить производительность. Однако, если это так, вероятно, лучше использовать другой метод, предложенный в других ответах.

    02.08.2015

    4

    Да, алгоритм Бентли-Оттмана может быть расширен для этого наряду с другими методами.

    В литературе описанная вами задача похожа на сообщение о пересечении красных и синих линий.

    Вот статья, расширяющая развертку BO до оптимального алгоритма. http://www.cs.unc.edu/~snoeyink/demos/rbseg/jcdcg25.pdf

    Я бы не согласился с утверждением @marcog о сложности. В связанной статье утверждается оптимальное время O (n log (n + k)), если вы отфильтруете пересечения, вам придется выполнить развертку BO на всех линиях, и это будет ((n + k) log n).

    Существуют и другие подобные алгоритмы, которые могут не требовать сложных структур данных http://www.cs.swarthmore.edu/~adanner/cs97/s08/pdf/palazzi93counting.pdf

    Для меньшего количества ребер и меньшего количества пересечений между ребрами решение в ответе @marcog может работать хорошо. (Вот пример из CGAL http://doc.cgal.org/latest/Arrangement_on_surface_2/Arrangement_on_surface_2_2consolidated_curve_data_8cpp-example.html).

    Если вам нужно обрабатывать сложные полигоны (данные ГИС и т. д.) или вам нужен общий алгоритм, этот класс алгоритмов может оказаться полезным.

    10.01.2016
    Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..