Узнать точку пересечения полилинии и блока c#

Автор Тема: Узнать точку пересечения полилинии и блока c#  (Прочитано 18931 раз)

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

Оффлайн DenisАвтор темы

  • ADN OPEN
  • **
  • Сообщений: 63
  • Карма: 2
Здравствуйте.
Извиняюсь,если кто-то эту тему уже поднимал.

У меня есть набор полилиний, которые стыкуются с блоками,хотелось бы узнать как определить какой конкретно блок пересекается с полилинией для того,чтобы вытащить из него имя.
Подскажите пожалуйста,откуда начать копать?

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
Приветствую на форуме!
которые стыкуются с блоками
пересекается с полилинией
Так стыкуются или пересекаются?
Если не вдаваться в детали постановки, то можно использовать метод Entity.IntersectWith для попарной проверки на пересечение полилинии и (габаритного контейнера) вставки блока.
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн DenisАвтор темы

  • ADN OPEN
  • **
  • Сообщений: 63
  • Карма: 2
Правильнее будет все-таки стыкуется.Буду аккуратнее в терминологии.В приложении файл,там есть полилиния и два блока на концах.

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
Правильнее будет все-таки стыкуется.
В том виде как нарисовано в dwg-файле я не вижу способа обрабатывать информацию. Конечные точки полилинии не касаются блоков (т.е. имеется весьма ощутимый зазор). И скорее всего Entity.IntersectWith ничего не даст.
Думаю, что вопрос нужно решать организационно. А именно конечная точка полилинии должна совпадать с точной вставки блока с заданной точностью. Тогда задача упрощается и ускоряется как минимум на порядок.
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн DenisАвтор темы

  • ADN OPEN
  • **
  • Сообщений: 63
  • Карма: 2
То есть та линия, которая выходит из блока, и стыкуется с полилинией в расчет не идет? Получается,что полилинию надо доводить до контура блока и только потом использовать Intersectwith? И костыль по типу координаты одного конца полилинии совпадает с координатами конца линии из блока не пройдет?

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
И костыль по типу координаты одного конца полилинии совпадает с координатами конца линии из блока не пройдет?
Всё зависит постановки задачи. В общем случае (если нет ограничений на типы примитивов в блоке, масштаб по осям вставки блока и т.д.), то мягко говоря будет не слишком просто вычислить координаты линии, находящейся в блоке. И еще придётся пройтись по всем вставкам блоков, найти в них все линии, найти для каждой линии характерные точки и преобразовать в их в МСК, а затем их сравнивать с координатами вершин всех полилиний.
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн DenisАвтор темы

  • ADN OPEN
  • **
  • Сообщений: 63
  • Карма: 2
Спасибо за ответ.
В продолжение решил попробовать написать код.Вопрос следующий: я получил все блоки как block table record, как проверить,что они пересекаются.Я просто полный новичок в этом и такое api меня пугает.
Заранее спасибо за подсказки!

Код - C# [Выбрать]
  1. using (Transaction acTrans = acCurDb.TransactionManager.StartTransaction())
  2.             {
  3.                
  4.                 BlockTable acBlkTble;
  5.                 acBlkTble = acTrans.GetObject(acCurDb.BlockTableId, OpenMode.ForRead) as BlockTable;
  6.                 foreach (ObjectId objId in acBlkTble)
  7.                 {
  8.                     BlockTableRecord btr;
  9.                     btr = acTrans.GetObject(objId, OpenMode.ForRead) as BlockTableRecord;
  10.                     acDoc.Editor.WriteMessage("\n" + btr.Name);
  11.                     list_bl.Add(btr);
  12.                 }
  13.                 acTrans.Commit();
  14.             }
  15.  
  16.  
  17.                         foreach (Entity block in list_bl)
  18.                         {
  19.                             Point3dCollection pts = new Point3dCollection();
  20.                             block.IntersectWith(poly,Intersect.ExtendArgument,pts,0,0);
  21.  
  22.                             if (pts.Count != 0)
  23.                             {
  24.                                 sheet1.addCell(new Label(3, 1, block.BlockName));
  25.                             }
  26.                         }
« Последнее редактирование: 28-06-2015, 21:25:41 от Александр Ривилис »

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
1. Начни с того, что прочитай мою подпись по поводу форматирования кода на форуме.
2. Я вижу какой-то совершенно непонятный для меня обрывок кода.
3. Проверку на пересечение нужно делать не для BlockTableRecord, а для BlockReference (т.е. для вставок блоков).
4. Один из вариантов - использование метода BlokReference.Explode и проверка на пересечение с коллекцией полученных примитивов. Есть правда ограничение, когда масштабные коэффициенты по X,Y,Z не равны.
« Последнее редактирование: 28-06-2015, 21:27:58 от Александр Ривилис »
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн Дима_

  • ADN Club
  • ****
  • Сообщений: 473
  • Карма: 66
Тут в общем случае все достаточно не просто. По хорошему надо проиндексировать все габаритные контейнеры необходимых блоков (BoundingBox), после чего вытянуть в сторону удлинения все (или только нужные) классы от Curve и проверять на принадлежность крайним точка индексов блоков, после чего уже запускать функцию сверки (касается? не касается?). Но и это годиться только для не сильно насыщенных чертежей - если тысячи линий надо проверить к тысячам блоков (по сути проверяется каждая к каждой), то тогда неплохо бы изучить R-деревья (писать реализацию не обязательно - готовые реализации в сети я точно видел) и индексировать по ним. В любом случае задачу следует хорошенько конкретизировать перед "кодовством".
з.ы. есть еще api автокада по выбору в заданных областях - но они работают только с тем что видно на экране и то в определенном масштабе - в общем не надежно.

Оффлайн trir

  • ADN Club
  • ****
  • Сообщений: 470
  • Карма: 63
http://sourceforge.net/projects/cspatialindexrt/
каноничная реализация...

Оффлайн DenisАвтор темы

  • ADN OPEN
  • **
  • Сообщений: 63
  • Карма: 2
Спасибо за ответы! Про код извиняюсь,надеюсь,что в следующий раз справлюсь)

Задачу я реализовал.Нашел точки пересечения блоков и полилиний.И это даже работает.Единственное,что сейчас все работает тупо с перебором блоков.Буду искать способ ускорить программу,возможно при помощи R-деревьев.

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
Единственное,что сейчас все работает тупо с перебором блоков
Перебирать придётся в любом случае, но Дима_ подсказал как можно перебирать быстрее - пройтись по всем вставкам блоков в чертеже и сохранить в коллекции их BoundigBox'ы. Это может очень значительно ускорить процесс. Ну а следующая оптимизация - деревья.
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн DenisАвтор темы

  • ADN OPEN
  • **
  • Сообщений: 63
  • Карма: 2
Сейчас я просто добавляю BlockReferences в List. Потом делаю IntersectWith. Это не то же самое,что BoundingBoxes?
Буду разбираться с R-trees.Надеюсь разберусь.
Спасибо за подсказки!

Оффлайн Дима_

  • ADN Club
  • ****
  • Сообщений: 473
  • Карма: 66
Это не то же самое,что BoundingBoxes?
Нет. Вы к каждому блоку запускаете долгую проверку на пересечение - а ее нужно запускать если только точка находиться в габаритах блока. С деревьями можно особо и не разбираться - а нагуглить готовые.
На всякий случай - если вдруг программный проект связан с SQL DB- практически во всех СУБД есть пространственные индексы основанные на r-деревьях.
з.ы. вот только в автокаде их почему-то нет?? Хотя "внутри" они скорее всего таки используются.

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
Это не то же самое,что BoundingBoxes?
Нет. BoundingBox (точнее Entity.GeometricExtents) позволяет получить параллелепипед со сторонами параллельными осям X Y Z мировой системы координат (МСК), в который вписывается (полностью влезает) примитив.
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн DenisАвтор темы

  • ADN OPEN
  • **
  • Сообщений: 63
  • Карма: 2
Это уже не совсем по сабжу,но может быть вы сможете подсказать.
Я попытался сделать так:
1)Просканировать чертеж и собрать все блоки в List.
2)При помощи R-tree я создаю Коллекцию прямоугольников, на вход которой я подаю точки,полученные следующим образом:
Код - C# [Выбрать]
  1. Entity.GeometricExtents.MinPoint.X
3)Нахожу прямоугольник,который включает в себя точку начала полилинии.

Дальше я застрял.Идеальный вариант был бы еще узнать номер этого прямоугольника в коллекции,чтобы получить доступ к соответствующему блоку и вытащить из него нужные мне атрибуты.
Вытаскивать атрибуты я научился.
Может быть кто-то подскажет,как найти индекс прямоугольника?
Заранее спасибо!

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
Может тип коллекции выбрал неудачный? Наверное нужно что-то типа Dictionary<Extents3d, ObjectId>, где Extents3d - габариты вставки блока, а ObjectId - его идентификатор.
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн trir

  • ADN Club
  • ****
  • Сообщений: 470
  • Карма: 63
Можно создать класс, который будет содержать блок или ObjectId, а также умеет создавать MBR и хранится в дереве

Оффлайн DenisАвтор темы

  • ADN OPEN
  • **
  • Сообщений: 63
  • Карма: 2
Я уже возненавидел этот самый Автокад.
Я действительно создал коллекцию Dictionary следующим образом:
Код - C# [Выбрать]
  1. BlockReference ent = (BlockReference)obj;
  2.                                 list_bl.Add(ent);
  3.  
  4.                                 float xmin = (float)ent.GeometricExtents.MinPoint.X;
  5.                                 float ymin = (float)ent.GeometricExtents.MinPoint.Y;
  6.                                 float xmax = (float)ent.GeometricExtents.MaxPoint.X;
  7.                                 float ymax = (float)ent.GeometricExtents.MaxPoint.Y;
  8.  
  9.                                 RTree.Rectangle rect = new RTree.Rectangle(xmin, ymin, xmax, ymax, 0, 0);
  10.                                 dict.Add(rect,number++);
  11.                                
  12.                                 tree.Add(rect,rect);
Где list_bl это List с блоками на чертеже, для каждого блока создается Прямоугольник,который потом добавляется в коллекцию. nember - это ключ,который нужен для извлечения номера.

Оффлайн DenisАвтор темы

  • ADN OPEN
  • **
  • Сообщений: 63
  • Карма: 2
Случайно отправилось.
После этого я нахожу самый близкий блок к точкам начала и конца полилинии. Дальше я вытаскиваю номер этого блока,вывожу в эксель и кажется,что все правильно,а получить имя блока у меня уже не получается.
 Пытаюсь следующим образом:
         
Код - C# [Выбрать]
  1. Autodesk.AutoCAD.DatabaseServices.AttributeCollection attCol = list_bl[number].AttributeCollection;
  2.                                  foreach (ObjectId attId in attCol)
  3.                                  {
  4.                                      AttributeReference attRef = (AttributeReference)acTrans.GetObject(attId, OpenMode.ForRead);
  5.                                      if (attRef.Tag.Equals("SYSNAME"))
  6.                                      {
  7.                                          list_nm.Add(attRef.TextString);
  8.                                          sheet1.addCell(new Label(7, columns + i - 1, list_nm[0]));
  9.                                          list_nm.RemoveAt(0);
  10.                                      }
  11.                                  }
  12.                              }
Может быть вы увидите что-то,что я пропустил?Лежащее на самом верху. Я пытаюсь вытащить информацию по тегу SYSNAME.

Оффлайн trir

  • ADN Club
  • ****
  • Сообщений: 470
  • Карма: 63
Для работы с деревом можно создать такой класс
Код - Visual Basic [Выбрать]
  1. Public Class MyClass1
  2.  
  3.     Public wObjID As Objectid
  4.     Public wRrect As Rectangle
  5.  
  6.     Public Sub New(nEnt As Entity)
  7.         Me.wObjID = nEnt.ObjectId
  8.         wRrect = MyClass1.GetRect(nEnt)
  9.     End Sub
  10.  
  11.     Public Shared Function GetRect(nEnt As Entity) As Rectangle
  12.         If nEnt.Bounds IsNot Nothing Then
  13.             Dim wExt As Extents3d = nEnt.Bounds
  14.             Return New Rectangle(wExt.MinPoint.X, wExt.MinPoint.Y, wExt.MinPoint.Z, wExt.MaxPoint.X, wExt.MaxPoint.Y, wExt.MaxPoint.Z)
  15.         Else
  16.             Return Nothing
  17.         End If
  18.     End Function
  19.  
  20.     Public Sub AddToTree(wTree As RTree(Of MyClass1))
  21.         wTree.Add(Me.wRrect, Me)
  22.     End Sub
  23.  
  24. End Class

Оффлайн DenisАвтор темы

  • ADN OPEN
  • **
  • Сообщений: 63
  • Карма: 2
Разобрался,все спасибо за помощь!!
Класс я приблизительно такой и создал.Проблема была в том,что почему-то есть разница в номере конкретного блока между способом перебора и способом дерева.
На старом чертеже эта разница была постоянной и равнялась 362, после переноса на новый чертеж все пришло в норму и способ дерева стал работать.Скорость его потрясает,практически мгновенно.
Еще раз спасибо!

Оффлайн Дима_

  • ADN Club
  • ****
  • Сообщений: 473
  • Карма: 66
Проблема была в том,что почему-то есть разница в номере конкретного блока между способом перебора и способом дерева.
Индексировать по порядковому номеру - ихмо это очень плохая идея - лишнию сущность вводите - бесполезную. Либо ObjectId с дальнейшим извлечением объекта из транзакции (надежный метод - при "правильной" реализации), либо (если памяти не жалко) сразу объект блока - но можно попасть на переполнение памяти с "зависоном" или фаталом. У вас получается сложены худшие стороны обоих методов.

Оффлайн DenisАвтор темы

  • ADN OPEN
  • **
  • Сообщений: 63
  • Карма: 2
Поменял на ObjectId.Действительно,все заработало и на старом чертеже!

Оффлайн Вильдар

  • ADN Club
  • ****
  • Сообщений: 405
  • Карма: 77
  • Skype: vildar82
Denis, можешь показать код работы с деревьями (RTree правильно?). Спасибо.
Попробовал код из этого проекта https://sourceforge.net/projects/cspatialindexrt/
Норм получилось.
Создаю "дерево" преобразуя все Extents3d из автокада в объекты Rectangle (из проекта по ссылке):
Код - C# [Выбрать]
  1.          RTree<Area> rtree = new RTree<Area>();          
  2.          foreach (Area area in _areas)
  3.          {
  4.             Rectangle rectTree = new Rectangle(area.Bounds.MinPoint.X, area.Bounds.MinPoint.Y,
  5.                                                area.Bounds.MaxPoint.X, area.Bounds.MaxPoint.Y, 0, 0);
  6.             rtree.Add(rectTree, area);
  7.          }
Потом получаю области в нужной точке
Код - C# [Выбрать]
  1.             Point p = new Point(location.X, location.Y, 0);
  2.             List<Area> areas = rtree.Nearest(p, 300);
Работает супер.
« Последнее редактирование: 14-10-2015, 18:09:25 от vildar82 »

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
Смущает в этом коде использование float вместо double, что должно сильно снижать точность.
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн Вильдар

  • ADN Club
  • ****
  • Сообщений: 405
  • Карма: 77
  • Skype: vildar82
Да, я заменил все float на double. Вроде ничего не сломал  ;D

Оффлайн DenisАвтор темы

  • ADN OPEN
  • **
  • Сообщений: 63
  • Карма: 2
Извините за долгий ответ.
Только добрался до компьютера после командировки.
Код очень похожий у меня,так что все то,что я знаю,ты уже написал!
Еще раз извини за то,что не успел ответить

Оффлайн Вильдар

  • ADN Club
  • ****
  • Сообщений: 405
  • Карма: 77
  • Skype: vildar82
Вначале думал что просто не получиться использовать rtree. Но оказалось, что использовать его просто. Только непонятно как он работает  :o

Оффлайн trir

  • ADN Club
  • ****
  • Сообщений: 470
  • Карма: 63
читай

Обратите внимание, что приведённая мной реализация RTree работает только в 2D, хотя её можно расширить и на 3D! А при большом желании и на ND. И вообще это порт с Джавы, классического алгоритма Гутмана (там даже в комментариях есть цитаты из статьи)

https://habrahabr.ru/post/224965/

Оффлайн RevitTormentor

  • ADN OPEN
  • ***
  • Сообщений: 162
  • Карма: 6
если только точка находиться в габаритах блока.

А как проверить что точка в габаритах блока?

Есть коллекция BoundingBox. Как проверить что точка попала в это параллелепипед

Код - C# [Выбрать]
  1. .Nearest(p, 300);
- это оно?

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

  • ADN
  • *
  • Сообщений: 2531
  • Карма: 735
Есть коллекция BoundingBox. Как проверить что точка попала в это параллелепипед
Можно чисто геометрически: x1 <= X <= x2, y1 <= Y <= y2, z1 <= Z <= z2. Тут X, Y, Z - координаты проверяемой точки. x1, y1, z1 - минимальная точка BoundingBox. x2, y2, z2 - максимальная точка BoundingBox.

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
Можно чисто геометрически: x1 <= X <= x2, y1 <= Y <= y2, z1 <= Z <= z2. Тут X, Y, Z - координаты проверяемой точки. x1, y1, z1 - минимальная точка BoundingBox. x2, y2, z2 - максимальная точка BoundingBox.
Наверное это самый оптимальный и быстрый способ. Можно еще через BoundBlock3d, у которого есть метод Contains.
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн RevitTormentor

  • ADN OPEN
  • ***
  • Сообщений: 162
  • Карма: 6
Можно чисто геометрически: x1 <= X <= x2, y1 <= Y <= y2, z1 <= Z <= z2. Тут X, Y, Z - координаты проверяемой точки. x1, y1, z1 - минимальная точка BoundingBox. x2, y2, z2 - максимальная точка BoundingBox.


Хотел уточнить на картинке Красным например объект. Его параллелепипед будет фиолетовым или голубым? Или вообще другой конфигурации?
Если фиолетовым, то зелёная точка попадёт мимо объекта по условиям x1 <= X <= x2, y1 <= Y <= y2 ?

Или я не прав?




Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
Его параллелепипед будет фиолетовым или голубым?
А что у тебя фиолетовый и голубой - это параллелепипеды? BoundingBox - это прямоугольный параллелепипед, со сторонами параллельными осям координат: 
Прямоугольный параллелепипед — Википедия

В твоём случае:



Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн RevitTormentor

  • ADN OPEN
  • ***
  • Сообщений: 162
  • Карма: 6
Кто ж знает. Иногда называют, что-то чем-то, а по факту это не соответствует определению.  Или соответствует, но не совсем. Поэтому я и предположил, что параллелепипед это просто контур, иначе не понятно. Я ищу находится ли точка в объекте, надо сравнивать с BoundingBox объекта. А получается зелёная точка попадает в BoundingBox, а в объекте она не находится.

В чём подвох.

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
В чём подвох.
Подвоха здесь никакого нет. В твоём случае задача совершенно другая. И вот когда ты сможешь сформулировать задачу - тогда станет понятно как её решать.
Пока же я догадываюсь (судя по картинке), что у тебя есть штриховка и тебе нужно определить попадает ли точка внутрь штриховки или нет. Такая задача решается другим способом. Нужно найти контур штриховки (если она без отверстий - внутренних контуров) и определить пересекает ли любой луч из точки контур штриховки или нет. Пересечений может быть несколько - если число пересечений нечетное, то точка внутри штриховки, если 0 или четное - вне штриховки. Это упрощенный вариант. Могут быть нюансы.
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн RevitTormentor

  • ADN OPEN
  • ***
  • Сообщений: 162
  • Карма: 6
Моя задача такая - быстро узнать входит ли любая точка из коллекции точек в контур любой полилинии из коллекции полилиний.

На стадии тестирования, когда точек мало и полилиний мало всё работает быстро с кодом с форума, называется вроде MakeCountur команда. Там или попала точка на контур или в контур или за контуром. Шикарно, но всё будет плохо, когда будет "реальный" рабочий файл.
Начал искать варианты: наткнулся Rtree и BoundingBox. И что получается Rtree прямоугольники, которые также могут быть не по границам полилинии, и BoundingBox также не по границам объекта.
Теперь получается надо сначала коллекцию Регионов создавать, а потом искать входит ли точка в эту коллекцию?
Наверное да.

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
Из всего множества BoundingBox для всех полилиний ты должен найти подмножество, в которые входит точка. А после этого определить входит ли точка реально в контур, а не только в его BoundingBox. Всё!
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн trir

  • ADN Club
  • ****
  • Сообщений: 470
  • Карма: 63
просто определить принадлежность точки полигону - это очень дорогая операция, а принадлежность BoundingBox - дешёвая

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

  • ADN Club
  • *****
  • Сообщений: 1658
  • Карма: 366
  • Отец modplus.org
    • ModPlus
просто определить принадлежность точки полигону - это очень дорогая операция
Если многоугольник выпуклый, то определить принадлежность точки достаточно просто - Учёт числа пересечений. В ссылке описано как раз. Просто пускаете луч в одну сторону из точки - если пересек многоугольник четное число раз, значит точка снаружи, если нечетное - точка внутри

Оффлайн trir

  • ADN Club
  • ****
  • Сообщений: 470
  • Карма: 63
Цитировать
Если многоугольник выпуклый, то определить принадлежность точки достаточно просто - Учёт числа пересечений. В ссылке описано как раз. Просто пускаете луч в одну сторону из точки - если пересек многоугольник четное число раз, значит точка снаружи, если нечетное - точка внутри
надо определить пересечения со всеми гранями полигона - а если их миллион?
а определение принадлежности к BoundingBox - фиксированное количество логических операций!
тут O(n) против O(1)

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

  • ADN Club
  • *****
  • Сообщений: 1658
  • Карма: 366
  • Отец modplus.org
    • ModPlus
trir, зависит от задачи конечно-же. Например, для треугольника вариант с BoundingBox может дать ой какие неверные результаты. Причем, чуть ли не с 50% погрешностью.
А алгоритмическая сложность O(n) тут явно будет незаметна, на мой взгляд. Эти вычисления достаточно просты и происходят быстро

Оффлайн trir

  • ADN Club
  • ****
  • Сообщений: 470
  • Карма: 63
O(n) для одного полигона - умножь на количество полигонов
там разница набегает очень значительная

Цитировать
Например, для треугольника вариант с BoundingBox может дать ой какие неверные результаты. Причем, чуть ли не с 50% погрешностью.
так с помощью BoundingBox мы делаем лишь первичную фильтрацию, отсеиваем заведомо ложные варианты. А потом уже применяем нормальные проверки

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
Если многоугольник выпуклый, то определить принадлежность точки достаточно просто - Учёт числа пересечений.
Не важно выпуклый или не выпуклый.
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение