|
||
| Правила | Регистрация | Пользователи | Сообщения за день | | Поиск | | Справка по форуму | Файлообменник | |
|
Поиск в этой теме |
02.12.2010, 21:36 | #1 | |
Как определить, лежит ли точка внутри контура
Регистрация: 22.01.2010
Сообщений: 311
|
||
Просмотров: 33163
|
|
||||
Если сумма площадей треугольников, образованных сегментом замкнутой полилинии и точкой равна площади замкнутой полилинии, то точка принадлежит внутреннему пространству. Все остальное - внешнему.
Есть одно исключение - это когда несколько сегментов полилинии образуют кривую закорючку. Если и с закорючками надо бороться, то есть решение. |
||||
|
||||
Регистрация: 22.01.2010
Сообщений: 311
|
Глянь картинку.
Мне в голову пришло только одно решение: из точки отрисовать 4 отрезка единичной длины под углами 0, 90, 180, 270 град. и затем 4 раза дать команду удлинить до контура. Если это 4 раза сработает, то точка внутри контура. Похоже на правду? Последний раз редактировалось swkx, 02.12.2010 в 22:32. |
|||
|
||||
Инженер LISP Регистрация: 11.05.2005
Минск
Сообщений: 6,992
|
Теория:
Проверка принадлежности точки многоугольнику: Метод трассировки луча Практика: Принадлежность точки криволинейному контуру Принадлежность точки линейному контуру 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...
частный случай, когда ближайшая точка в вершине полилинии - нужно рассматривать два вектора - конец одного сегмента и начало следующего. Удачи!
__________________
Чем гениальнее ваш план, тем меньше людей с ним будут согласны. /Сунь Цзы/ |
||||
|
||||
Инженер LISP Регистрация: 11.05.2005
Минск
Сообщений: 6,992
|
Если через построения, то можно еще одним способом:
1. Из координат вершин полилинии формируешь список точек lst 2. В интересующем тебя месте рисуешь примитив "точка" e1 3. ssget'ом с опцией "_CP" (секущий многоугольник) формируешь набор 4. Проверяешь, попал ли примитив "точка" в набор. Если да - точка внутри контура, если нет - то и точки внутри нет
__________________
Как использовать код на Лиспе читаем здесь Последний раз редактировалось VVA, 30.05.2016 в 23:22. Причина: орфоргафия |
|||
|
||||
- Регистрация: 24.07.2005
Москва
Сообщений: 1,335
|
Цитата:
|
|||
|
||||
Инженер LISP Регистрация: 11.05.2005
Минск
Сообщений: 6,992
|
swkx, "Метод трассировки луча" у меня уже работает лет так надцать и зарекомендовал себя как надежный и устойчивый алгоритм. Советую остановиться на нем.
__________________
Как использовать код на Лиспе читаем здесь |
|||
|
||||
Ничего подобного, этот алгоритм отлично работает с невыпуклыми контурами, в том числе имеющими дуговые сегменты! Другое дело, что действительно, этот алгоритм не подходит для контуров имеющих самопересечения. В моих проектах обрабатываются контура, которые в дальнейшем пойдут на станки чпу - вертикальные фрезеры, другими словами, постпроцессоры станков чпу не работают с самопересекающимися контурами - у контура должна быть только одна сторона внешняя и одна внутренняя...
__________________
Чем гениальнее ваш план, тем меньше людей с ним будут согласны. /Сунь Цзы/ |
||||
|
||||
Продуман Регистрация: 22.02.2007
Питер
Сообщений: 2,840
|
То Евгений - я если честно не очень понял принцип алгоритма - но ихмо исходных данных маловато для вычисления и на "сложноневыпуклых" не пройдет. Если можно объяни более подробно свой метод.
Автору - если подразумеваются фигуры "сложновыпуклые" или еще и с самопересечениями - я бы вначале трангулировал-бы фигуру - а затем проверил бы треугольники.
__________________
Когда в руках молоток все вокруг кажется гвоздями. |
|||
|
||||
Цитата:
например у нас есть квадрат и точка внутри: 1. проверяем направление обхода вершин в контуре - например получили против часовой стрелки 2. используя vlax-curve-getclosestpointto находим ближайшую точку на контуре (ближайшую от проверяемой точки) 3. используя vlax-curve-getFirstDeriv получаем первую производную контура в найденой точке на контуре, другими словами, мы получаем вектор направленности контура в данной точке, если сегмент дуговой, то вектор идет по косательной, если прямолинейный, то вдоль сегмента. 4. находим углы направления вектора первой производной и между тестовой точкой и ближайшей точкой на контуре, чтоб узнать угол между этими направлениями В нашем случае, мы получаем 90 градусов или если без перевода в градусы то (/ pi 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 |