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

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

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

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

Контур - замкнутая 2D-полилиния неправильной формы.
Как программно определить, лежит ли точка с координатами X и Y внутри контура ?
Нужна не готовая функция, а просто подходы к решению.
А может уже есть стандартная из серии VLA-....?
Просмотров: 32727
 
Непрочитано 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)
Если бы точка была снаружи, то угл был бы отрицательным, если контур по часовой стрелке, то результаты надо инвертировать т.е. внутри отрицательный и снаружи положительный.

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

Хочу пояснить еще один момент, если у контура несколько последовательных вершин совпадают, т.е сегмент имеет нулевую длину, то угол будет всегда равен нулю и необходимо искать последнюю вершину в списке совпадающих.
__________________
Чем гениальнее ваш план, тем меньше людей с ним будут согласны.
/Сунь Цзы/
Елпанов Евгений вне форума  
 
Непрочитано 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 вне форума  
 
Непрочитано 30.05.2016, 20:19
#41
gomer

строю, ломаю
 
Регистрация: 03.04.2008
Украина
Сообщений: 5,515


подниму темку, чтоб не создавать новую... Собственно сабж: Допустим есть некий контур (р1 р2 ... рn) и есть прямоугольник, заданный списком (list (list x y) width height). Необходимо определить, лежит ли прямоугольник внутри контура, находится ли за его пределами или пересекает контур, причем прямоугольник может иметь вершины на границе контура. Это меня больше всего смущает, так как проверка принадлежности вершин прямоугольника контуру не работает
gomer вне форума  
 
Непрочитано 30.05.2016, 20:23
#42
Кулик Алексей aka kpblc
Moderator

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


Контур и прямоугольник существуют в чертеже или они "виртуальные"?
__________________
Моя библиотека lisp-функций
---
Обращение ко мне - на "ты".
Все, что сказано - личное мнение.
Кулик Алексей aka kpblc вне форума  
 
Непрочитано 30.05.2016, 20:40
#43
trir


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


https://en.wikipedia.org/wiki/DE-9IM
trir вне форума  
 
Непрочитано 30.05.2016, 20:48
#44
gomer

строю, ломаю
 
Регистрация: 03.04.2008
Украина
Сообщений: 5,515


Цитата:
Сообщение от Кулик Алексей aka kpblc Посмотреть сообщение
Контур и прямоугольник существуют в чертеже или они "виртуальные"?
Виртуальные контур задается набором точек, прямоугольник точкой и размерами

Цитата:
Сообщение от trir Посмотреть сообщение
https://en.wikipedia.org/wiki/DE-9IM
не ругайся, можешь популярно на пальцах объяснить метод?
gomer вне форума  
 
Непрочитано 30.05.2016, 20:58
#45
Кулик Алексей aka kpblc
Moderator

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


Если у тебя контур не содержит дуговых сегментов, то чем не устраивает inters ?
__________________
Моя библиотека lisp-функций
---
Обращение ко мне - на "ты".
Все, что сказано - личное мнение.
Кулик Алексей aka kpblc вне форума  
 
Непрочитано 30.05.2016, 21:48
#46
gomer

строю, ломаю
 
Регистрация: 03.04.2008
Украина
Сообщений: 5,515


Цитата:
Сообщение от Кулик Алексей aka kpblc Посмотреть сообщение
Если у тебя контур не содержит дуговых сегментов, то чем не устраивает inters ?
во первых не понятно, что делать, если одна или несколько точек лежит на контуре
gomer вне форума  
 
Непрочитано 30.05.2016, 23:22
#47
Кулик Алексей aka kpblc
Moderator

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


В таком случае inters возвращает точку, лежащую на прямой, насколько я помню.
P.S. Только что проверил - так и есть:
Код:
[Выделить все]
(setq pt1 '(2402.409793472364 1829.035665492093)
pt2 '(3291.370801813302 1135.601769925651)
pt3 '(1312.931107424096 951.4967684136836)
pt4 '(2926.630530332957 2251.278058244966))
(inters pt1 pt2 pt3 pt4) ; '(2402.409793472364 1829.035665492093)
Сделал тупо: нарисовал два отрезка, вершину одного из них положил на второй, получил точки - и проверил в inters
__________________
Моя библиотека lisp-функций
---
Обращение ко мне - на "ты".
Все, что сказано - личное мнение.
Кулик Алексей aka kpblc вне форума  
 
Непрочитано 30.05.2016, 23:31
#48
Дима_

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


Если это не метод который надо крутить миллионами раз друг к другу - то создаешь две области (Region) и делаешь вычитание их копий. Если кто-то пропадает - то он внутри другого. Остаются как есть - без пересечения иначе - пересекаются.
з.ы. случайно не на "сетку" режешь?
в конце темы код и описание
__________________
Когда в руках молоток все вокруг кажется гвоздями.
Дима_ вне форума  
 
Непрочитано 31.05.2016, 01:59
#49
gomer

строю, ломаю
 
Регистрация: 03.04.2008
Украина
Сообщений: 5,515


Цитата:
Сообщение от Кулик Алексей aka kpblc Посмотреть сообщение
В таком случае inters возвращает точку, лежащую на прямой, насколько я помню.
Понятно, что на прямой, непонятно, внутри контура прямоугольник в таком случае или нет. В общем состряпал код, но загвоздка именно в определении состояния прямоугольника. Идея была простая, если все вершины прямоугольника внутри контура, то прямоугольник внутри контура, если какие-то точки есть и внутри и снаружи, то есть пересечение, иначе не пересекает, взял функцию пересечения отсюда, погонял, вроде работает, а на выходе белеберда получилась, хотя может я где-то ошибся.
Если по хорошему не получится, придется рисовать и удалять, но мне это не очень нравится, должен быть математический путь
Вложения
Тип файла: zip test.zip (26.8 Кб, 30 просмотров)
gomer вне форума  
 
Непрочитано 31.05.2016, 07:04
#50
Владимир_М


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


Цитата:
Сообщение от gomer Посмотреть сообщение
Понятно, что на прямой, непонятно, внутри контура прямоугольник в таком случае или нет.
Может быть использовать Offset, использовать вспомогательный контур с каким-то минимальным отступом, сравнивать площади контуров, а также их пересечение с прямоугольником.. Несколько для другой задачи (армирование по контуру) использовал эту функцию...
(в качестве доп. идеи):
Код:
[Выделить все]
offsetObj = returnObj.Offset(zt / mk)
If returnObj.Area < offsetObj(0).Area Then
    offsetObj(0).Delete
    offsetObj = returnObj.Offset(-zt / mk)
End If
Владимир_М вне форума  
 
Непрочитано 31.05.2016, 09:08
#51
Кулик Алексей aka kpblc
Moderator

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


Владимир_М, это предполагает построение примитивов, чего хотелось бы избежать
__________________
Моя библиотека lisp-функций
---
Обращение ко мне - на "ты".
Все, что сказано - личное мнение.
Кулик Алексей aka kpblc вне форума  
 
Непрочитано 31.05.2016, 10:13
#52
hexD

КМД
 
Регистрация: 26.03.2013
Я ЖЫВУ В РОССИИ.
Сообщений: 506
<phrase 1=


Цитата:
Сообщение от gomer Посмотреть сообщение
подниму темку, чтоб не создавать новую... Собственно сабж: Допустим есть некий контур (р1 р2 ... рn) и есть прямоугольник, заданный списком (list (list x y) width height). Необходимо определить, лежит ли прямоугольник внутри контура, находится ли за его пределами или пересекает контур, причем прямоугольник может иметь вершины на границе контура. Это меня больше всего смущает, так как проверка принадлежности вершин прямоугольника контуру не работает
В свое время начал что то такое писать(маленький пиар)
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.
hexD вне форума  
 
Непрочитано 31.05.2016, 10:52
#53
Puroshev


 
Регистрация: 22.10.2008
Сообщений: 73
Отправить сообщение для Puroshev с помощью Skype™


Вот когда-то нашел, кто автор не знаю, но ему спасибо
Код:
[Выделить все]
 
; Функция Kontur возвращает 0 или 1 в зависимости где находится точка
    ;(setq _e1 (car(entsel "\nВыбери полилинию-контур: ")))
    ;(setq _pt1 (getpoint "\nУкажи точку (не на контуре): "))

(defun Kontur ( _e1 _Pt1 /)
  (vl-load-COM)
  (and
    (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))
          (setq _Kon 0)
          (setq _Kon 1)
          )
        )
      (progn  ;;; если контур против часовой стрелки
        (if (minusp (last _ang))
          (setq _Kon 1) ;(alert "Точка внутри")
          (setq _Kon 0);(alert "Точка снаружи")
          )
        )
      )
    )
  (setq _kon _Kon)
  )
;********************************
; Векторное произведение векторов
;********************************
; 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)
(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)
  )
 ;************************************************************************
 ;************************************************************************
 ;************************************************************************
----- добавлено через ~2 мин. -----
Нашел автора: Елпанов Евгений.
Puroshev вне форума  
 
Непрочитано 31.05.2016, 11:31
#54
VVA

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


Вроде как алгоритм работает. Зеленые - внутри контура, черные - вне, красный - частично в контуре
Код:
[Выделить все]
 
(defun C:TEST ( / str)
  (SSSETFIRST nil nil)
  (setq Boundary1 (car (entsel "\nВыберите контур (полилиния): ")))
  (SSSETFIRST nil (ssadd Boundary1))
  (setq rect1 (car (entsel "\nВыберите прямоугольник (полилиния): ")))
  (SSSETFIRST nil (ssadd Boundary1 (ssadd rect1)))
  (setq Boundary (coords Boundary1))
  (setq rect (coords rect1))
  (setq ret
         (mapcar 'mip_IsPointInside
                 rect
                 (mapcar '(lambda (x) Boundary) rect)
         ) ;_ end of mapcar
  ) ;_ end of setq
  (cond
    ((apply 'and ret) (setq str "Прямоугольник целиком в контуре"))
    ((eq (length(vl-remove T ret)) 3)(setq str "Прямоугольник НЕ в контуре\nКасается одной точкой"))
    ((apply 'or ret) (setq str "Прямоугольник частично в контуре"))
    ((not (apply 'and ret))
     (setq str "Прямоугольник НЕ в контуре")
    )
    (t (setq str "Не опознано"))
  ) ;_ end of cond
  (princ)
  (vla-sendcommand (vlax-get-property(vlax-get-acad-object) 'activedocument) (strcat "(alert " "\"" str "\"" ")\n"))
) ;_ end of defun
;* алгоритм взят на http://algolist.manual.ru/maths/geom/belong/poly2d.php
;* На основе vk_IsPointInside
;* Опубликовано  http://www.caduser.ru/forum/index.php...&TID=36191
;               http://forum.dwg.ru/showthread.php?p=1538162#post1538162
;* Boundary - список нормализованных [т.е. только либо (X Y) либо (X Y Z)] точек
(defun mip_IsPointInside (Point Boundary / FarPoint)
  ;_Проверяет Boundary на условие car и last одна и та же точка
  (if (not (equal (car Boundary)(last Boundary) 1e-6))
    (setq Boundary (append Boundary (list(car Boundary)))))
  (setq FarPoint (cons (+ (apply 'max (mapcar 'car Boundary)) 1.0)
                       (list(+ (apply 'max (mapcar 'cadr Boundary)) 1.0 (cadr Point)))
                 ) ;_ end of cons
  ) ;_ end of setq
  (or
    (not
      (zerop
        (rem
          (length
            (vl-remove
              nil
              (mapcar
                (function (lambda (p1 p2) (inters Point FarPoint p1 p2))
                ) ;_ end of function
                Boundary
                (cdr Boundary)
              ) ;_ end of mapcar
            ) ;_ end of vl-remove
          ) ;_ end of length
          2
        ) ;_ end of rem
      ) ;_ end of zerop
    ) ;_ end of not
    (vl-some (function (lambda (x)
                         x
                       ) ;_ end of lambda
             ) ;_ end of function
             (mapcar
               (function (lambda (p1 p2)
                           (equal (+ (distance Point p1)
                                     (distance Point p2)
                                  ) ;_ end of +
                                  (distance p1 p2)
                                  1e-3
                           ) ;_ end of equal
                         ) ;_ end of lambda
               ) ;_ end of function
               Boundary
               (cdr Boundary)
             ) ;_ end of mapcar
    ) ;_ end of vl-some
  ) ;_ end of or
) ;_ end of defun
(defun coords (en)
  (mapcar 'cdr
	  (vl-remove-if-not
	    (function (lambda (x) (= 10 (car x))))
	    (entget en)
	  )
  )
)
Вложения
Тип файла: dwg
DWG 2007
test.dwg (79.5 Кб, 28 просмотров)
__________________
Как использовать код на Лиспе читаем здесь

Последний раз редактировалось VVA, 31.05.2016 в 19:57.
VVA вне форума  
 
Непрочитано 31.05.2016, 14:02
#55
gomer

строю, ломаю
 
Регистрация: 03.04.2008
Украина
Сообщений: 5,515


Цитата:
Сообщение от VVA Посмотреть сообщение
Вроде как алгоритм работает.
VVA, спасибо но код не должен так работать, не знаю почему, но серые прямоугольники оказываются внутри контура... и я не могу понять почему так происходит
gomer вне форума  
 
Непрочитано 31.05.2016, 18:13
#56
VVA

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


Цитата:
Сообщение от gomer Посмотреть сообщение
но серые прямоугольники оказываются внутри контура...
Изменил алгоритм построения луча в mip_IsPointInside. Там получалось, что луч строился горизонтально, 3-я вершина контура с координатами 128,64 лежала на этом луче. Поэтому две примыкающие стороны давали перечение. В итоге получалось 2 пересечения, хотя контур пересекается один раз в вершине. Четное количество пересечений - точка вне контура.
Обновил #54 Тестируй.
__________________
Как использовать код на Лиспе читаем здесь
VVA вне форума  
 
Непрочитано 31.05.2016, 19:38
#57
Vov.Ka


 
Регистрация: 21.07.2008
Луцьк
Сообщений: 179


можно еще попробовать вот это http://www.cadtutor.net/forum/showth...l=1#post263330
там немного другой способ
Vov.Ka вне форума  
 
Непрочитано 31.05.2016, 19:41
#58
gomer

строю, ломаю
 
Регистрация: 03.04.2008
Украина
Сообщений: 5,515


Цитата:
Сообщение от VVA Посмотреть сообщение
Изменил алгоритм построения луча в mip_IsPointInside.
VVA, благодарю вас, это почти то, что надо, единственный момент - если прямоугольник касается контура снаружи, то он считается частично в контуре, для меня это означат лишние итерации в программе
gomer вне форума  
 
Непрочитано 31.05.2016, 20:01
#59
VVA

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


В этом случае mip_IsPointInside вернет список из одного T и трех NIL. Добавил проверку в #54

----- добавлено через ~12 ч. -----
*** Добавлено ***
Для упрощения анализа можно "обернуть" функцию mip_IsPointInside, которая будет возвращать не T или NIL, а 1 или 0. И анализировать сумму чисел полученного списка( 0 - не в контуре, 1 - касается одной точкой или одна точка в контуре (недостающие ф-ции в #54)
Код:
[Выделить все]
 
(defun C:TEST1 ( / str)
  (SSSETFIRST nil nil)
  (setq Boundary1 (car (entsel "\nВыберите контур (полилиния): ")))
  (SSSETFIRST nil (ssadd Boundary1))
  (setq rect1 (car (entsel "\nВыберите прямоугольник (полилиния): ")))
  (SSSETFIRST nil (ssadd Boundary1 (ssadd rect1)))
  (setq Boundary (coords Boundary1))(setq rect (coords rect1))
  (setq ret (mapcar '_IsPointInside rect (mapcar '(lambda (x) Boundary) rect))) ;_ end of setq
  (cond
    ((> (apply '+ ret) 3)(setq str "Прямоугольник целиком в контуре"))
    ((= (apply '+ ret) 1)(setq str "Прямоугольник НЕ в контуре\nКасается одной точкой"))
    ((> (apply '+ ret) 1) (setq str "Прямоугольник частично в контуре"))
    ((zerop (apply '+ ret))(setq str "Прямоугольник НЕ в контуре"))
    (t (setq str "Не опознано"))
  ) ;_ end of cond
  (vla-sendcommand (vlax-get-property(vlax-get-acad-object) 'activedocument)
    (strcat "(alert " "\"" str "\"" ")\n"))
) ;_ end of defun
(defun _IsPointInside (Point Boundary)(if (mip_IsPointInside Point Boundary) 1 0))
__________________
Как использовать код на Лиспе читаем здесь

Последний раз редактировалось VVA, 01.06.2016 в 08:19.
VVA вне форума  
 
Непрочитано 01.06.2016, 08:17
#60
VVA

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


*** Добавлено2 ***
Цитата:
Сообщение от gomer Посмотреть сообщение
единственный момент - если прямоугольник касается контура снаружи, то он считается частично в контуре, для меня это означат лишние итерации в программе
В таком случае синий и зеленый квадрат будут считаться не в контуре. Это правильно?
Миниатюры
Нажмите на изображение для увеличения
Название: tr.png
Просмотров: 18
Размер:	2.7 Кб
ID:	171432  
__________________
Как использовать код на Лиспе читаем здесь
VVA вне форума  
 
Непрочитано 01.06.2016, 14:34
#61
gomer

строю, ломаю
 
Регистрация: 03.04.2008
Украина
Сообщений: 5,515


Цитата:
Сообщение от VVA Посмотреть сообщение
В таком случае синий и зеленый квадрат будут считаться не в контуре. Это правильно?
Да, вопрос именно в этом, что мы понимаем под словом "внутри" и "снаружи". Как вариант можно рассмотреть игнор пограничных точек, но тогда нужно проверять принцип погрраничности, а затраты на это действие зависят от многоугольника границы
gomer вне форума  
 
Непрочитано 01.06.2016, 18:41
#62
VVA

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


Если немного переписать функцию, то можно анализировать все варианты
Код:
[Выделить все]
 
 
(defun C:TEST2 ( / str)
  (SSSETFIRST nil nil)
  (setq Boundary1 (car (entsel "\nВыберите контур (полилиния): ")))
  (SSSETFIRST nil (ssadd Boundary1))
  (setq rect1 (car (entsel "\nВыберите прямоугольник (полилиния): ")))
  (SSSETFIRST nil (ssadd Boundary1 (ssadd rect1)))
  (setq Boundary (coords Boundary1))
  (setq rect (coords rect1))
  (setq ret
         (mapcar 'mip_IsPointInside1
                 rect
                 (mapcar '(lambda (x) Boundary) rect)
         ) ;_ end of mapcar
  ) ;_ end of setq
  (cond
    ((equal (apply '+ ret) 4 1e-3)(setq str "Прямоугольник целиком в контуре"))
    ((equal (apply '+ ret) 3.1 1e-3)(setq str "Прямоугольник 3 точки в контуре, одна на границе"))
    ((equal (apply '+ ret) 2.2 1e-3)(setq str "Прямоугольник 2 точки в контуре, ДВЕ на границе"))
    ((equal (apply '+ ret) 1.3 1e-3)(setq str "Прямоугольник 1 точка в контуре, ТРИ на границе"))
    ((equal (apply '+ ret) 0.4 1e-3)(setq str "Прямоугольник ЧЕТЫРЕ точки на границе"))
    ((equal (apply '+ ret) 3 1e-3)(setq str "Прямоугольник 3 точки в контуре, одна за пределами"))
    ((equal (apply '+ ret) 2 1e-3)(setq str "Прямоугольник 2 точки в контуре, ДВЕ за пределами"))
    ((equal (apply '+ ret) 1 1e-3)(setq str "Прямоугольник 1 точка в контуре, ТРИ за пределами"))
    ((equal (apply '+ ret) 0.1 1e-3)(setq str "Прямоугольник 1 точка на границе, ТРИ за пределами"))
    ((equal (apply '+ ret) 0.2 1e-3)(setq str "Прямоугольник 2 точки на границе, ДВЕ за пределами"))
    ((equal (apply '+ ret) 0.3 1e-3)(setq str "Прямоугольник 3 точки на границе, ОДНА за пределами"))
    ((zerop (apply '+ ret))(setq str "Прямоугольник за пределами"))
    (t (setq str "Не опознано"))
  ) ;_ end of cond
  (princ)
  (vla-sendcommand (vlax-get-property(vlax-get-acad-object) 'activedocument) (strcat "(alert " "\"" str "\"" ")\n"))
) ;_ end of defun
;* алгоритм взят на http://algolist.manual.ru/maths/geom/belong/poly2d.php
;* На основе vk_IsPointInside
;* Опубликовано  http://www.caduser.ru/forum/index.php...&TID=36191
;               http://forum.dwg.ru/showthread.php?p=1538162#post1538162
;* Boundary - список нормализованных [т.е. только либо (X Y) либо (X Y Z)] точек
(defun mip_IsPointInside1 (Point Boundary / FarPoint)
  ;_Проверяет Boundary на условие car и last одна и та же точка
  (if (not (equal (car Boundary)(last Boundary) 1e-6))
    (setq Boundary (append Boundary (list(car Boundary)))))
  (setq FarPoint (cons (+ (apply 'max (mapcar 'car Boundary)) 1.0)
                       (list(+ (apply 'max (mapcar 'cadr Boundary)) 1.0 (cadr Point)))
                 ) ;_ end of cons
  ) ;_ end of setq
  (cond
    ((vl-some (function (lambda (x)   ;_На границе
                         x
                       ) ;_ end of lambda
             ) ;_ end of function
             (mapcar
               (function (lambda (p1 p2)
                           (equal (+ (distance Point p1)
                                     (distance Point p2)
                                  ) ;_ end of +
                                  (distance p1 p2)
                                  1e-3
                           ) ;_ end of equal
                         ) ;_ end of lambda
               ) ;_ end of function
               Boundary
               (cdr Boundary)
             ) ;_ end of mapcar
    ) ;_ end of vl-some
     (setq ret 0.1)
     )
    ((not    ;_Внутри
      (zerop
        (rem
          (length
            (vl-remove
              nil
              (mapcar
                (function (lambda (p1 p2) (inters Point FarPoint p1 p2))
                ) ;_ end of function
                Boundary
                (cdr Boundary)
              ) ;_ end of mapcar
            ) ;_ end of vl-remove
          ) ;_ end of length
          2
        ) ;_ end of rem
      ) ;_ end of zerop
    ) ;_ end of not
     (setq ret 1)
     )
    (t (setq ret 0)) ;_Снаружи
  ) ;_ end of cond
) ;_ end of defun
(defun coords (en)
  (mapcar 'cdr
	  (vl-remove-if-not
	    (function (lambda (x) (= 10 (car x))))
	    (entget en)
	  )
  )
)
----- добавлено через ~15 ч. -----
Единственное улучшение - возвращать можно целые числа:
0 - не в контуре
100 - в контуре
1 - на границе
И сравнивать целые числа
400 - 4 точти внутри контура
300 - 3 точки внутри, одна снаружи
301 - 3 точки внутри, одна на границе
и т.д.
Вложения
Тип файла: dwg
DWG 2007
test.dwg (67.0 Кб, 22 просмотров)
__________________
Как использовать код на Лиспе читаем здесь
VVA вне форума  
 
Непрочитано 27.04.2022, 14:33
#63
АлексЮстасу

топограф, технолог
 
Блог
 
Регистрация: 24.05.2009
Москва
Сообщений: 3,029


Хорошо действует Принадлежность точки криволинейному контуру VVA.
Действует для линейных объектов, образующих контуры:
Код:
[Выделить все]
 ("AcDb2dPolyline" "AcDbPolyline" "AcDb3dPolyline"
  "AcDbCircle" "AcDbArc" "AcDbEllipse"
  "AcDbSpline" "AcDbLine")
Но не для площадных, которым такая функция нужна не меньше, и которые линейные контуры косвенно представляют.
Для штриховок, регионов, мультиполигонов. В т.ч. для площадных объектов с отверстиями в них.
Можно ли расширить эту функцию для площадных объектов?
__________________
количество моих сообщений не говорит о знании Автокада
АлексЮстасу вне форума  
 
Непрочитано 03.06.2022, 19:44
#64
АлексЮстасу

топограф, технолог
 
Блог
 
Регистрация: 24.05.2009
Москва
Сообщений: 3,029


Пока нашел почти аналог 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.
АлексЮстасу вне форума  
 
Непрочитано 24.06.2022, 03:16
#65
АлексЮстасу

топограф, технолог
 
Блог
 
Регистрация: 24.05.2009
Москва
Сообщений: 3,029


In_Figure_Obj выдает ошибочный результат, если горизонтальный вправо луч из точки попадает на вершину контура.
И In_Figure_Obj на каких-то эллипсах (желтый) вообще зависает. На каких - закономерности не нашел.

Проверял так:
Код:
[Выделить все]
(in_figure_obj (getpoint "\nPoint:") (car (entsel)))
Миниатюры
Нажмите на изображение для увеличения
Название: In_Figure_Obj.png
Просмотров: 33
Размер:	26.9 Кб
ID:	248222  
Вложения
Тип файла: dwg
DWG 2018
In_Figure_Obj.dwg (807.7 Кб, 13 просмотров)
__________________
количество моих сообщений не говорит о знании Автокада
АлексЮстасу вне форума  
 
Непрочитано 27.06.2022, 08:43
#66
VVA

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


Цитата:
Сообщение от АлексЮстасу Посмотреть сообщение
Пока нашел почти аналог In_Figure_Obj - LM:Inside-p от Lee Mac, https://www.cadtutor.net/forum/topic...comment=254876.
Что-то на том форуме у меня с форматированием, не могу глянуть саму функцию
Нашел еще один вариант от Ли на болоте (требуется регистрация) https://www.theswamp.org/index.php?topic=43550.0
Код:
[Выделить все]
;; Point Inside-p  -  Lee Mac https://www.theswamp.org/index.php?topic=43550.0
;; Utilises a ray-casting algorithm to determine whether a
;; given point (WCS) resides within a supplied object.

(defun LM:PointInside-p ( pt obj / lst ray )
    (setq lst
        (vlax-invoke
            (setq ray
                (vla-addray
                    (vla-objectidtoobject (vla-get-document obj) (vla-get-ownerid obj))
                    (vlax-3D-point pt)
                    (vlax-3D-point (vlax-curve-getclosestpointto obj pt))
                )
            )
            'intersectwith obj acextendnone
        )
    )
    (vla-delete ray)
    (= 1 (logand 1 (length lst)))
)

(defun c:test ( / ent obj pnt )
    (if (setq ent (car (entsel "\nSelect Polyline: ")))
        (if (vlax-method-applicable-p (setq obj (vlax-ename->vla-object ent)) 'intersectwith)
            (while (setq pnt (getpoint "\nPick Point: "))
                (if (LM:PointInside-p (trans pnt 1 0) obj)
                    (alert "Point is INSIDE")
                    (alert "Point is OUTSIDE")
                )
            )
            (princ "\nInvalid Object selected.")
        )
    )
    (princ)
)
(vl-load-com) (princ)
И с этого же форума из этой темы Point Containment Test: Convex and Concave Polygons
Код:
[Выделить все]
(defun isPtinPM	(pt pts eps / is at)
  ;; by 狂刀  Handed Knife
  ;; Edit by GSLS(SS) 2011.03.28
  ;; Solved the problem : if a point at the given polygon , it perhap return T or NIL .
  ;; http://www.theswamp.org/index.php?topic=7785.15

  (setq	is(equal PI(abs(apply(function +)(mapcar(function(lambda (x y / a)							   
		       (setq a (rem (- (angle pt x) (angle pt y)) PI))
		       (if (equal a 0.0 eps)(setq at T))a))
		   (cons (last pts) pts) pts))) eps))
  (cond (at 0)(is 1)(T -1))
)
(defun c:test (/ pts pt is)
  (setq pts (ss-assoc 10 (entget (car (entsel "Select a polyline :")))))
  (while (setq pt (getpoint "Select point:>"))
    (setq is (isPtinPM pt pts 1e-8))
    (cond ((= is -1) (alert "Out ."))
	  ((= is 0) (alert "At ."))
	  ((= is 1) (alert "In ."))
    )
  )
  (princ)
)
----- добавлено через ~2 мин. -----
Публикую без проверки. LM:PointInside-p использует метод 'intersectwith, поэтому должна работать и с полигонами и проч, ели автодеск заложил такую возможность
__________________
Как использовать код на Лиспе читаем здесь
VVA вне форума  
 
Непрочитано 27.06.2022, 12:07
#67
andriadi

геолог
 
Регистрация: 30.01.2016
КМВ
Сообщений: 145


Помнится давно такую задачку решал в FoxPro через неравенства и координаты точек.
andriadi вне форума  
 
Непрочитано 27.06.2022, 12:46
#68
gumel


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


Код Александра Ривилиса:
Код:
[Выделить все]
 
enum PointContourStatus {
  OutsideContour  = -1, // Точка вне контура
  OnContour       =  0, // Точка на контуре
  InsideContour   =  1, // Точка внутри контура
  InternalError   = -99  // Ошибка
};
PointContourStatus is_point_in_curve(AcGePoint3d p, AcGePoint2dArray &pts, AcGeDoubleArray &blgs)
{
  AcDbMPolygon mpol;
  if (mpol.appendMPolygonLoop(pts,blgs) != Acad::eOk) return InternalError;
  AcGeIntArray ar;
  if (mpol.isPointOnLoopBoundary(p,0)) return OnContour;
  if (mpol.isPointInsideMPolygon(p,ar) > 0) return InsideContour;
  else return OutsideContour;
}
PointContourStatus is_point_in_curve(AcGePoint3d p, AcDbCurve *pCurv)
{
  double fuzz = AcGeContext::gTol.equalPoint();
  AcGePoint3d pointOnCurve;
  pCurv->getClosestPointTo(p,pointOnCurve);
  if (p.distanceTo(pointOnCurve) <= fuzz) return OnContour;
  AcDbPolyline   *pPoly   = AcDbPolyline::cast(pCurv);
  AcDb2dPolyline *p2Poly  = AcDb2dPolyline::cast(pCurv);
  AcDbCircle     *pCircle = AcDbCircle::cast(pCurv);
  AcDbMPolygon mpol;
  if (pPoly) {
    if (mpol.appendLoopFromBoundary(pPoly)   != Acad::eOk) return InternalError;
  } else if (p2Poly) {
    if (mpol.appendLoopFromBoundary(p2Poly)  != Acad::eOk) return InternalError;
  } else if (pCircle) {
    if (mpol.appendLoopFromBoundary(pCircle) != Acad::eOk) return InternalError;
  } else return InternalError;
  AcGeIntArray ar;
  if (mpol.isPointInsideMPolygon(p,ar) > 0) return InsideContour;
  else return OutsideContour;
}
Отсюда: https://www.caduser.ru/forum/topic22322.html
gumel вне форума  
 
Непрочитано 04.07.2022, 23:20
#69
АлексЮстасу

топограф, технолог
 
Блог
 
Регистрация: 24.05.2009
Москва
Сообщений: 3,029


Цитата:
Сообщение от VVA Посмотреть сообщение
Публикую без проверки.
LM:PointInside-p с регионами у меня не работает. Как и с мультиполигонами, штриховками и 3дфейсами.
Со сплайнами, с окружностями, с дуговыми сегментами работает. Для точек на границе выдает "; error: Automation Error. Points are coincident".
Для полилиний с самопересечениями может выдать и "Point is INSIDE", и "Point is OUTSIDE".
Т.е. ненадежно.
Так же несерьезно с isPtinPM. Во многих случаях выдает загадочное ""At", при том, что точки далеко от границ.
Цитата:
Сообщение от gumel Посмотреть сообщение
Код Александра Ривилиса:
Наверняка отличное решение, но не на лисп.
Если про другие языки, то феноменально быстрое и точное решение дал Debalance - https://dwg.ru/b/topomap/287 и т.д.
__________________
количество моих сообщений не говорит о знании Автокада
АлексЮстасу вне форума  
 
Непрочитано 10.11.2023, 04:14 Еще 11 лет назад сталкивался
#70
AlexeyG


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


В общем, 11 лет назад поломал голову. Решение такое. Берем произвольную прямую, проходящую через точку. Для простоты, можно взять горизонтальную (т.е. Y не меняется) и считаем число пересечений контура с этой прямой слева и справа. если оба получившихся числа нечетные - точка в контуре. И не надо всякие углы изобретать.
AlexeyG вне форума  
 
Непрочитано 10.11.2023, 06:40
#71
SetQ

конструктор
 
Регистрация: 21.07.2007
Петрозаводск
Сообщений: 1,969


Цитата:
Сообщение от AlexeyG Посмотреть сообщение
Решение такое. Берем произвольную прямую, проходящую через точку. Для простоты, можно взять горизонтальную (т.е. Y не меняется) и считаем число пересечений контура с этой прямой слева и справа. если оба получившихся числа нечетные - точка в контуре.
Надо не спутать пересечение с точкой касания, а касание - с касанием в точке перегиба.
SetQ вне форума  
 
Непрочитано 10.11.2023, 12:47
#72
AlexeyG


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


Цитата:
Сообщение от SetQ Посмотреть сообщение
Надо не спутать пересечение с точкой касания, а касание - с касанием в точке перегиба.
Конечно, этот случай надо обрабатывать отдельно и не учитывать. А так, все отлично работает. Код сложно привести, там случай существенно сложнее идеализированного контура и точки, большой, и вряд ли кто-то будет ковыряться. Главное идея.
AlexeyG вне форума  
Ответ
Вернуться   Форум 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