Определение пересечений множества отрезков

Автор Тема: Определение пересечений множества отрезков  (Прочитано 2782 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Тема содержит сообщение с Решением. Нажмите здесь чтобы посмотреть его.

Оффлайн Кирилл ЗахаровАвтор темы

  • ADN OPEN
  • ***
  • Сообщений: 119
  • Карма: 5
Есть ли в API AutoCAD какой-нибудь метод который позволяет рассчитать пересечения множества линейных отрезков, но при этом чтобы сложность этой процедуры была не квадратичной. Например, как в алгоритме Бентли-Оттмана (http://geomalgorithms.com/a09-_intersect-3.html).

Оффлайн Александр Пекшев aka Modis

  • ADN Club
  • *****
  • Сообщений: 1658
  • Карма: 366
  • Отец modplus.org
    • ModPlus
API не должно решать подобных задач - у него задача дать Вам доступ для работы с объектами автокада. А вот реализация таких алгоритмов (что является частным случаем) - это уже ваша задача

Оффлайн Дмитрий Загорулькин

  • ADN
  • *
  • Сообщений: 2531
  • Карма: 735
API не должно решать подобных задач - у него задача дать Вам доступ для работы с объектами автокада.
В целом - да. Но если какие-то механизмы используются для внутренних задач AutoCAD, то они могут быть вынесены и в API.
Есть ли в API AutoCAD какой-нибудь метод который позволяет рассчитать пересечения множества линейных отрезков
Конкретно в этом случае, насколько мне известно, ничего такого нет.

Оффлайн Кирилл ЗахаровАвтор темы

  • ADN OPEN
  • ***
  • Сообщений: 119
  • Карма: 5
что является частным случаем
Попробую сформулировать более общую проблему:
Есть множество любых примитивов, и стоит задача найти пересечения между всеми ними.
Можно ли это сделать более эффективно чем искать пересечения каждого с каждым с помощью метода IntersectWith?

Отмечено как Решение Кирилл Захаров 15-08-2018, 16:29:54

Оффлайн Владимир Шу

  • ADN Club
  • *****
  • Сообщений: 611
  • Карма: 155
    • ПГСу Бложик
Про API ничего не скажу, не встречал, но Вашу задачу можно решить и без API, поищите по форуму слово "RTree" и дальше по ссылкам.

Оффлайн Кирилл ЗахаровАвтор темы

  • ADN OPEN
  • ***
  • Сообщений: 119
  • Карма: 5
Спасибо, Владимир Шу.
Я немного знаком с тем что такое RTree. В частности я использовал библиотеку RBush на C# вот отсюда https://github.com/viceroypenguin/RBush.
Это может помочь, хотя не совсем то, что нужно вроде бы.