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

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

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

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

Контур - замкнутая 2D-полилиния неправильной формы.
Как программно определить, лежит ли точка с координатами X и Y внутри контура ?
Нужна не готовая функция, а просто подходы к решению.
А может уже есть стандартная из серии VLA-....?
Просмотров: 32729
 
Непрочитано 03.12.2010, 18:03
#21
Дима_

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


Домой пора - короче нефига не понял как по одному вектору можно у НЕВЫПУКЛОЙ фигуры направление понять. В понедельник отпишусь.
__________________
Когда в руках молоток все вокруг кажется гвоздями.
Дима_ вне форума  
 
Непрочитано 03.12.2010, 18:34
#22
Елпанов Евгений

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


Цитата:
Сообщение от Дима_ Посмотреть сообщение
Домой пора - короче нефига не понял как по одному вектору можно у НЕВЫПУКЛОЙ фигуры направление понять. В понедельник отпишусь.
Направление обхода точек можно узнать программно - заходи на мой сайт и бери или ищи на этом форуме.
Направление сегмента можно получить из вектора направленности - результат работы функции vlax-curve-getFirstDeriv, т.е. угол между двумя точками '(0. 0.) и вектором
Направление на ближайшую точку контура, вообще просто - угол между двумя точками - тестовой и ближайшей
Угол между двумя углами, вообще просто - вычел из одного другой и получил нужный угол, только проверить чтоб был в диапазоне -180/+180 градусов...
__________________
Чем гениальнее ваш план, тем меньше людей с ним будут согласны.
/Сунь Цзы/
Елпанов Евгений вне форума  
 
Непрочитано 03.12.2010, 18:47
#23
VVA

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


>Евгений, все таки наверное алгоритм для выпуклых контуров
Ну и алгоритм поста #20 в коде (для выпуклых контуров)
Код:
[Выделить все]
(defun C:TEST ( )
  (vl-load-COM)
  (and
    (setq e1 (car(entsel "\nВыбери полилинию-контур: ")))
    (setq pt1 (getpoint "\nУкажи точку (не на контуре): "))
    (setq pt2 (vlax-curve-getclosestpointto e1 pt1)) ;_ см п.2 пост #20
    (setq pt3 (vlax-curve-getFirstDeriv e1 (vlax-curve-getParamAtPoint e1 pt2)));_ см п.3 пост #20
    (setq pt1 (mapcar '- pt1 pt2))
    (setq ang (3d_Wnorm pt1 pt3)) ;_ см п.4 пост #20
    (if (lib:pline_clockwise e1) ;;; если контур по часовой стрелке
      (progn
        ;;;Если бы точка была снаружи, то угол был бы отрицательным
        (if (minusp (last ang))
          (alert "Точка снаружи")
          (alert "Точка внутри")
          )
        )
      (progn  ;;; если контур против часовой стрелки
        (if (minusp (last ang))
          (alert "Точка внутри")
          (alert "Точка снаружи")
          )
        )
      )
    )
  )

;********************************
; Векторное произведение векторов
;********************************
; W1, W2 - вектора
; Возвращает: вектор нормали к плоскости заданной векторами  в правой системе координат.
;W1 и W2 не должны лежать на одной прямой).
(defun 3d_Wnorm (W1 W2)
  (if (< (length W1) 3)(setq W1 (list (car W1)(cadr W1) 0)))
  (if (< (length W2) 3)(setq W2 (list (car W2)(cadr W2) 0)))
  (list (- (* (cadr W1)(caddr W2))(* (caddr W1)(cadr W2)))
        (- (* (caddr W1)(car W2)) (* (car W1)(caddr W2)))(- (* (car W1)(cadr W2)) (* (cadr W1)(car W2)))))


(defun lib:pline_clockwise ( lw  / LST MAXP MINP)
;;;Eugeni Elpanov
;;; Arguments
;;;         lw - ename or vla object of polyline
;;; Return
;;;     t - clockwise
;;;    nil - counter-clockwise
  
(if (= (type lw) 'ENAME)
    (setq lw (vlax-ename->vla-object lw)))  
(vla-GetBoundingBox lw 'MinP 'MaxP)
(setq
minp(vlax-safearray->list minp)
MaxP(vlax-safearray->list MaxP)
lst(mapcar(function(lambda(x)
(vlax-curve-getParamAtPoint lw
(vlax-curve-getClosestPointTo lw x))))
(list minp(list(car minp)(cadr MaxP))
MaxP(list(car MaxP)(cadr minp)))))
(if(or
(<=(car lst)(cadr lst)(caddr lst)(cadddr lst))
(<=(cadr lst)(caddr lst)(cadddr lst)(car lst))
(<=(caddr lst)(cadddr lst)(car lst)(cadr lst))
(<=(cadddr lst)(car lst)(cadr lst)(caddr lst))) t nil))
__________________
Как использовать код на Лиспе читаем здесь
VVA вне форума  
 
Непрочитано 03.12.2010, 19:12
#24
Елпанов Евгений

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


VVA, я же описал, если ближайшая точка в вершине, то нужно рассматривать вектор в конце предыдущего сегмента и в начале следующего после ближайшей вершины...
Те же проблемы будут и с выпуклым контуром, если ты укажешь точку снаружи, напротив вершины, т.е. ближайшей будет именно вершина контура.
__________________
Чем гениальнее ваш план, тем меньше людей с ним будут согласны.
/Сунь Цзы/
Елпанов Евгений вне форума  
 
Непрочитано 03.12.2010, 23:46
#25
zamtmn

КИПиА
 
Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
<phrase 1=


Цитата:
Евгений этот алгорим будет работать только для выпухлых контуров, но он быстр как и все твои алгоритмы =)
Этот алгоритм совсем не быстрый, т.к. поиск ближайшей точки на контуре подразумевает поиск пересечений со всеми линиями образующими контур. Видимо его реализация быстрее за счет
Цитата:
находишь ближайшую точку на полилинии к твоей точке vlax-curve-*
zamtmn вне форума  
 
Непрочитано 04.12.2010, 00:02
#26
Дима_

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


То Евгений - для тупых - объясни как работает твоя функция на невыпуклой (правой) фигуре?
Миниатюры
Нажмите на изображение для увеличения
Название: фигура.jpg
Просмотров: 135
Размер:	22.1 Кб
ID:	49405  
__________________
Когда в руках молоток все вокруг кажется гвоздями.
Дима_ вне форума  
 
Непрочитано 04.12.2010, 00:19
#27
zamtmn

КИПиА
 
Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
<phrase 1=


понятие обхода вершин применимо к невыпуклым контурам. в первом случае направление обхода (касательной к контуру) в ближай точке будет в одну сторону, во втором в противоположную.
zamtmn вне форума  
 
Непрочитано 05.12.2010, 21:19
#28
Li6-D


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


Простой алгоритм для любой фигуры (выпуклой, невыпуклой, самопересекающейся). Но дуги в контуре, увы нельзя - может обмануть...
Код:
[Выделить все]
(defun conclusion ( / n ent PN P P0 a)
;|Функция запрашивает контур (2D-полининию из отрезков) и точку P.
  Если контур замкнут и точка не находится на его границе,
  а внутри контура, фунция возвращает T. Иначе - nil.
  Функция также печатает в текстовое окно соответствующее сообщение.
  Может некорректно работать, если полилиния содержит дуги|;
  (setq n 0) ;Начальное значение числа пересечений контуром оси PX.
  (princ "\nУкажите контур (2D-полилинию).")
  (and
    (setq ent (ssget "_:S" '((0 . "LWPOLYLINE"))))
    (setq PN (vl-remove-if '(lambda (x) (/= (car x) 10))
                (setq ent (entget (ssname ent 0)))
    )         )
    (or (= (cdr (assoc 70 ent)) 1) (prompt "\nКонтур не замкнут."))
    (setq P (getpoint "\nУкажите точку: "))
    (or
      (not (setq P0 (ssget P)))
      (not (ssmemb (cdar ent) P0))
      (prompt "\nТочка на границе контура.")
    )
    (setq PN (mapcar '(lambda (x) (angle P (cdr x))) PN)
          P0 (last PN))
    (foreach P PN
      (setq a (- P P0) P0 P)
      (or (<= (abs a) Pi) (setq n (1+ n)))
    )
    (or (/= (rem n 2) 0) (prompt "\nТочка снаружи контура."))
    (princ "\nТочка внутри контура.")
    t
) )
Долго не проверял

Последний раз редактировалось Li6-D, 11.12.2010 в 23:27. Причина: отсек лишнее
Li6-D вне форума  
 
Непрочитано 03.03.2015, 11:28
#29
Disney

Геодезист
 
Регистрация: 12.03.2009
Сибирь (где медведи по улицам ходят)
Сообщений: 860
Отправить сообщение для Disney с помощью Skype™


А у меня другая дилемма, как для команды-boundary найти точку внутри двух контуров красного и синего, чтоб получить зелёный?
Миниатюры
Нажмите на изображение для увеличения
Название: boundary.jpg
Просмотров: 58
Размер:	66.4 Кб
ID:	145017  
__________________
Почему все вдруг становятся умными, когда уже не надо?
Disney вне форума  
 
Непрочитано 03.03.2015, 12:00
1 | #30
trir


 
Регистрация: 18.12.2010
Сообщений: 5,047


http://alglib.sources.ru/articles/convpol.php
trir вне форума  
 
Непрочитано 03.03.2015, 12:19
#31
Disney

Геодезист
 
Регистрация: 12.03.2009
Сибирь (где медведи по улицам ходят)
Сообщений: 860
Отправить сообщение для Disney с помощью Skype™


Цитата:
Сообщение от trir Посмотреть сообщение
Прочитал, но не понял ни чего
__________________
Почему все вдруг становятся умными, когда уже не надо?
Disney вне форума  
 
Непрочитано 03.03.2015, 12:21
1 | #32
VVA

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


Disney,
Как вариант
1. Найти центроид одного контура
2. Проверить, находится ли он внутри другого
3. Если нет - поменять контура местами
4. Если опять нет - ?

----- добавлено через ~17 мин. -----
Еще один алгоритм
1. 1-й контур преобразовать в region
2. 2-й контур преобразовать в регион
3. Найти пересечение областей
4. У полученного контура найти центроид
Что-то похожее было здесь
Там надо нарисовать замкнутую полилинию, задать размеры отверствия и полученное отверствие "посадить" на один из сегментов
__________________
Как использовать код на Лиспе читаем здесь
VVA вне форума  
 
Непрочитано 03.03.2015, 12:52
#33
Disney

Геодезист
 
Регистрация: 12.03.2009
Сибирь (где медведи по улицам ходят)
Сообщений: 860
Отправить сообщение для Disney с помощью Skype™


Цитата:
Сообщение от VVA Посмотреть сообщение
Disney,
Как вариант
...Найти центроид
...
С центроидами не вариант, в моём примере он будет лежать вне контура примерно по центру картинки
Я думал о подобном, взять центр из GetBoundingBox.
Миниатюры
Нажмите на изображение для увеличения
Название: Центроиды.jpg
Просмотров: 31
Размер:	68.9 Кб
ID:	145029  
__________________
Почему все вдруг становятся умными, когда уже не надо?

Последний раз редактировалось Disney, 03.03.2015 в 12:58.
Disney вне форума  
 
Непрочитано 03.03.2015, 12:54
#34
Кулик Алексей aka kpblc
Moderator

LISP, C# (ACAD 200[9,12,13,14])
 
Регистрация: 25.08.2003
С.-Петербург
Сообщений: 39,772


Не прокатит. Возьми фигуру типа "полумесяц"....
__________________
Моя библиотека lisp-функций
---
Обращение ко мне - на "ты".
Все, что сказано - личное мнение.
Кулик Алексей aka kpblc вне форума  
 
Непрочитано 03.03.2015, 13:11
#35
Disney

Геодезист
 
Регистрация: 12.03.2009
Сибирь (где медведи по улицам ходят)
Сообщений: 860
Отправить сообщение для Disney с помощью Skype™


Обычно ситуация такая

и там вполне "центр" прокатит, но не исключен вариант с полумесяцами, или например такой
Миниатюры
Нажмите на изображение для увеличения
Название: 1-идеал.jpg
Просмотров: 546
Размер:	12.4 Кб
ID:	145031  Нажмите на изображение для увеличения
Название: 2-вариант.jpg
Просмотров: 544
Размер:	12.5 Кб
ID:	145033  
__________________
Почему все вдруг становятся умными, когда уже не надо?
Disney вне форума  
 
Непрочитано 03.03.2015, 13:50
1 | #36
VVA

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


Цитата:
Сообщение от Disney Посмотреть сообщение
С центроидами не вариант
Цитата:
Сообщение от Кулик Алексей aka kpblc Посмотреть сообщение
Не прокатит. Возьми фигуру типа "полумесяц"....
Я в #32 добавил еще один вариант, преобразовать в области, найти пересечение контуров и ... мне кажется этого достаточно ?
__________________
Как использовать код на Лиспе читаем здесь
VVA вне форума  
 
Непрочитано 03.03.2015, 17:07
#37
Disney

Геодезист
 
Регистрация: 12.03.2009
Сибирь (где медведи по улицам ходят)
Сообщений: 860
Отправить сообщение для Disney с помощью Skype™


Цитата:
Сообщение от VVA Посмотреть сообщение
преобразовать в области, найти пересечение контуров и ... мне кажется этого достаточно ?
Да точно, просто я понять не мог, чем пересечение(IntersectWith) областей отличается от пересечения полилиний.
А оказалось ты о команде Пересечение , я привык её к 3D телам применять, а то что она с областями сработает и не знал. Вообще ни когда области не использовал и не понимал для чего они... я и сейчас не понимаю, но в моём случаи пригодиться.
Спасибо!

----- добавлено через ~18 ч. -----
Всё получилось.
Но теперь как мне достать координаты вершин получившейся области?
__________________
Почему все вдруг становятся умными, когда уже не надо?
Disney вне форума  
 
Непрочитано 04.03.2015, 12:50
#38
fasadel


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


Была у меня такая задачка.
fasadel вне форума  
 
Непрочитано 04.03.2015, 13:10
#39
Disney

Геодезист
 
Регистрация: 12.03.2009
Сибирь (где медведи по улицам ходят)
Сообщений: 860
Отправить сообщение для Disney с помощью Skype™


Цитата:
Сообщение от Disney Посмотреть сообщение
Но теперь как мне достать координаты вершин получившейся области?
Разбил область на линии, и уже из них выудил координаты.

----- добавлено через 20 сек. -----
Цитата:
Сообщение от fasadel Посмотреть сообщение
Была у меня такая задачка.
Ну и как ты её решил?
__________________
Почему все вдруг становятся умными, когда уже не надо?
Disney вне форума  
 
Непрочитано 04.03.2015, 22:00
#40
VVA

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


Цитата:
Сообщение от Disney Посмотреть сообщение
Разбил область на линии, и уже из них выудил координаты.
Все правильно. Ссылку на пример я приводил в #32
Цитата:
Сообщение от VVA Посмотреть сообщение
Что-то похожее было здесь
Фрагмент кода для иллюстрации
Код:
[Выделить все]
  (progn ;_ пересекаются
    (vl-cmdf "_.Region" pline "")(setq pline (entlast))
    (vl-cmdf "_.Region" otv "")(setq otv (entlast))
    (vl-cmdf "_subtract" pline "" otv "")
    (setq otv (entlast) nab (ssadd))
    (foreach item (vlax-invoke (vlax-ename->vla-object otv) 'Explode)
      (ssadd (vlax-vla-object->ename item) nab))
    (if (and (getvar "PEDITACCEPT") (= (getvar "PEDITACCEPT") 1))
    (vl-cmdf "_pedit" "_Multiple" nab "" "_Join" 0 "")
    (vl-cmdf "_pedit" "_Multiple" nab "" "_Y" "_Join" 0 ""))
    (setq pline (entlast) nab nil)
    (entdel otv)
    )
__________________
Как использовать код на Лиспе читаем здесь
VVA вне форума  
Ответ
Вернуться   Форум 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