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

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

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

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

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