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

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

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

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

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


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

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


Пока нашел почти аналог 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,030


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
КМВ
Сообщений: 147


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


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


Код Александра Ривилиса:
Код:
[Выделить все]
 
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,030


Цитата:
Сообщение от 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,971


Цитата:
Сообщение от 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