Тема: Принадлежность точки криволинейному контуру
На форуме нашел алгоритм, определяющий, лежит ли точка в контуре, заданном линейными сегментами. А возможно ли это сделать, если в контур помимо линейных входят дуговые сегменты?
Информационный портал для профессионалов в области САПР
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
Форумы CADUser → Программирование → LISP → Принадлежность точки криволинейному контуру
Чтобы отправить ответ, вы должны войти или зарегистрироваться
На форуме нашел алгоритм, определяющий, лежит ли точка в контуре, заданном линейными сегментами. А возможно ли это сделать, если в контур помимо линейных входят дуговые сегменты?
> Михаил
Аппроксимировать дуговые сегменты линейными
> Михаил
Или использовать алгоритмы, учитывающие существование дуговых сегментов...
Например, я в своих проектах, использую подобный.
Жаль, не могу поделиться программой, но поделюсь алгоритмом.
1 - определяем направление обхода контура (по или против часовой)
2 - находим ближайшую точку на контуре
3 - находим первую производную
4 - находим угол между исходной точкой, ближайшей точкой на контуре и первой производной из точки на контуре
Всего, может быть несколько вариантов:
1 - точка на контуре, находится на сегменте, тогда анализ результатов вычислений п.1 + п.4 дадут точные данные о местоположении точки
2 - точка на контуре, находится точно на вершине котнура, тогда, необходимо повторить п.4 с предыдущим сегментом и анализировать положение точки, относительно обеих касательных...
Спасибо за советы! Как вариант, объединил оба ответа...Если есть алгоритм определения нахождения точки внутри контура из линейных сегментов, то можно его применить и для контура, если в него входят дуговые. Для этого определить ближайшую к заданной точке точку на контуре и если сегмент контура в этой точке будет дуговым, то аппроксимировать его всего двумя линейными сегментами (один из начала дуги в ближайшую точку контура заданной точке, другой - из этой же точки к концу дуги), и определить принадлежность точки линейному контуру по имеющемуся алгоритму.
> Михаил
Жаль, но должен вас разочаровать...
Как пример:
(entmakex '((0 . "POINT") (10 5.0 5.0 0.0))) (entmakex '((0 . "LWPOLYLINE") (100 . "AcDbEntity") (100 . "AcDbPolyline") (90 . 2) (70 . 1) (43 . 0.0) (38 . 0.0) (39 . 0.0) (10 5.0 -8.66025) (40 . 0.0) (41 . 0.0) (42 . -3.73205) (10 10.0 0.0) (40 . 0.0) (41 . 0.0) (42 . 0.0) (210 0.0 0.0 1.0) ) )
> Михаил
У тебя контур существует ввиде примитива или некий виртуальный?
Про контура еще зесь написано
http://www.arcada.com.ua/forum/viewtopi … ee25b56f7c
http://algolist.manual.ru/maths/geom/belong/poly2d.php
Вот-вот, я этот алгоритм и имел в виду, который "взят из статьи Мусина в журнале "Программирование....". У меня контур представляет собой замкнутую полилинию, но в любом случае по этому алгоритму создается список координат вершин, т.е. контур может быть и виртуальным...просто я считал, что в случае с дуговыми сегментами, можно предварительно в список координат добавлять координаты еще одной точки, которая будет лежать на контуре и являться ближайшей к заданной,
> Евгений Елпанов
Согласен, в этом случае это не сработает
В этом случае скорее всего придется добавлять еще одну точку на дуговом сегменте чтобы отсечь 180 градусов...я так понимаю, что это случай, когда значение кривизны больше 1
> Михаил
Если у тебя существующая полилиния, то
вот здесь http://dwg.ru/dnl/607 есть команда ConvTo2d для аппроксимации дуговых сегментов.
Если пишешь на лиспе, то можешь воспользоваться имеющимися там ф-циями
(TraceToLWPlineObj (vlax-ename->vla-object (car(entsel"\nУкажи полилинию"))))
Получить полилинию с аппроксимированными дуговыми сегментами
(TraceToLWPlinePoint (vlax-ename->vla-object (car(entsel"\nУкажи полилинию"))))
Получишь просто список точек полилинии с аппроксимированными дуговыми сегментами. Потом его можешь скармливать другим алгоритмам
> Михаил
Можно еще использовать чисто автокадовский метод,
релизованный в функции PointInside на сайте:
http://www.cadforyou.spb.ru/index.php?c … tions_page
~'J'~
> Fatty
У тебя там идет создание 2 примитивов. Тогда уж проще создавать луч и считать количество пересечений (идея не моя).
алгоритм взят на http://algolist.manual.ru/maths/geom/belong/poly2d.php
условие для Boundary - car и last одна и та же точка
(defun vk_IsPointInside (Point Boundary / FarPoint) (setq FarPoint (cons (+ (apply 'max (mapcar 'car Boundary)) 1.0) (cdr Point))) (not (zerop (rem (length (vl-remove nil (mapcar (function (lambda (p1 p2) (inters Point FarPoint p1 p2))) Boundary (cdr Boundary) ) ) ) 2 ) ) ) )
> Vovka
Алгоритм известный но работает
только с прямолинейными сегментами
~'J'~
> Кулик Алексей aka kpblc
Во-во, давай напиши и залей туда же для разнообразия,
помогай питерским :)
~'J'~
> Fatty
Дык ета... Он (в смысле реализованный алгоритм) вроде был у KAI: http://geol-dh.ru/ Точнее: http://geol-dh.narod.ru/spds/func-is-in-contour.html
> Кулик Алексей aka kpblc
Спасибо за ссылку, теперь вроде получился
неплохой набор на все вкусы, а кому и пригодится
кто будет потом искать :)
~'J'~
> Vovka
Спасибо за ф-цию.
Немного доделал для контуров, у которых есть самопересечения (не выпуклые). Корректно определяет принадлежность точки контуру, если оне на границе контура.
;* алгоритм взят на http://algolist.manual.ru/maths/geom/belong/poly2d.php ;* На основе vk_IsPointInside ;* Опубликовано https://www.caduser.ru/forum/topic36191.html ;* 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) (cdr 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-6 ) ;_ 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
Наверное тоже, что и у KAI, только покороче.
Тут возник вопрос:
Если точка внутри контура, то незачем определять на границе ли она.
Теперь сам вопрос. Как работает конструкция OR
(OR <точка внутри контура?> <точка на границе контура?> )
Если <точка внутри контура?> вернула Т OR выполняет конструкцию <точка на границе контура?> или возвращает T не выполняя <точка на границе контура?> ??
Обычно выполнение OR прекращается после нахождения первого t, насколько я понимаю. То есть если <точка внутри контура?> вернет t, то вход в <точка на границе контура?> выполнен не будет. Смысла нет.
> Кулик Алексей aka kpblc
Я тоже так думал, но сумневался немного
> VVA
(or t (princ "'(or t t)")) (or nil (princ "'(or nil t)"))
> Евгений Елпанов
Теперь не сомневаюсь :)
> VVA
Не работает с кривыми так же как и предыдущая
к сожалению, а жаль красивый код
~'J'~
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Форумы CADUser → Программирование → LISP → Принадлежность точки криволинейному контуру
Форум работает на PunBB, при поддержке Informer Technologies, Inc