|
||
| Правила | Регистрация | Пользователи | Поиск | Сообщения за день | Все разделы прочитаны | Справка по форуму | Файлообменник | |
|
Поиск в этой теме |
02.12.2010, 21:36 | #1 | |
Как определить, лежит ли точка внутри контура
Регистрация: 22.01.2010
Сообщений: 311
|
||
Просмотров: 32727
|
|
||||
Если сумма площадей треугольников, образованных сегментом замкнутой полилинии и точкой равна площади замкнутой полилинии, то точка принадлежит внутреннему пространству. Все остальное - внешнему.
Есть одно исключение - это когда несколько сегментов полилинии образуют кривую закорючку. Если и с закорючками надо бороться, то есть решение. |
||||
|
||||
Регистрация: 22.01.2010
Сообщений: 311
|
Глянь картинку.
Мне в голову пришло только одно решение: из точки отрисовать 4 отрезка единичной длины под углами 0, 90, 180, 270 град. и затем 4 раза дать команду удлинить до контура. Если это 4 раза сработает, то точка внутри контура. Похоже на правду? Последний раз редактировалось swkx, 02.12.2010 в 22:32. |
|||
|
||||
Теория:
Проверка принадлежности точки многоугольнику: Метод трассировки луча Практика: Принадлежность точки криволинейному контуру Принадлежность точки линейному контуру A point inside a region LISP. Проверка вхождения точки в контур ссылка на dwg.ru http://forum.dwg.ru/showthread.php?p...62#post1538162
__________________
Как использовать код на Лиспе читаем здесь Последний раз редактировалось VVA, 26.04.2017 в 18:53. Причина: актуализирована ссылка |
||||
|
||||
Регистрация: 22.01.2010
Сообщений: 311
|
VVA,
спасибо за ссылочки. Правда, я суть алгоритма не ухватил. Поясни, если можешь, вот это, до меня не доходит: "...Точка лежит в контуре, если некий луч пересекает отрезки контура нечетное количество раз..." ... Всё, не нужно пояснять, дошло. |
|||
|
||||
геологоразведка, строительство Регистрация: 14.10.2003
Магадан
Сообщений: 311
|
В дополнение к последней ссылке VVA (пост №6).
Мои функции лучше брать из первоисточника. http://geol-dh.ru/spds/function.html
__________________
Лень - великий двигатель прогресса! |
|||
|
||||
самый простой способ - находишь ближайшую точку на полилинии к твоей точке vlax-curve-* тебе в помощь. Далее находишь производную в этой точке - вектор направленности. Зная направление обхода полилинии (по часовой или против часовой) можно определить угол +90 или -90...
частный случай, когда ближайшая точка в вершине полилинии - нужно рассматривать два вектора - конец одного сегмента и начало следующего. Удачи!
__________________
Чем гениальнее ваш план, тем меньше людей с ним будут согласны. /Сунь Цзы/ |
||||
|
||||
Если через построения, то можно еще одним способом:
1. Из координат вершин полилинии формируешь список точек lst 2. В интересующем тебя месте рисуешь примитив "точка" e1 3. ssget'ом с опцией "_CP" (секущий многоугольник) формируешь набор 4. Проверяешь, попал ли примитив "точка" в набор. Если да - точка внутри контура, если нет - то и точки внутри нет
__________________
Как использовать код на Лиспе читаем здесь Последний раз редактировалось VVA, 30.05.2016 в 23:22. Причина: орфоргафия |
||||
|
||||
- Регистрация: 24.07.2005
Москва
Сообщений: 1,335
|
Цитата:
|
|||
|
||||
swkx, "Метод трассировки луча" у меня уже работает лет так надцать и зарекомендовал себя как надежный и устойчивый алгоритм. Советую остановиться на нем.
__________________
Как использовать код на Лиспе читаем здесь |
||||
|
||||
Ничего подобного, этот алгоритм отлично работает с невыпуклыми контурами, в том числе имеющими дуговые сегменты! Другое дело, что действительно, этот алгоритм не подходит для контуров имеющих самопересечения. В моих проектах обрабатываются контура, которые в дальнейшем пойдут на станки чпу - вертикальные фрезеры, другими словами, постпроцессоры станков чпу не работают с самопересекающимися контурами - у контура должна быть только одна сторона внешняя и одна внутренняя...
__________________
Чем гениальнее ваш план, тем меньше людей с ним будут согласны. /Сунь Цзы/ |
||||
|
||||
Продуман Регистрация: 22.02.2007
Питер
Сообщений: 2,840
|
То Евгений - я если честно не очень понял принцип алгоритма - но ихмо исходных данных маловато для вычисления и на "сложноневыпуклых" не пройдет. Если можно объяни более подробно свой метод.
Автору - если подразумеваются фигуры "сложновыпуклые" или еще и с самопересечениями - я бы вначале трангулировал-бы фигуру - а затем проверил бы треугольники.
__________________
Когда в руках молоток все вокруг кажется гвоздями. |
|||
|
||||
Цитата:
например у нас есть квадрат и точка внутри: 1. проверяем направление обхода вершин в контуре - например получили против часовой стрелки 2. используя vlax-curve-getclosestpointto находим ближайшую точку на контуре (ближайшую от проверяемой точки) 3. используя vlax-curve-getFirstDeriv получаем первую производную контура в найденой точке на контуре, другими словами, мы получаем вектор направленности контура в данной точке, если сегмент дуговой, то вектор идет по косательной, если прямолинейный, то вдоль сегмента. 4. находим углы направления вектора первой производной и между тестовой точкой и ближайшей точкой на контуре, чтоб узнать угол между этими направлениями В нашем случае, мы получаем 90 градусов или если без перевода в градусы то (/ pi 2) Если бы точка была снаружи, то угл был бы отрицательным, если контур по часовой стрелке, то результаты надо инвертировать т.е. внутри отрицательный и снаружи положительный. Это описание, если ближайшая точка лежит на сегменте, если ближайшей точкой является вершина полилинии, то чуть сложнее, но если вы нарисуете, то сами поймете - ничего сложного! Хочу пояснить еще один момент, если у контура несколько последовательных вершин совпадают, т.е сегмент имеет нулевую длину, то угол будет всегда равен нулю и необходимо искать последнюю вершину в списке совпадающих.
__________________
Чем гениальнее ваш план, тем меньше людей с ним будут согласны. /Сунь Цзы/ |
||||
|
||||
Цитата:
Направление сегмента можно получить из вектора направленности - результат работы функции vlax-curve-getFirstDeriv, т.е. угол между двумя точками '(0. 0.) и вектором Направление на ближайшую точку контура, вообще просто - угол между двумя точками - тестовой и ближайшей Угол между двумя углами, вообще просто - вычел из одного другой и получил нужный угол, только проверить чтоб был в диапазоне -180/+180 градусов...
__________________
Чем гениальнее ваш план, тем меньше людей с ним будут согласны. /Сунь Цзы/ |
||||
|
||||
>Евгений, все таки наверное алгоритм для выпуклых контуров
Ну и алгоритм поста #20 в коде (для выпуклых контуров) Код:
__________________
Как использовать код на Лиспе читаем здесь |
||||
|
||||
VVA, я же описал, если ближайшая точка в вершине, то нужно рассматривать вектор в конце предыдущего сегмента и в начале следующего после ближайшей вершины...
Те же проблемы будут и с выпуклым контуром, если ты укажешь точку снаружи, напротив вершины, т.е. ближайшей будет именно вершина контура.
__________________
Чем гениальнее ваш план, тем меньше людей с ним будут согласны. /Сунь Цзы/ |
||||
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
Цитата:
Цитата:
|
|||
|
||||
А у меня другая дилемма, как для команды-boundary найти точку внутри двух контуров красного и синего, чтоб получить зелёный?
__________________
Почему все вдруг становятся умными, когда уже не надо? |
||||
|
||||
Регистрация: 18.12.2010
Сообщений: 5,047
|
|
|||
|
||||
Цитата:
__________________
Почему все вдруг становятся умными, когда уже не надо? |
||||
|
||||
Disney,
Как вариант 1. Найти центроид одного контура 2. Проверить, находится ли он внутри другого 3. Если нет - поменять контура местами 4. Если опять нет - ? ----- добавлено через ~17 мин. ----- Еще один алгоритм 1. 1-й контур преобразовать в region 2. 2-й контур преобразовать в регион 3. Найти пересечение областей 4. У полученного контура найти центроид Что-то похожее было здесь Там надо нарисовать замкнутую полилинию, задать размеры отверствия и полученное отверствие "посадить" на один из сегментов
__________________
Как использовать код на Лиспе читаем здесь |
||||
|
||||
Цитата:
Я думал о подобном, взять центр из GetBoundingBox.
__________________
Почему все вдруг становятся умными, когда уже не надо? Последний раз редактировалось Disney, 03.03.2015 в 12:58. |
||||
|
||||
Moderator
LISP, C# (ACAD 200[9,12,13,14]) Регистрация: 25.08.2003
С.-Петербург
Сообщений: 39,772
|
Не прокатит. Возьми фигуру типа "полумесяц"....
__________________
Моя библиотека lisp-функций --- Обращение ко мне - на "ты". Все, что сказано - личное мнение. |
|||
|
||||
Я в #32 добавил еще один вариант, преобразовать в области, найти пересечение контуров и ... мне кажется этого достаточно ?
__________________
Как использовать код на Лиспе читаем здесь |
||||
|
||||
Цитата:
А оказалось ты о команде Пересечение , я привык её к 3D телам применять, а то что она с областями сработает и не знал. Вообще ни когда области не использовал и не понимал для чего они... я и сейчас не понимаю, но в моём случаи пригодиться. Спасибо! ----- добавлено через ~18 ч. ----- Всё получилось. Но теперь как мне достать координаты вершин получившейся области?
__________________
Почему все вдруг становятся умными, когда уже не надо? |
||||
|
||||
Разбил область на линии, и уже из них выудил координаты.
----- добавлено через 20 сек. ----- Ну и как ты её решил?
__________________
Почему все вдруг становятся умными, когда уже не надо? |
||||
|
||||
Все правильно. Ссылку на пример я приводил в #32
Цитата:
Код:
__________________
Как использовать код на Лиспе читаем здесь |
||||
|
||||
строю, ломаю Регистрация: 03.04.2008
Украина
Сообщений: 5,515
|
подниму темку, чтоб не создавать новую... Собственно сабж: Допустим есть некий контур (р1 р2 ... рn) и есть прямоугольник, заданный списком (list (list x y) width height). Необходимо определить, лежит ли прямоугольник внутри контура, находится ли за его пределами или пересекает контур, причем прямоугольник может иметь вершины на границе контура. Это меня больше всего смущает, так как проверка принадлежности вершин прямоугольника контуру не работает
|
|||
|
||||
Moderator
LISP, C# (ACAD 200[9,12,13,14]) Регистрация: 25.08.2003
С.-Петербург
Сообщений: 39,772
|
Контур и прямоугольник существуют в чертеже или они "виртуальные"?
__________________
Моя библиотека lisp-функций --- Обращение ко мне - на "ты". Все, что сказано - личное мнение. |
|||
|
||||
Регистрация: 18.12.2010
Сообщений: 5,047
|
|
|||
|
||||
строю, ломаю Регистрация: 03.04.2008
Украина
Сообщений: 5,515
|
Цитата:
не ругайся, можешь популярно на пальцах объяснить метод? |
|||
|
||||
Moderator
LISP, C# (ACAD 200[9,12,13,14]) Регистрация: 25.08.2003
С.-Петербург
Сообщений: 39,772
|
Если у тебя контур не содержит дуговых сегментов, то чем не устраивает inters ?
__________________
Моя библиотека lisp-функций --- Обращение ко мне - на "ты". Все, что сказано - личное мнение. |
|||
|
||||
Moderator
LISP, C# (ACAD 200[9,12,13,14]) Регистрация: 25.08.2003
С.-Петербург
Сообщений: 39,772
|
В таком случае inters возвращает точку, лежащую на прямой, насколько я помню.
P.S. Только что проверил - так и есть: Код:
__________________
Моя библиотека lisp-функций --- Обращение ко мне - на "ты". Все, что сказано - личное мнение. |
|||
|
||||
Продуман Регистрация: 22.02.2007
Питер
Сообщений: 2,840
|
Если это не метод который надо крутить миллионами раз друг к другу - то создаешь две области (Region) и делаешь вычитание их копий. Если кто-то пропадает - то он внутри другого. Остаются как есть - без пересечения иначе - пересекаются.
з.ы. случайно не на "сетку" режешь? в конце темы код и описание
__________________
Когда в руках молоток все вокруг кажется гвоздями. |
|||
|
||||
строю, ломаю Регистрация: 03.04.2008
Украина
Сообщений: 5,515
|
Цитата:
Если по хорошему не получится, придется рисовать и удалять, но мне это не очень нравится, должен быть математический путь |
|||
|
||||
Регистрация: 05.11.2015
Сообщений: 585
|
Цитата:
(в качестве доп. идеи): Код:
|
|||
|
||||
Moderator
LISP, C# (ACAD 200[9,12,13,14]) Регистрация: 25.08.2003
С.-Петербург
Сообщений: 39,772
|
Владимир_М, это предполагает построение примитивов, чего хотелось бы избежать
__________________
Моя библиотека lisp-функций --- Обращение ко мне - на "ты". Все, что сказано - личное мнение. |
|||
|
||||
КМД Регистрация: 26.03.2013
Я ЖЫВУ В РОССИИ.
Сообщений: 506
|
Цитата:
http://mysimpleengeneeringsolutions....-continue.html работает с помощью Clipper http://www.angusj.com/delphi/clipper.php Clipper, в свою очередь, основан на Алгоритме Ваати https://en.wikipedia.org/wiki/Vatti_clipping_algorithm Алгоритм Ваати основан на понятии "ветрянных чисел" - это как раз о количестве пересечений контура лучом из точки... "A generic solution to polygon clipping", Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63. - платная статья(15$), но у автора появились другие ссылки - http://www.me.berkeley.edu/~mcmains/...setPolygon.pdf алгоритм работает и с дугами, и с отверстиями, устраняет самопересечения в контуре, позволяет пользоваться оффсетом, доступен на питоне дельфи плюсах, шарпе... Проект жив и развивается: http://codepen.io/timo22345/pen/LpEbWB?editors=101 Последний раз редактировалось hexD, 31.05.2016 в 10:34. |
|||
|
||||
Вроде как алгоритм работает. Зеленые - внутри контура, черные - вне, красный - частично в контуре
Код:
__________________
Как использовать код на Лиспе читаем здесь Последний раз редактировалось VVA, 31.05.2016 в 19:57. |
||||
|
||||
Изменил алгоритм построения луча в mip_IsPointInside. Там получалось, что луч строился горизонтально, 3-я вершина контура с координатами 128,64 лежала на этом луче. Поэтому две примыкающие стороны давали перечение. В итоге получалось 2 пересечения, хотя контур пересекается один раз в вершине. Четное количество пересечений - точка вне контура.
Обновил #54 Тестируй.
__________________
Как использовать код на Лиспе читаем здесь |
||||
|
||||
Регистрация: 21.07.2008
Луцьк
Сообщений: 179
|
можно еще попробовать вот это http://www.cadtutor.net/forum/showth...l=1#post263330
там немного другой способ |
|||
|
||||
строю, ломаю Регистрация: 03.04.2008
Украина
Сообщений: 5,515
|
|
|||
|
||||
В этом случае mip_IsPointInside вернет список из одного T и трех NIL. Добавил проверку в #54
----- добавлено через ~12 ч. ----- *** Добавлено *** Для упрощения анализа можно "обернуть" функцию mip_IsPointInside, которая будет возвращать не T или NIL, а 1 или 0. И анализировать сумму чисел полученного списка( 0 - не в контуре, 1 - касается одной точкой или одна точка в контуре (недостающие ф-ции в #54) Код:
__________________
Как использовать код на Лиспе читаем здесь Последний раз редактировалось VVA, 01.06.2016 в 08:19. |
||||
|
||||
*** Добавлено2 ***
В таком случае синий и зеленый квадрат будут считаться не в контуре. Это правильно?
__________________
Как использовать код на Лиспе читаем здесь |
||||
|
||||
строю, ломаю Регистрация: 03.04.2008
Украина
Сообщений: 5,515
|
Да, вопрос именно в этом, что мы понимаем под словом "внутри" и "снаружи". Как вариант можно рассмотреть игнор пограничных точек, но тогда нужно проверять принцип погрраничности, а затраты на это действие зависят от многоугольника границы
|
|||
|
||||
Если немного переписать функцию, то можно анализировать все варианты
Код:
Единственное улучшение - возвращать можно целые числа: 0 - не в контуре 100 - в контуре 1 - на границе И сравнивать целые числа 400 - 4 точти внутри контура 300 - 3 точки внутри, одна снаружи 301 - 3 точки внутри, одна на границе и т.д.
__________________
Как использовать код на Лиспе читаем здесь |
||||
|
||||
Хорошо действует Принадлежность точки криволинейному контуру VVA.
Действует для линейных объектов, образующих контуры: Код:
Для штриховок, регионов, мультиполигонов. В т.ч. для площадных объектов с отверстиями в них. Можно ли расширить эту функцию для площадных объектов?
__________________
количество моих сообщений не говорит о знании Автокада |
||||
|
||||
Пока нашел почти аналог In_Figure_Obj - LM:Inside-p от Lee Mac, https://www.cadtutor.net/forum/topic...comment=254876.
Она на 4 года "новее" In_Figure_Obj - 2011 г. LM:Inside-p работает в 1.8 раз быстрее, но только для LWPolyline. Можно ли расширить ее действие на окружности, эллипсы, сплайны и другие полилинии? Или тогда скорость сразу резко уменьшится? --------------- Для самопересекающихся объектов In_Figure_Obj выдает invalid... - я ошибся, не выдает, работает нормально.
__________________
количество моих сообщений не говорит о знании Автокада Последний раз редактировалось АлексЮстасу, 24.06.2022 в 02:59. |
||||
|
||||
In_Figure_Obj выдает ошибочный результат, если горизонтальный вправо луч из точки попадает на вершину контура.
И In_Figure_Obj на каких-то эллипсах (желтый) вообще зависает. На каких - закономерности не нашел. Проверял так: Код:
__________________
количество моих сообщений не говорит о знании Автокада |
||||
|
||||
Цитата:
Нашел еще один вариант от Ли на болоте (требуется регистрация) https://www.theswamp.org/index.php?topic=43550.0 Код:
Код:
Публикую без проверки. LM:PointInside-p использует метод 'intersectwith, поэтому должна работать и с полигонами и проч, ели автодеск заложил такую возможность
__________________
Как использовать код на Лиспе читаем здесь |
||||
|
||||
Регистрация: 20.04.2011
Сообщений: 396
|
|
|||
|
||||
LM:PointInside-p с регионами у меня не работает. Как и с мультиполигонами, штриховками и 3дфейсами.
Со сплайнами, с окружностями, с дуговыми сегментами работает. Для точек на границе выдает "; error: Automation Error. Points are coincident". Для полилиний с самопересечениями может выдать и "Point is INSIDE", и "Point is OUTSIDE". Т.е. ненадежно. Так же несерьезно с isPtinPM. Во многих случаях выдает загадочное ""At", при том, что точки далеко от границ. Наверняка отличное решение, но не на лисп. Если про другие языки, то феноменально быстрое и точное решение дал Debalance - https://dwg.ru/b/topomap/287 и т.д.
__________________
количество моих сообщений не говорит о знании Автокада |
||||
|
||||
Регистрация: 10.11.2023
Сообщений: 2
|
В общем, 11 лет назад поломал голову. Решение такое. Берем произвольную прямую, проходящую через точку. Для простоты, можно взять горизонтальную (т.е. Y не меняется) и считаем число пересечений контура с этой прямой слева и справа. если оба получившихся числа нечетные - точка в контуре. И не надо всякие углы изобретать.
|
|||
|
||||
конструктор Регистрация: 21.07.2007
Петрозаводск
Сообщений: 1,969
|
Надо не спутать пересечение с точкой касания, а касание - с касанием в точке перегиба.
|
|||
|
||||
Регистрация: 10.11.2023
Сообщений: 2
|
Конечно, этот случай надо обрабатывать отдельно и не учитывать. А так, все отлично работает. Код сложно привести, там случай существенно сложнее идеализированного контура и точки, большой, и вряд ли кто-то будет ковыряться. Главное идея.
|
|||
|
Опции темы | Поиск в этой теме |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Справка по форуму | Admin | FAQ: Часто задаваемые вопросы | 13 | 04.03.2014 11:12 |
У меня вопрос по Ansys, как правильно оформить контакт с жестким телом? | Цветочек | ANSYS | 17 | 10.11.2013 09:41 |
Проектирование человека. | FOXAL | Разное | 283 | 25.05.2010 09:52 |
Вопрос: Интерактивное построение полилинии внутри lisp-программы | Tonic | LISP | 5 | 26.04.2010 15:50 |
Как определить, что точка за пределами видимой области? VBA | den001 | Программирование | 6 | 20.01.2007 20:48 |