| Правила | Регистрация | Пользователи | Поиск | Сообщения за день | Все разделы прочитаны |  Справка по форуму | Файлообменник |

Вернуться   Форум DWG.RU > Программное обеспечение > Программирование > Как определить, лежит ли точка внутри контура

Как определить, лежит ли точка внутри контура

Ответ
Поиск в этой теме
Непрочитано 02.12.2010, 21:36 #1
Как определить, лежит ли точка внутри контура
swkx
 
Регистрация: 22.01.2010
Сообщений: 311

Контур - замкнутая 2D-полилиния неправильной формы.
Как программно определить, лежит ли точка с координатами X и Y внутри контура ?
Нужна не готовая функция, а просто подходы к решению.
А может уже есть стандартная из серии VLA-....?
Просмотров: 32728
 
Непрочитано 02.12.2010, 22:11
#2
Supermax

Руководитель фирмы
 
Регистрация: 28.03.2007
Москва
Сообщений: 1,831
Отправить сообщение для Supermax с помощью Skype™


Если сумма площадей треугольников, образованных сегментом замкнутой полилинии и точкой равна площади замкнутой полилинии, то точка принадлежит внутреннему пространству. Все остальное - внешнему.
Есть одно исключение - это когда несколько сегментов полилинии образуют кривую закорючку.
Если и с закорючками надо бороться, то есть решение.
Supermax вне форума  
 
Автор темы   Непрочитано 02.12.2010, 22:17
#3
swkx


 
Регистрация: 22.01.2010
Сообщений: 311


Supermax,

думаю, не прокатит. Контур не обязательно выпуклая фигура. Т.е. отрезок от точки, даже если она лежит внутри контура, до вершины сегмента не обязательно будет внутри контура.
Миниатюры
Нажмите на изображение для увеличения
Название: ТочкаВКонтуре.jpg
Просмотров: 449
Размер:	13.9 Кб
ID:	49323  
swkx вне форума  
 
Непрочитано 02.12.2010, 22:21
#4
Supermax

Руководитель фирмы
 
Регистрация: 28.03.2007
Москва
Сообщений: 1,831
Отправить сообщение для Supermax с помощью Skype™


Я че-то совсем не понял, что ты хотел сказать.
Supermax вне форума  
 
Автор темы   Непрочитано 02.12.2010, 22:22
#5
swkx


 
Регистрация: 22.01.2010
Сообщений: 311


Глянь картинку.

Мне в голову пришло только одно решение: из точки отрисовать 4 отрезка единичной длины под углами 0, 90, 180, 270 град. и затем 4 раза дать команду удлинить до контура. Если это 4 раза сработает, то точка внутри контура.

Похоже на правду?

Последний раз редактировалось swkx, 02.12.2010 в 22:32.
swkx вне форума  
 
Непрочитано 02.12.2010, 22:51
#6
VVA

Инженер LISP
 
Регистрация: 11.05.2005
Минск
Сообщений: 6,990
<phrase 1= Отправить сообщение для VVA с помощью Skype™


Теория:
Проверка принадлежности точки многоугольнику: Метод трассировки луча
Практика:
Принадлежность точки криволинейному контуру

Принадлежность точки линейному контуру

A point inside a region

LISP. Проверка вхождения точки в контур ссылка на dwg.ru http://forum.dwg.ru/showthread.php?p...62#post1538162
__________________
Как использовать код на Лиспе читаем здесь

Последний раз редактировалось VVA, 26.04.2017 в 18:53. Причина: актуализирована ссылка
VVA вне форума  
 
Автор темы   Непрочитано 02.12.2010, 23:11
#7
swkx


 
Регистрация: 22.01.2010
Сообщений: 311


VVA,
спасибо за ссылочки. Правда, я суть алгоритма не ухватил.

Поясни, если можешь, вот это, до меня не доходит:
"...Точка лежит в контуре, если некий луч пересекает отрезки контура нечетное количество раз..."

...
Всё, не нужно пояснять, дошло.
swkx вне форума  
 
Непрочитано 03.12.2010, 01:25
#8
KAI

геологоразведка, строительство
 
Регистрация: 14.10.2003
Магадан
Сообщений: 311


В дополнение к последней ссылке VVA (пост №6).

Мои функции лучше брать из первоисточника.
http://geol-dh.ru/spds/function.html
__________________
Лень - великий двигатель прогресса!
KAI вне форума  
 
Автор темы   Непрочитано 03.12.2010, 08:03
#9
swkx


 
Регистрация: 22.01.2010
Сообщений: 311


KAI,
благодарю, воспользуюсь.
swkx вне форума  
 
Непрочитано 03.12.2010, 12:51
#10
Елпанов Евгений

программист
 
Регистрация: 20.12.2005
Москва
Сообщений: 1,439
Отправить сообщение для Елпанов Евгений с помощью Skype™


самый простой способ - находишь ближайшую точку на полилинии к твоей точке vlax-curve-* тебе в помощь. Далее находишь производную в этой точке - вектор направленности. Зная направление обхода полилинии (по часовой или против часовой) можно определить угол +90 или -90...
частный случай, когда ближайшая точка в вершине полилинии - нужно рассматривать два вектора - конец одного сегмента и начало следующего.

Удачи!
__________________
Чем гениальнее ваш план, тем меньше людей с ним будут согласны.
/Сунь Цзы/
Елпанов Евгений вне форума  
 
Автор темы   Непрочитано 03.12.2010, 14:14
#11
swkx


 
Регистрация: 22.01.2010
Сообщений: 311


Я рассматривал этот метод в одной из ссылок, которые VVA подкинул, но вариант с лучом (четное-нечетное число пересечений контура) мне больше понравился.
А мой собственный способ из поста #5 нравится ещё больше )))))
swkx вне форума  
 
Непрочитано 03.12.2010, 14:20
#12
Лиспер


 
Регистрация: 11.10.2010
Сообщений: 980


Вариант с построением можно занимать значительно бОльшее время, чем математическое вычисление.
__________________
(/= RegDate StartReadDate)
Лиспер вне форума  
 
Непрочитано 03.12.2010, 14:27
#13
VVA

Инженер LISP
 
Регистрация: 11.05.2005
Минск
Сообщений: 6,990
<phrase 1= Отправить сообщение для VVA с помощью Skype™


Цитата:
Сообщение от swkx Посмотреть сообщение
А мой собственный способ из поста #5 нравится ещё больше )))))
Если через построения, то можно еще одним способом:
1. Из координат вершин полилинии формируешь список точек lst
2. В интересующем тебя месте рисуешь примитив "точка" e1
3. ssget'ом с опцией "_CP" (секущий многоугольник) формируешь набор
4. Проверяешь, попал ли примитив "точка" в набор. Если да - точка внутри контура, если нет - то и точки внутри нет
__________________
Как использовать код на Лиспе читаем здесь

Последний раз редактировалось VVA, 30.05.2016 в 23:22. Причина: орфоргафия
VVA вне форума  
 
Автор темы   Непрочитано 03.12.2010, 14:40
#14
swkx


 
Регистрация: 22.01.2010
Сообщений: 311


Лиспер,
очень может быть, я к непосредственной реализации ещё не приступал, всё пока только в голове крутится.

VVA,
я про ssget с опцией "_CP" даже не подумал. Похоже, это вообще самый простой способ.
swkx вне форума  
 
Непрочитано 03.12.2010, 14:43
#15
Лиспер


 
Регистрация: 11.10.2010
Сообщений: 980


Цитата:
Сообщение от swkx Посмотреть сообщение
это вообще самый простой способ.
До тех пор, пока контур не начнет самопересекаться или вылезать за границы видимой части экрана.
__________________
(/= RegDate StartReadDate)
Лиспер вне форума  
 
Непрочитано 03.12.2010, 14:43
#16
Sleekka

-
 
Регистрация: 24.07.2005
Москва
Сообщений: 1,335


Цитата:
самый простой способ - находишь ближайшую точку на полилинии к твоей точке vlax-curve-* тебе в помощь. Далее находишь производную в этой точке - вектор направленности. Зная направление обхода полилинии (по часовой или против часовой) можно определить угол +90 или -90...
частный случай, когда ближайшая точка в вершине полилинии - нужно рассматривать два вектора - конец одного сегмента и начало следующего.
Евгений этот алгорим будет работать только для выпухлых контуров, но он быстр как и все твои алгоритмы =), есть же более полные алгоримы, которые работают даже с самопересекающимися контурами, хотя конечно всегда лучше работать, с выпуклыми.
Sleekka вне форума  
 
Непрочитано 03.12.2010, 14:46
#17
VVA

Инженер LISP
 
Регистрация: 11.05.2005
Минск
Сообщений: 6,990
<phrase 1= Отправить сообщение для VVA с помощью Skype™


swkx, "Метод трассировки луча" у меня уже работает лет так надцать и зарекомендовал себя как надежный и устойчивый алгоритм. Советую остановиться на нем.
__________________
Как использовать код на Лиспе читаем здесь
VVA вне форума  
 
Непрочитано 03.12.2010, 14:47
#18
Елпанов Евгений

программист
 
Регистрация: 20.12.2005
Москва
Сообщений: 1,439
Отправить сообщение для Елпанов Евгений с помощью Skype™


Цитата:
Сообщение от Sleekka Посмотреть сообщение
Евгений этот алгорим будет работать только для выпухлых контуров, но он быстр как и все твои алгоритмы =), есть же более полные алгоримы, которые работают даже с самопересекающимися контурами, хотя конечно всегда лучше работать, с выпуклыми.
Ничего подобного, этот алгоритм отлично работает с невыпуклыми контурами, в том числе имеющими дуговые сегменты! Другое дело, что действительно, этот алгоритм не подходит для контуров имеющих самопересечения. В моих проектах обрабатываются контура, которые в дальнейшем пойдут на станки чпу - вертикальные фрезеры, другими словами, постпроцессоры станков чпу не работают с самопересекающимися контурами - у контура должна быть только одна сторона внешняя и одна внутренняя...
__________________
Чем гениальнее ваш план, тем меньше людей с ним будут согласны.
/Сунь Цзы/
Елпанов Евгений вне форума  
 
Непрочитано 03.12.2010, 15:02
#19
Дима_

Продуман
 
Регистрация: 22.02.2007
Питер
Сообщений: 2,840


То Евгений - я если честно не очень понял принцип алгоритма - но ихмо исходных данных маловато для вычисления и на "сложноневыпуклых" не пройдет. Если можно объяни более подробно свой метод.
Автору - если подразумеваются фигуры "сложновыпуклые" или еще и с самопересечениями - я бы вначале трангулировал-бы фигуру - а затем проверил бы треугольники.
__________________
Когда в руках молоток все вокруг кажется гвоздями.
Дима_ вне форума  
 
Непрочитано 03.12.2010, 17:20
#20
Елпанов Евгений

программист
 
Регистрация: 20.12.2005
Москва
Сообщений: 1,439
Отправить сообщение для Елпанов Евгений с помощью Skype™


Цитата:
Сообщение от Дима_ Посмотреть сообщение
я если честно не очень понял принцип алгоритма - но ихмо исходных данных маловато для вычисления и на "сложноневыпуклых" не пройдет. Если можно объяни более подробно свой метод.
есть проверяемая точка и контур.
например у нас есть квадрат и точка внутри:

1. проверяем направление обхода вершин в контуре - например получили против часовой стрелки
2. используя vlax-curve-getclosestpointto находим ближайшую точку на контуре (ближайшую от проверяемой точки)
3. используя vlax-curve-getFirstDeriv получаем первую производную контура в найденой точке на контуре, другими словами, мы получаем вектор направленности контура в данной точке, если сегмент дуговой, то вектор идет по косательной, если прямолинейный, то вдоль сегмента.
4. находим углы направления вектора первой производной и между тестовой точкой и ближайшей точкой на контуре, чтоб узнать угол между этими направлениями

В нашем случае, мы получаем 90 градусов или если без перевода в градусы то (/ pi 2)
Если бы точка была снаружи, то угл был бы отрицательным, если контур по часовой стрелке, то результаты надо инвертировать т.е. внутри отрицательный и снаружи положительный.

Это описание, если ближайшая точка лежит на сегменте, если ближайшей точкой является вершина полилинии, то чуть сложнее, но если вы нарисуете, то сами поймете - ничего сложного!

Хочу пояснить еще один момент, если у контура несколько последовательных вершин совпадают, т.е сегмент имеет нулевую длину, то угол будет всегда равен нулю и необходимо искать последнюю вершину в списке совпадающих.
__________________
Чем гениальнее ваш план, тем меньше людей с ним будут согласны.
/Сунь Цзы/
Елпанов Евгений вне форума  
Ответ
Вернуться   Форум DWG.RU > Программное обеспечение > Программирование > Как определить, лежит ли точка внутри контура

Размещение рекламы
Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Справка по форуму 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