Print Page - Point is Inside polyline (Now with Bulges)

Code Red => AutoLISP (Vanilla / Visual) => Topic started by: ymg on December 10, 2014, 12:56:28 PM

Title: Point is Inside polyline (Now with Bulges)
Post by: ymg on December 10, 2014, 12:56:28 PM

Yet another function to test if a point is inside a polyline.
This one based on the winding number method.

I've looked for existing function but could not find one using this method.

Should work for any kind of closed poly, even self-intersecting.

Would appreciate feedback!

ymg

Code - Auto/Visual Lisp: [Select]

;;============================================================================;
;;                                                                            ;
;;      PtInPoly_p(): Winding number test for a point in a polygon            ;
;;                                                                            ;
;;      Input:    p = a point                                                 ;
;;               en = ename or vla-object of a closed polyline.               ;
;;                                                                            ;
;;      Return:  t, if point is in polyline. (wn is not 0)                    ;
;;                                                                            ;
;; Original code in C++ by Dan Sunday                                         ;
;; See: http://geomalgorithms.com/a03-_inclusion.html                         ;
;;============================================================================;
 
(defun PtInPoly_p (p en / i l p1 p2 v wn y)
 
   ;; Returns t if point p is strictly to the left of v1->v2   by ymg         ;
   (defun isleft (p v1 v2 / xp yp)
       (setq  xp (car  p)  yp (cadr  p))
       (minusp (- (* (- (cadr v1) yp) (- (car v2) xp)) (* (- (car v1) xp) (- (cadr v2) yp)))) 
   )
  
  
   (setq i (+ (vlax-curve-getEndParam en) 1))                 
   (while (setq v (vlax-curve-getPointAtParam en (setq i (1- i))))
       (setq l (cons v l))
   )
   
  
   (setq p1 (car  l)
          y (cadr p)
         wn 0                               
   )      
  
   ;; Loop through all edges of polygon.                                      ;
   (foreach p2 (cdr l) 
      (if (<= (cadr p1) y)
         (if (> (cadr p2) y)                          
            (if (isleft p p1 p2) (setq wn (1+ wn)))
         )  
         (if (<= (cadr p2) y)
            (if (isleft p p2 p1) (setq wn (1- wn)))
         )
      )
      (setq p1 p2)
   )
   (not (zerop wn))
) 
 

Title: Re: Point is Inside polyline
Post by: VovKa on December 11, 2014, 05:33:13 AM

here is something like yours
http://www.cadtutor.net/forum/showthread.php?39199-Identify-a-polyline-by-a-point-inside-this-polyline&p=263330&viewfull=1#post263330

Title: Re: Point is Inside polyline
Post by: ymg on December 11, 2014, 08:23:58 AM

VovKa,

Yes essentially the same method.

You did it recursively, nice!

ymg

Title: Re: Point is Inside polyline
Post by: AARYAN on December 11, 2014, 02:00:36 PM

Thank You so much ymg.
Your routine works great!!!

Title: Re: Point is Inside polyline
Post by: ymg on December 11, 2014, 07:30:21 PM

AARYAN,

You are very welcome!!, but VovKa was there before me.

Do test it though, as I did not test every situation.

ymg

Title: Re: Point is Inside polyline
Post by: Marc'Antonio Alessi on December 12, 2014, 04:40:51 AM

Quote from: VovKa on December 11, 2014, 05:33:13 AM

here is something like yours
http://www.cadtutor.net/forum/showthread.php?39199-Identify-a-polyline-by-a-point-inside-this-polyline&p=263330&viewfull=1#post263330 (http://www.cadtutor.net/forum/showthread.php?39199-Identify-a-polyline-by-a-point-inside-this-polyline&p=263330&viewfull=1#post263330)

I have test your function and about: ; works with polygons only, i.e. if (equal (car PointsList) (last PointsList))
it works in many cases, but not in the case "D" see figure (4 vertices). Do you think it's better to pass the last vertex in all cases where it is not equal to the first?

Code: [Select]

(defun c:test (/ ent pt PntLst)
  (if
    (and
      (setq ent (car (entsel "\nLWPolyline: ")))
      (setq pt (getpoint "\nPt: "))
      (setq PntLst (mapcar 'cdr (vl-remove-if-not (function (lambda (x) (eq 10 (car x)))) (entget ent))))
    )
    (progn
      (princ "\nequal:  ")(princ (equal (car PntLst) (last PntLst)))
      (princ "\nIsPointInside:  ")(princ (vl-princ-to-string (vk_IsPointInside pt PntLst)))
      (princ "     PtInPoly_p:  ")(princ (vl-princ-to-string (PtInPoly_p        pt ent)))
    )
  )
  (princ)
)

Title: Re: Point is Inside polyline
Post by: VovKa on December 12, 2014, 05:42:25 AM

Quote from: Marc'Antonio Alessi on December 12, 2014, 04:40:51 AM

Do you think it's better to pass the last vertex in all cases where it is not equal to the first?

usually i write my routines to work with coordinate lists not entities
so it's up to the calling function to supply 'correct' arguments
something like:

Code: [Select]

(vk_IsPointInside
  pt
  (if (vl-position (cons 70 1) (entget ent))
    (cons (last PntLst) PntLst)
    PntLst
  )
)

Title: Re: Point is Inside polyline
Post by: Marc'Antonio Alessi on December 12, 2014, 05:48:34 AM

Ok, grazie. :)
Just a note: in case "C" (open but apparently closed ) you add a vertex equal to the last...

Title: Re: Point is Inside polyline
Post by: VovKa on December 12, 2014, 05:56:47 AM

Quote from: Marc'Antonio Alessi on December 12, 2014, 05:48:34 AM

Ok, grazie. :)

one more thing that i forgot to mention was that your

Code: [Select]

(setq PntLst (mapcar 'cdr (vl-remove-if-not (function (lambda (x) (eq 10 (car x)))) (entget ent))))and ymg's

Code: [Select]

(setq i (+ (vlax-curve-getEndParam en) 1))          
  (while (setq v (vlax-curve-getPointAtParam en (setq i (1- i))))
      (setq l (cons v l))
  )

return different results
so be careful

Title: Re: Point is Inside polyline
Post by: Marc'Antonio Alessi on December 12, 2014, 10:54:54 AM

Quote from: VovKa on December 12, 2014, 05:56:47 AM

Quote from: Marc'Antonio Alessi on December 12, 2014, 05:48:34 AM
Ok, grazie. :)
one more thing that i forgot to mention was that your
Code: [Select]
(setq PntLst (mapcar 'cdr (vl-remove-if-not (function (lambda (x) (eq 10 (car x)))) (entget ent))))and ymg's
Code: [Select]
(setq i (+ (vlax-curve-getEndParam en) 1)) (while (setq v (vlax-curve-getPointAtParam en (setq i (1- i)))) (setq l (cons v l)) )return different results
so be careful

Sorry for late, now I realized:
Case X > if the LW is closed (flag 70 = 1) > return also the last vertex (as in Poly "C")
Case Y > if the LW is closed (flag 70 = 1) > do NOT return the last vertex

Code: [Select]

(defun Ale_AddZeta (pt)
   (if (not (caddr pt))
      (list (car pt) (cadr pt) 0.0)
      pt
   )
)
(defun c:test2 (/ ent pt PntLst i v l)
  (setq ent (car (entsel "\nLWPolyline: ")))
  (setq PntLst (mapcar 'cdr (vl-remove-if-not (function (lambda (x) (eq 10 (car x)))) (entget ent))))
  (setq PntLst (mapcar 'Ale_AddZeta PntLst))
  (setq i (+ (vlax-curve-getEndParam ent) 1))          
  (while (setq v (vlax-curve-getPointAtParam ent (setq i (1- i))))
      (setq l (cons v l))
  )(princ " \n ")
  (princ (vl-princ-to-string l))                                 ; case X
  (princ " \n ")  (princ (vl-princ-to-string PntLst))  ; case Y
  (princ)
)

Just a note: in case "C" (open but apparently closed ) with:

Code: [Select]

(vk_IsPointInside
  pt
  (if (vl-position (cons 70 1) (entget ent))
    (cons (last PntLst) PntLst)
    PntLst
  )
)

you add a double vertex equal to the last...

Title: Re: Point is Inside polyline
Post by: ymg on December 12, 2014, 01:20:37 PM

Marc'Antonio Alessi,

As stated the input should be the ename or vla-object of a closed polyline.

The little snippet that list the vertices is an excerpt from one of Gile's routine.

There is logic in VovKa's way of passing a point list instead of an entity to the
routine.

I'm sure you can easily modify it.

ymg

Title: Re: Point is Inside polyline
Post by: Marc'Antonio Alessi on December 12, 2014, 03:14:15 PM

Quote from: ymg on December 12, 2014, 01:20:37 PM

Marc'Antonio Alessi,

As stated the input should be the ename or vla-object of a closed polyline.

The little snippet that list the vertices is an excerpt from one of Gile's routine.

There is logic in VovKa's way of passing a point list instead of an entity to the
routine.

I'm sure you can easily modify it.

ymg

There are two types of "closed polylines" see value 1 and 2 of this function:

Code: [Select]

; Return Values:
;   nil if LwPolyline is Open                         Lw0
;   1   if is Closed - (or logand 1 flag 70 is True)  Lw1
;   2   if is Open BUT startpoint is equal endpoint   Lw2
;
; Example:
;  (ALE_Pline_LwClosedP (vlax-ename->vla-object (car (entsel "Poly: "))) 0.001)
;
(defun ALE_Pline_LwClosedP (LwPObj FuzFac)
  (cond
    ( (eq :vlax-true (vla-get-closed LwPObj)) 1)   ; or (= 1 (logand 1 (cdr (assoc 70 (entget EntNam)))))
    ( (equal (vlax-curve-getStartPoint LwPObj) (vlax-curve-getEndPoint LwPObj) FuzFac) 2 )
  )
)

if you use my function test2 you get:

Code: [Select]

Lw0:
 ((0.0 0.0 0.0) (10.0 0.0 0.0) (0.0 10.0 0.0))
 ((0.0 0.0 0.0) (10.0 0.0 0.0) (0.0 10.0 0.0))

Lw1:
 ((13.0 0.0 0.0) (23.0 0.0 0.0) (13.0 10.0 0.0) (13.0 0.0 0.0))
 ((13.0 0.0 0.0) (23.0 0.0 0.0) (13.0 10.0 0.0))

Lw2:
 ((27.0 0.0 0.0) (37.0 0.0 0.0) (27.0 10.0 0.0) (27.0 0.0 0.0))
 ((27.0 0.0 0.0) (37.0 0.0 0.0) (27.0 10.0 0.0) (27.0 0.0 0.0))

So your function works well with both Lw1 and LW2 even if the polyline is open because it always gets 4 vertices.
What I wanted to say to VovKa is that with LW2 types not need to add the vertex even if the polyline is open.

Marco

Title: Re: Point is Inside polyline
Post by: Marc'Antonio Alessi on December 14, 2014, 04:43:08 AM

What do you think of the condition 3 (Lw3)? Is it realistic take this into account?

Code: [Select]

; ALE_Pline_LwClosedP - Version: 1.01
;
; Return Values:
;   nil if LwPolyline is Open                         
;   1   if is Closed - (or logand 1 flag 70 is True)  
;   2   if is Open   BUT startpoint is equal endpoint   
;   3   if is Closed AND startpoint is equal endpoint   
;
; Example:
;  (ALE_Pline_LwClosedP (vlax-ename->vla-object (car (entsel "Poly: "))) 0.001)
;
(defun ALE_Pline_LwClosedP (LwPObj FuzFac)
  (cond
    ( (eq :vlax-true (vla-get-closed LwPObj))
      (if
        (equal
          (vlax-curve-getEndPoint LwPObj)
          (vlax-curve-getPointAtParam LwPObj (1- (vlax-curve-getEndParam LwPObj)))
        )
        3 1
      )
    )
    ( (equal (vlax-curve-getStartPoint LwPObj) (vlax-curve-getEndPoint LwPObj) FuzFac) 2 )
  )
)

Title: Re: Point is Inside polyline
Post by: AARYAN on December 14, 2014, 05:39:33 AM

Working with coordinates rather than the entity is faster as Vovka's routine does.

Great routine Mr. Vovka.

Thanks for sharing.

Title: Re: Point is Inside polyline
Post by: VovKa on December 14, 2014, 05:54:17 AM

Quote from: AARYAN on December 14, 2014, 05:39:33 AM

Working with coordinates rather than the entity is faster as Vovka's routine does.

yep, but you must get coordinates somewhere in you code anyway
so eventually it will make both functions equal in speed

Title: Re: Point is Inside polyline
Post by: roy_043 on April 16, 2015, 09:58:22 AM

Thank you ymg for that interesting link: http://geomalgorithms.com/a03-_inclusion.html
Here is my 'port' of the Crossing Number (ray) algorithm:

Code - Auto/Visual Lisp: [Select]

; Based on C++ code by Dan Sunday.
; http://geomalgorithms.com/a03-_inclusion.html
(defun PointInsidePointList_P (pt ptLst)
  (=
    1
    (logand
      (apply
        '+
        (mapcar
          '(lambda (ptA ptB)
            (if
              (and
                (or
                  (and (<= (cadr ptA) (cadr pt)) (> (cadr ptB) (cadr pt))) ; Upward crossing.
                  (and (> (cadr ptA) (cadr pt)) (<= (cadr ptB) (cadr pt))) ; Downward crossing.
                )
                (<
                  (car pt)
                  (+
                    (car ptA)
                    (*
                      (- (cadr pt) (cadr ptA))
                      (/ (- (car ptB) (car ptA)) (- (cadr ptB) (cadr ptA))) ; DeltaX/DeltaY edge.
                    )
                  )
                )
              )
              1
              0
            )
          )
          ptLst
          (append (cdr ptLst) (list (car ptLst)))
        )
      )
      1
    )
  )
)

Title: Re: Point is Inside polyline
Post by: ronjonp on April 16, 2015, 11:27:23 AM

FWIW .. Here are some benchmarks (Using MP's benchmark code) for YMG, ROY & Vovka's code. I modified YMG's code to accept a point list like the other two.

Quote

3668 Points
Benchmarking .........Elapsed milliseconds / relative speed for 64 iteration(s):

(PTINPOLY_P P L).................1422 / 1.60 <fastest>
(POINTINSIDEPOINTLIST_P P L).....2031 / 1.12
(VK_ISPOINTINSIDE P L)...........2282 / 1.00 <slowest>

36639 Points
Benchmarking ........Elapsed milliseconds / relative speed for 32 iteration(s):

(PTINPOLY_P P L).................1500 / 1.65 <fastest>
(POINTINSIDEPOINTLIST_P P L).....2469 / 1.00 <slowest>
(vk_ispointinside p l) ...Hard error occurred *** internal stack limit reached (simulated)

Title: Re: Point is Inside polyline
Post by: Andrea on April 16, 2015, 11:50:04 AM

my contribution...
not the Quicker way or smallest code...
but it work when the polygon is far away from 0,0. :)

Code: [Select]

(defun Isinside	(pt ent / pt1 pt2 $_object_1 $_object_2 $_object_3 #gr #pti Inresult vlazone)
  (if (>
	(distance '(0 0 0) (cdr (assoc 10 (entget ent))))
	9000000.00
      )
    (setq ofstval 0.8)
    (setq ofstval 0.001)
  )

  (if (and pt ent)
    (progn
      (setq vlazone (vlax-ename->vla-object ent))
      (setq $_object_1 (vlax-ename->vla-object ent))
      (setq $_object_2 (car (vlax-invoke $_object_1 'Offset ofstval))
	    $_object_3 (car (vlax-invoke $_object_1 'Offset (- ofstval)))
      )
      (if (> (vla-get-area $_object_2) (vla-get-area $_object_3))
	(progn
	  (set '#gr $_object_2)
	  (set '#pti $_object_3)
	)
	(progn
	  (set '#gr $_object_3)
	  (set '#pti $_object_2)
	)
      )
      (setq pt1	(vlax-curve-getClosestPointTo #gr pt)
	    pt2	(vlax-curve-getClosestPointTo #pti pt)
      )

      (if (> (distance pt pt1) (distance pt pt2))
	(setq Inresult T)
	(setq Inresult nil)
      )
      (mapcar (function	(lambda	(x)
			  (progn
			    (vla-delete x)
			    (vlax-release-object x)
			  )
			)
	      )
	      (list $_object_2 $_object_3)
      )
      (if (not (vlax-object-released-p $_object_1))
	(vlax-release-object $_object_1)
      )
    )
  )
  Inresult
)

;;test
;;(Isinside (getpoint) (car (entsel)))

Title: Re: Point is Inside polyline
Post by: ymg on April 16, 2015, 05:16:17 PM

Andrea,

The "isleft" test normally should not be too sensitive to
how far from zero you are.

Although it is a cross-product, you are multiplying only
the difference between coordinates.

Rojomp,

It could be a little faster if we would modify the isleft
to get 6 parameters (xp yp x1 y1 x2 y2) since
we already do some of the car and cadr in the calling
routine.

Beware! I did not test any of the code below,
just did the change on the fly!

Code - Auto/Visual Lisp: [Select]

(defun isleft (xp yp x1 y1 x2 y2)
   (minusp (- (* (- y1 yp) (- x2 xp))
              (* (- x1 xp) (- y2 yp))
           )
   ) 
)
 

Code - Auto/Visual Lisp: [Select]

;;============================================================================;
;;                                                                            ;
;;      PtInPoly_p(): Winding number test for a point in a polygon            ;
;;                                                                            ;
;;      Input:    p = a point                                                 ;
;;                l = List of points forming the polyline                     ;
;;                                                                            ;
;;      Return:  t, if point is in polyline. (wn is not 0)                    ;
;;                                                                            ;
;; Original code in C++ by Dan Sunday                                         ;
;; See: http://geomalgorithms.com/a03-_inclusion.html                         ;
;;============================================================================;
 
(defun PtInPoly_p (p l / xp yp x1 y1 x2 y2 wn)
 
   ;; Returns t if point p is strictly to the left of v1->v2   by ymg         ;
   (defun isleft (xp yp x1 y1 x2 y2)
      (minusp (- (* (- y1 yp) (- x2 xp))
                 (* (- x1 xp) (- y2 yp))
              )
      ) 
   )
 
   (setq x1 (caar  l) y1 (cadar l)
         xp (car p)   yp (cadr p)
         wn 0                               
   )      
 
   ;; Loop through all edges of polygon.                                      ;
   (foreach p2 (cdr l)
      (setq x2 (car p2) y2 (cadr p2))
      (if (<= y1 yp)
         (if (> y2 yp)                          
            (if (isleft xp yp x1 y1 x2 y2) (setq wn (1+ wn)))
         )  
         (if (<= y2 yp)
            (if (isleft xp yp x2 y2 x1 y1) (setq wn (1- wn)))
         )
      )
      (setq x1 x2   y1 y2)
   )
   (not (zerop wn))
) 
 

ymg

Title: Re: Point is Inside polyline
Post by: ronjonp on April 17, 2015, 08:49:00 AM

Here's a quick test:

Quote

14739 Points

_$
Benchmarking ..........Elapsed milliseconds / relative speed for 128 iteration(s):

(PTINPOLY_P P L)......1954 / 1.11 <fastest>
(PTINPOLY_P2 P L).....2172 / 1.00 <slowest>
Benchmarking ..........Elapsed milliseconds / relative speed for 128 iteration(s):

(PTINPOLY_P P L)......1969 / 1.12 <fastest>
(PTINPOLY_P2 P L).....2203 / 1.00 <slowest>
Benchmarking ..........Elapsed milliseconds / relative speed for 128 iteration(s):

(PTINPOLY_P P L)......1968 / 1.12 <fastest>
(PTINPOLY_P2 P L).....2203 / 1.00 <slowest>

Title: Re: Point is Inside polyline
Post by: ymg on April 17, 2015, 12:18:18 PM

ronjomp,

Thanks! for the test.

There is a 15% difference,
but which one is the fastest
(6 arguments) or (3 arguments)?

ymg

Title: Re: Point is Inside polyline
Post by: ronjonp on April 17, 2015, 12:25:41 PM

Quote from: ymg on April 17, 2015, 12:18:18 PM

ronjomp,

Thanks! for the test.

There is a 15% difference,
but which one is the fastest
(6 arguments) or (3 arguments)?

ymg

Your code in the first post is faster.

Title: Re: Point is Inside polyline
Post by: ymg on April 17, 2015, 01:33:25 PM

ronjomp,

Looks to me as if passing an argument takes about the same time
as a setq.

So maybe we could keep the test inline with the code
like so:

Code - Auto/Visual Lisp: [Select]

;;============================================================================;
;;                                                                            ;
;;      PtInPoly_p(): Winding number test for a point in a polygon            ;
;;                                                                            ;
;;      Input:    p = a point                                                 ;
;;                l = List of points forming the polyline                     ;
;;                                                                            ;
;;      Return:  t, if point is in polyline. (wn is not 0)                    ;
;;                                                                            ;
;; Original code in C++ by Dan Sunday                                         ;
;; See: http://geomalgorithms.com/a03-_inclusion.html                         ;
;;============================================================================;
 
(defun PtInPoly_p3 (p l / xp yp x1 y1 x2 y2 wn)
 
   (setq xp (car  p)  yp (cadr  p)
         x1 (caar l)  y1 (cadar l)
         wn 0                               
   )      
 
   ;; Loop through all edges of polygon.                                      ;
   (foreach p2 (cdr l)
      (setq x2 (car p2) y2 (cadr p2))
      (if (<= y1 yp)
         (if (> y2 yp)                          
            (if (minusp (- (* (- y1 yp) (- x2 xp))
                           (* (- x1 xp) (- y2 yp))
                        )
                )
              (setq wn (1+ wn))
            )
         )  
         (if (<= y2 yp)
            (if (minusp (- (* (- y2 yp) (- x1 xp))
                           (* (- x2 xp) (- y1 yp))
                        )
                ) (setq wn (1- wn))
            )
         )
      )
      (setq x1 x2   y1 y2)
   )
   (not (zerop wn))
)
 

Result of a test on a small poly only 7 sides:

Quote

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

(PTINPOLY_P3 P L)..........1232 / 1.09 <fastest>
(VK_ISPOINTINSIDE P L).....1295 / 1.04
(PTINPOLY_P2 P L)..........1310 / 1.02
(PTINPOLY_P1 P L)..........1342 / 1.00 <slowest>
; 11 forms loaded from #<editor "C:/Lisp/ptinpoly_p test.LSP">
_$
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

(PTINPOLY_P3 P L)..........1232 / 1.08 <fastest>
(PTINPOLY_P2 P L)..........1295 / 1.02
(VK_ISPOINTINSIDE P L).....1295 / 1.02
(PTINPOLY_P1 P L)..........1326 / 1.00 <slowest>
; 11 forms loaded from #<editor "C:/Lisp/ptinpoly_p test.LSP">
_$
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

(PTINPOLY_P3 P L)..........1248 / 1.08 <fastest>
(PTINPOLY_P2 P L)..........1311 / 1.02
(VK_ISPOINTINSIDE P L).....1326 / 1.01
(PTINPOLY_P1 P L)..........1342 / 1.00 <slowest>
; 12 forms loaded from #<editor "C:/Lisp/ptinpoly_p test.LSP">
_$

Also notes that ptinpoly_p returns true if the points is on the poly.

Vovka's return false.

ymg

Title: Re: Point is Inside polyline
Post by: roy_043 on April 22, 2015, 03:48:26 AM

Thank you ronjonp for your benchmark tests.

I am a little surprised that my code proves to be clearly slower than ymg's code. To find the cause I have created two initial variations (see *_01 and *_02 below), both of which avoid the addition of what can be a long list of integers. I have compared my original code and the two variations against ymg's latest function: PtInPoly_p3.

On BricsCAD V14 the benchmark results are markedly different from ronjonp's test. In all tests my original code is the fastest. Even if the point list contains 1000+ random points. Which, for my application, is not a very realistic scenario.

This makes me wonder what is causing the bottle neck on AutoCAD. Is it the use of mapcar and is foreach perhaps much faster on AutoCAD?

Benchmark:

Code: [Select]

(setq lstC ((629.78 294.034 0.0) (1964.78 1162.32 0.0) (2507.46 907.264 0.0) (2936.18 147.51 0.0) (2219.84 -623.098 0.0) (1036.79 -557.976 0.0) (249.903 -699.074 0.0) (249.903 -281.209 0.0) (1015.08 -281.209 0.0) (917.402 -37.002 0.0) (92.5253 28.1198 0.0) (92.5253 266.9 0.0)))

(setq pt (570.085 -112.977 0.0))

(KGX_BenchMark '((GEO_Geom_PointInsidePointList_P pt lstC) (GEO_Geom_PointInsidePointList_P_01 pt lstC) (GEO_Geom_PointInsidePointList_P_02 pt lstC) (PtInPoly_p3 pt lstC)) 100000)

Benchmarking .......... elapsed milliseconds / relative timing <100000 iterations>

  (GEO_GEOM_POINTINSIDEPOINTLIST_P PT LSTC) ........ 1593 / 1.27 <fastest>
  (GEO_GEOM_POINTINSIDEPOINTLIST_P_01 PT LSTC) ..... 1703 / 1.18
  (GEO_GEOM_POINTINSIDEPOINTLIST_P_02 PT LSTC) ..... 1813 / 1.11
  (PTINPOLY_P3 PT LSTC) ............................ 2016 / 1.00 <slowest>

Code:

Code - Auto/Visual Lisp: [Select]

; Based on C++ code by Dan Sunday.
; http://geomalgorithms.com/a03-_inclusion.html
(defun GEO_Geom_PointInsidePointList_P (pt ptLst)
  (=
    1
    (logand
      (apply
        '+
        (mapcar
          '(lambda (ptA ptB)
            (if
              (and
                (or
                  (and (<= (cadr ptA) (cadr pt)) (> (cadr ptB) (cadr pt))) ; Upward crossing.
                  (and (> (cadr ptA) (cadr pt)) (<= (cadr ptB) (cadr pt))) ; Downward crossing.
                )
                (<
                  (car pt)
                  (+
                    (car ptA)
                    (*
                      (- (cadr pt) (cadr ptA))
                      (/ (- (car ptB) (car ptA)) (- (cadr ptB) (cadr ptA))) ; DeltaX/DeltaY edge.
                    )
                  )
                )
              )
              1
              0
            )
          )
          ptLst
          (append (cdr ptLst) (list (car ptLst)))
        )
      )
      1
    )
  )
)
 
(defun GEO_Geom_PointInsidePointList_P_01 (pt ptLst / ret)
  (setq cnt 0)
  (mapcar
    '(lambda (ptA ptB)
      (if
        (and
          (or
            (and (<= (cadr ptA) (cadr pt)) (> (cadr ptB) (cadr pt))) ; Upward crossing.
            (and (> (cadr ptA) (cadr pt)) (<= (cadr ptB) (cadr pt))) ; Downward crossing.
          )
          (<
            (car pt)
            (+
              (car ptA)
              (*
                (- (cadr pt) (cadr ptA))
                (/ (- (car ptB) (car ptA)) (- (cadr ptB) (cadr ptA))) ; DeltaX/DeltaY edge.
              )
            )
          )
        )
        (setq cnt (1+ cnt))
      )
    )
    ptLst
    (append (cdr ptLst) (list (car ptLst)))
  )
  (= 1 (logand cnt 1))
)
 
(defun GEO_Geom_PointInsidePointList_P_02 (pt ptLst / ret)
  (setq cnt 0)
  (setq xPt (car pt))
  (setq yPt (cadr pt))
  (mapcar
    '(lambda (ptA ptB)
      (if
        (and
          (or
            (and (<= (cadr ptA) yPt) (> (cadr ptB) yPt)) ; Upward crossing.
            (and (> (cadr ptA) yPt) (<= (cadr ptB) yPt)) ; Downward crossing.
          )
          (<
            xPt
            (+
              (car ptA)
              (*
                (- yPt (cadr ptA))
                (/ (- (car ptB) (car ptA)) (- (cadr ptB) (cadr ptA))) ; DeltaX/DeltaY edge.
              )
            )
          )
        )
        (setq cnt (1+ cnt))
      )
    )
    ptLst
    (append (cdr ptLst) (list (car ptLst)))
  )
  (= 1 (logand cnt 1))
)

Title: Re: Point is Inside polyline
Post by: ronjonp on April 22, 2015, 09:17:47 AM

This is what I get for a 940 point list:

Code: [Select]

Benchmarking ............Elapsed milliseconds / relative speed for 512 iteration(s):
    (PTINPOLY_P1 P L)............................2875 / 1.85 <fastest>
    (PTINPOLY_P2 P L)............................3859 / 1.38
    (PTINPOLY_P3 P L)............................4125 / 1.29
    (GEO_GEOM_POINTINSIDEPOINTLIST_P_02 ...).....4219 / 1.26
    (GEO_GEOM_POINTINSIDEPOINTLIST_P_01 ...).....5281 / 1.01
    (GEO_GEOM_POINTINSIDEPOINTLIST_P P L)........5328 / 1.00 <slowest>

And using your 'lstc' and 'pt':

Code: [Select]

Elapsed milliseconds / relative speed for 32768 iteration(s):
    (PTINPOLY_P3 P L)............................1125 / 1.51 <fastest>
    (PTINPOLY_P2 P L)............................1188 / 1.43
    (PTINPOLY_P1 P L)............................1297 / 1.31
    (GEO_GEOM_POINTINSIDEPOINTLIST_P_02 ...).....1468 / 1.16
    (GEO_GEOM_POINTINSIDEPOINTLIST_P_01 ...).....1656 / 1.03
    (GEO_GEOM_POINTINSIDEPOINTLIST_P P L)........1703 / 1.00 <slowest>

And here's compiled with the 940 point list and replacing your '(lambda with (function (lambda.

Code: [Select]

Elapsed milliseconds / relative speed for 2048 iteration(s):
    (PTINPOLY_P1 P L)............................1125 / 2.75 <fastest>
    (PTINPOLY_P2 P L)............................1187 / 2.61
    (PTINPOLY_P3 P L)............................1187 / 2.61
    (GEO_GEOM_POINTINSIDEPOINTLIST_P_02 ...).....2375 / 1.30
    (GEO_GEOM_POINTINSIDEPOINTLIST_P_01 ...).....3078 / 1.01
    (GEO_GEOM_POINTINSIDEPOINTLIST_P P L)........3094 / 1.00 <slowest>

Title: Re: Point is Inside polyline
Post by: ymg on April 24, 2015, 06:39:49 AM

Roy,

I am like you not understanding why ptinpoly_p1 would be faster.

There is obviously one "if" too many in there and yet it does run faster
when I test it with Ronjomp poly.

ptinpoly_p1 was a litteral translation of Dan Sunday's code

ymg

Title: Re: Point is Inside polyline
Post by: roy_043 on April 25, 2015, 05:47:57 AM

Benchmarking all the functions in this topic on BricsCAD V14.2.17 and on a sloooow computer...

Conclusion:
Ymg's function PtInPoly_p1 is the fastest in most situations.

Short point list:

Code: [Select]

(setq lstC '((629.78 294.034 0.0) (1964.78 1162.32 0.0) (2507.46 907.264 0.0) (2936.18 147.51 0.0) (2219.84 -623.098 0.0) (1036.79 -557.976 0.0) (249.903 -699.074 0.0) (249.903 -281.209 0.0) (1015.08 -281.209 0.0) (917.402 -37.002 0.0) (92.5253 28.1198 0.0) (92.5253 266.9 0.0)))
(setq pt '(570.085 -112.977 0.0))

Benchmarking .......... elapsed milliseconds / relative timing <32768 iterations>

  (GEO_GEOM_POINTINSIDEPOINTLIST_P_02 PT LSTC) ..... 500 / 1.56 <fastest>
  (GEO_GEOM_POINTINSIDEPOINTLIST_P PT LSTC) ........ 516 / 1.51
  (PTINPOLY_P1 PT LSTC) ............................ 531 / 1.47
  (GEO_GEOM_POINTINSIDEPOINTLIST_P_01 PT LSTC) ..... 531 / 1.47
  (PTINPOLY_P3 PT LSTC) ............................ 672 / 1.16
  (PTINPOLY_P2 PT LSTC) ............................ 735 / 1.06
  (VK_ISPOINTINSIDE PT LSTC) ....................... 781 / 1.00 <slowest>

Long point list (using P en L from ronjonp's pts.txt).

Code: [Select]

Benchmarking .......... elapsed milliseconds / relative timing <2048 iterations>

  (PTINPOLY_P1 P L) ............................. 1469 / 39.81 <fastest>
  (GEO_GEOM_POINTINSIDEPOINTLIST_P_02 P L) ...... 2125 / 27.52
  (GEO_GEOM_POINTINSIDEPOINTLIST_P P L) ......... 2375 / 24.63
  (GEO_GEOM_POINTINSIDEPOINTLIST_P_01 P L) ...... 2422 / 24.15
  (PTINPOLY_P3 P L) ............................. 2750 / 21.27
  (PTINPOLY_P2 P L) ............................. 2890 / 20.24
  (VK_ISPOINTINSIDE P L) ....................... 58485 / 1.00 <slowest>

Repeat of the last test leaving out VovKa's code:

Code: [Select]

Benchmarking .......... elapsed milliseconds / relative timing <2048 iterations>

  (PTINPOLY_P1 P L) ............................ 1297 / 1.93 <fastest>
  (GEO_GEOM_POINTINSIDEPOINTLIST_P P L) ........ 1953 / 1.28
  (GEO_GEOM_POINTINSIDEPOINTLIST_P_01 P L) ..... 2078 / 1.20
  (GEO_GEOM_POINTINSIDEPOINTLIST_P_02 P L) ..... 2188 / 1.14
  (PTINPOLY_P3 P L) ............................ 2453 / 1.02
  (PTINPOLY_P2 P L) ............................ 2500 / 1.00 <slowest>

Title: Re: Point is Inside polyline
Post by: GP on April 25, 2015, 07:43:56 AM

My $0.02 :-)

Code: [Select]

(defun inside_p (:p :Lst / remote_p cross)
    (setq remote_p (mapcar '+ '(1.0 1.0 0) (getvar "extmax")))
    (setq cross 0)
    (mapcar
        '(lambda (a b)
             (if (inters :p remote_p a b) (setq cross (1+ cross)))
         )
        :Lst (cdr :Lst)
    )
    (= 1 (rem cross 2))
)

Title: Re: Point is Inside polyline
Post by: ymg on April 25, 2015, 08:21:11 AM

Gian Paolo,

I don't think this will work with self intersecting polylines.

Also what happen If point P is directly on a vertex of the polyline?

This is a well known method of counting the crossings.

ymg

Title: Re: Point is Inside polyline
Post by: Lee Mac on April 25, 2015, 10:53:59 AM

What about polylines with arc segments?

This thread may be of interest: http://www.theswamp.org/index.php?topic=47969.0

Title: Re: Point is Inside polyline
Post by: ymg on April 25, 2015, 11:53:21 AM

Lee,

For polylines with bulge, it gets messy.

You can approximate the curve part by adding straight segments.

Code: [Select]

(defun approxpoly (en / px fe)
      (setq px (* 0.75 (acet-geom-pixel-unit))
            fe (acet-list-remove-adjacent-dups
		  (acet-geom-object-point-list en (/ px 2.0)))
      )	    
   )

But this is bound to create problems when you are on the
boundary.

ymg

Title: Re: Point is Inside polyline
Post by: GP on April 25, 2015, 01:58:20 PM

Quote from: ymg on April 25, 2015, 08:21:11 AM

I don't think this will work with self intersecting polylines.

Also what happen If point P is directly on a vertex of the polyline?

Quote from: Lee Mac on April 25, 2015, 10:53:59 AM

What about polylines with arc segments?

True... but I think also the other codes posted :-)

This code should works with self intersecting polylines and also If point P is directly on a vertex/segment of the polyline:

Code - Auto/Visual Lisp: [Select]

(defun inside_p (:p :Lst / far_p cross on)
    (setq far_p (mapcar '+ '(1.0 1.0 0.0) (getvar "extmax")))
    (setq cross 0)
    (if (not (member :p :Lst))
        (mapcar
            '(lambda (a b)
                 (if (inters :p far_p a b) (setq cross (1+ cross)))
                 (if (equal (+ (distance :p a) (distance :p b)) (distance a b) 1e-8) (setq on t))
             )
            :Lst (cdr :Lst)
        )
        (setq on t)
    )
    (or (not (zerop (rem cross 2))) on)
)

Title: Re: Point is Inside polyline
Post by: ymg on April 25, 2015, 05:03:35 PM

Gian Paolo,

The winding number method works with self-intersecting polylines
and also if your point is on a vertex.

It does not work with bulges though!

ymg

Quote

Benchmarking .............Elapsed milliseconds / relative speed for 1024 iteration(s):

(PTINPOLY_P1 P L)..........1279 / 1.52 <fastest>
(INSIDE_P P L).............1934 / 1.01
(VK_ISPOINTINSIDE P L).....1950 / 1.00 <slowest>

Images below from: http://geomalgorithms.com/a03-_inclusion.html

Title: Re: Point is Inside polyline
Post by: GP on April 25, 2015, 07:15:57 PM

Thank you ymg, I realized now, but... seems it does not work always.

Title: Re: Point is Inside polyline
Post by: roy_043 on April 26, 2015, 10:00:43 AM

@ GP:

Quote from: http://geomalgorithms.com/a03-_inclusion.html

Further, one must decide whether a point on the polygon's boundary is inside or outside. A standard convention is to say that a point on a left or bottom edge is inside, and a point on a right or top edge is outside. This way, if two distinct polygons share a common boundary segment, then a point on that segment will be in one polygon or the other, but not both at the same time. This avoids a number of problems that might occur, especially in computer graphics displays.

Title: Re: Point is Inside polyline
Post by: ymg on April 26, 2015, 10:02:54 AM

Gian Paolo,

Yes there seems to be some inconsistencies when we are directly
on the line.

Maybe due to some rounding error in the onleft routine.

Thanks,

ymg

Code: [Select]

(defun PtInPoly_p1 (p l / i l p1 p2 v wn y)

   ;; Returns t if point p is strictly to the left of v1->v2   by ymg         ;
   (defun isleft (p v1 v2 / xp yp)
       (setq  xp (car  p)  yp (cadr  p))
       (minusp (- (* (- (cadr v1) yp) (- (car v2) xp)) (* (- (car v1) xp) (- (cadr v2) yp)))) 
   )
  
   
  
   
   ;; Initialize the loop.                                                    ;
   (setq p1 (car  l)
	  y (cadr p)
         wn 0                               
   )
    
   ;; Loop through all edges of polygon.                                      ;
   (foreach p2 (cdr l) 
      (if (<= (cadr p1) y)
	 (if (> (cadr p2) y)                          
	    (if (isleft p p1 p2) (setq wn (1+ wn)))
	 )  
         (if (<= (cadr p2) y)
	    (if (not (isleft p p1 p2)) (setq wn (1- wn)))
	 )
      )
      (setq p1 p2)
   )
   (not (zerop wn));; Returns t if wn not equal to zero.                      ;
)


 ;   // loop through all edges of the polygon                            
 ;   for (int i=0; i<n; i++) {   // edge from V[i] to  V[i+1]            
 ;       if (V[i].y <= P.y) {          // start y <= P.y                 
 ;          if (V[i+1].y  > P.y)      // an upward crossing              
 ;               if (isLeft( V[i], V[i+1], P) > 0)  // P left of  edge   
 ;                    ++wn;            // have  a valid up intersect     
 ;       }                                                               
 ;       else {                        // start y > P.y (no test needed) 
 ;           if (V[i+1].y  <= P.y)     // a downward crossing            
 ;                if (isLeft( V[i], V[i+1], P) < 0)  // P right of  edge 
 ;                    --wn;            // have  a valid down intersect   
 ;       }                                                               
 ;   }                                                                   
 ;   return wn;                                                          
 ;}                                                                      


(defun listpol (en / i p l)  
  (setq	i (if (vlax-curve-IsClosed en)
  	     (vlax-curve-getEndParam en)
	     (+ (vlax-curve-getEndParam en) 1)
	  )
  )	      
  (while (setq p (vlax-curve-getPointAtParam en (setq i (1- i))))
      (setq l (cons (trans p 0 1 ) l))
  )
)


(defun c:test (/ en l p)
   (princ "\nSelect Polyline Under Test: ")
   (setq en (car (entsel))
	  l (listpol en)
	  l (cons (last l) l)
   )
   (setvar 'PDSIZE -1.5)
   (while (setq p (getpoint "\nPick a Point: "))
      (if (ptinpoly_p1 p l)
         (entmakex (list (cons 0 "POINT") (cons 10 p) (cons 62 1)))
	 (entmakex (list (cons 0 "POINT") (cons 10 p) (cons 62 7)))
      )
   )
   (princ)
)

Title: Re: Point is Inside polyline
Post by: ymg on April 26, 2015, 03:14:46 PM

Roy,

Here I've modified on left by removing the minusp test,
and modified ptinpoly_p to test exactly like Sunday's
routine.

Works more or less OK as by his description.

I do run into some roundoff error on the left side
of the test poly.

Code: [Select]

(defun PtInPoly_p5 (p l / i l p1 p2 v wn y)

   ;; Returns t if point p is strictly to the left of v1->v2   by ymg         ;
   (defun isleft (p v1 v2 / xp yp)
       (setq  xp (car  p)  yp (cadr  p))
       (- (* (- (cadr v1) yp) (- (car v2) xp)) (* (- (car v1) xp) (- (cadr v2) yp))) 
   )
  
   
  
   
   ;; Initialize the loop.                                                    ;
   (setq p1 (car  l)
	  y (cadr p)
         wn 0                               
   )
    
   ;; Loop through all edges of polygon.                                      ;
   (foreach p2 (cdr l) 
      (if (<= (cadr p1) y)
	 (if (> (cadr p2) y)                          
	    (if (> (isleft p p1 p2) 0) (setq wn (1+ wn)))
	 )  
         (if (<= (cadr p2) y)
	    (if (< (isleft p p1 p2) 0) (setq wn (1- wn)))
	 )
      )
      (setq p1 p2)
   )
   (not (zerop wn));; Returns t if wn not equal to zero.                      ;
)

Title: Re: Point is Inside polyline
Post by: roy_043 on April 27, 2015, 09:23:57 AM

@ ymg:
I was trying to replicate your experiment and while doing so came across some strange results:

Code: [Select]

(setq ptLst '((0.0 0.0 0.0) (104.0 0.0 0.0) (104.0 72.0 0.0) (0.0 72.0 0.0)))

(GEO_GEOM_POINTINSIDEPOINTLIST_P '(1.0 1.0 0.0) ptLst) => T
(PtInPoly_p1                     '(1.0 1.0 0.0) ptLst) => T
(PtInPoly_p2                     '(1.0 1.0 0.0) ptLst) => T
(PtInPoly_p3                     '(1.0 1.0 0.0) ptLst) => T
(PtInPoly_p5                     '(1.0 1.0 0.0) ptLst) => nil

(GEO_GEOM_POINTINSIDEPOINTLIST_P '(-1.0 0.0 0.0) ptLst) => nil
(PtInPoly_p1                     '(-1.0 0.0 0.0) ptLst) => T
(PtInPoly_p2                     '(-1.0 0.0 0.0) ptLst) => T
(PtInPoly_p3                     '(-1.0 0.0 0.0) ptLst) => T
(PtInPoly_p5                     '(-1.0 0.0 0.0) ptLst) => nil

Title: Re: Point is Inside polyline
Post by: roy_043 on April 27, 2015, 09:40:30 AM

It is interesting to note that where http://geomalgorithms.com/a03-_inclusion.html mentions that, by convention, points on the left and bottom edges are considered inside the polyline, ymg's code favors the right and bottom edges instead and the code I have 'ported' favors the left and top edges.

Title: Re: Point is Inside polyline
Post by: ymg on April 27, 2015, 11:13:27 AM

Roy,

This is a finicky! beast.

It is somewhat unsastisfying for example that a point of the polyline
would be considered outside.

ymg

Title: Re: Point is Inside polyline
Post by: roy_043 on April 28, 2015, 05:39:36 AM

@ ymg:
I now see that your code requires a different point list than mine. For your code the last point in the list must be equal to the first point. The strange results reported in post #37 are all due to this oversight. My apologies for that.

The same test with correct point lists:

Code: [Select]

(setq ptLst    '((0.0 0.0 0.0) (104.0 0.0 0.0) (104.0 72.0 0.0) (0.0 72.0 0.0)))
(setq ptLstAlt '((0.0 0.0 0.0) (104.0 0.0 0.0) (104.0 72.0 0.0) (0.0 72.0 0.0) (0.0 0.0 0.0)))

(GEO_GEOM_POINTINSIDEPOINTLIST_P '(1.0 1.0 0.0) ptLst)    => T
(PtInPoly_p1                     '(1.0 1.0 0.0) ptLstAlt) => T
(PtInPoly_p2                     '(1.0 1.0 0.0) ptLstAlt) => T
(PtInPoly_p3                     '(1.0 1.0 0.0) ptLstAlt) => T
(PtInPoly_p5                     '(1.0 1.0 0.0) ptLstAlt) => T
(vk_IsPointInside                '(1.0 1.0 0.0) ptLstAlt) => T

(GEO_GEOM_POINTINSIDEPOINTLIST_P '(-1.0 0.0 0.0) ptLst)    => nil
(PtInPoly_p1                     '(-1.0 0.0 0.0) ptLstAlt) => nil
(PtInPoly_p2                     '(-1.0 0.0 0.0) ptLstAlt) => nil
(PtInPoly_p3                     '(-1.0 0.0 0.0) ptLstAlt) => nil
(PtInPoly_p5                     '(-1.0 0.0 0.0) ptLstAlt) => nil
(vk_IsPointInside                '(-1.0 0.0 0.0) ptLstAlt) => nil

Title: Re: Point is Inside polyline
Post by: ymg on April 28, 2015, 08:44:32 AM

Roy,

No apologies necessary,

I attach a lot of value to your Input.

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on April 29, 2015, 09:50:59 AM

Here I've modified approxpoly to work with a tolerance
instead of the zoom level of your screen.

If we use it to get the point list of a polyline with bulges,
ptinpoly_p returns valid results to within the tolerance
given above.

I attached a test program and a drawings with the
polylines I used for testing.

Would appreciate to know if approxpoly can be ported
to briscad.

ymg

Code - Auto/Visual Lisp: [Select]

;; Routine to Test if a Point is inside a polylines                           ;
;; Will work with bulges and Self-Crossing and Overlapping Poly                ;
;;                                                                            ;
 
(defun c:test (/ *AcadDoc* *error* en l p varl listpol approxpoly ptinpoly_p)
   (vl-load-com)
    ;;; Error Handler by ElpanovEvgenyi                                       ;
    (defun *error* (msg)
        (mapcar 'eval varl)
        (if (and msg (not (wcmatch (strcase msg) "*BREAK*,*CANCEL*,*EXIT*")))
           (princ (strcat "\nError: " msg))
        )
        (and *AcadDoc* (vla-endundomark *AcadDoc*))
        (princ)
    )
     
    (setq varl '("CLAYER" "OSMODE" "CMDECHO" "PDMODE" "PDSIZE")
          varl (mapcar (function (lambda (a) (list 'setvar a (getvar a)))) varl)
    )     
     
   (or *AcadDoc* (setq *AcadDoc* (vla-get-activedocument (vlax-get-acad-object))))
 
   ;;                                                                         ;
   ;; listpol     by ymg    (Simplified a Routine by Gile Chanteau)           ;
   ;;                                                                         ;
   ;; Parameter:  en,  Entity Name or Object Name of Any Type of Polyline     ;
   ;;                                                                         ;
   ;; Returns:    List of Points in Current UCS                               ;
   ;;                                                                         ;
   ;; Notes:      On Closed Polyline the Last Vertex is Same as First)        ;
   ;;                                                                         ;
 
   (defun listpol (en / i l)
      (repeat (setq i (fix (1+ (vlax-curve-getEndParam en))))
         (setq l (cons (trans (vlax-curve-getPointAtParam en (setq i (1- i))) 0 1) l))
      )
   )
 
   ;;                                                                         ;
   ;; approxpoly        by ymg       (Derived from Fast Select)               ;
   ;;                                                                         ;
   ;; Parameters: en   Entity Name of a Polyline (Any types)                  ;
   ;;             tol  Tolerance Allowed for Lines Segments.                  ;
   ;;                                                                         ;
   ;; Returns:   A List of Points Replacing Bulges With Straight Segments.    ;
   ;;                                                                         ;
 
   (defun approxpoly (en tol)
      (acet-list-remove-adjacent-dups
           (acet-geom-object-point-list en tol)
      )     
   )
 
   ;;=========================================================================;
   ;;                                                                         ;
   ;;      PtInPoly_p(): Winding number test for a point in a polygon         ;
   ;;                                                                         ;
   ;;      Input:    p = a point                                              ;
   ;;               en = ename or vla-object of a closed polyline.            ;
   ;;                                                                         ;
   ;;      Return:  t, if point is in polyline. (wn is not 0)                 ;
   ;;                                                                         ;
   ;; Original code in C++ by Dan Sunday, Translated by ymg                   ;
   ;; See: http://geomalgorithms.com/a03-_inclusion.html                      ;
   ;;=========================================================================;
 
   (defun ptinpoly_p (p l / i p1 p2 v wn y isleft)
 
      ;; Returns t if point p is strictly to the left of v1->v2   by ymg      ;
      (defun isleft (p v1 v2 / xp yp)
          (setq  xp (car  p)  yp (cadr  p))
          (- (* (- (cadr v1) yp) (- (car v2) xp)) (* (- (car v1) xp) (- (cadr v2) yp))) 
      )
   
      ;; Initialize the loop.                                                 ;
      (setq p1 (car  l)
             y (cadr p)
            wn 0                               
      )
    
      ;; Loop through all edges of polygon.                                   ;
      (foreach p2 (cdr l) 
         (if (<= (cadr p1) y)
            (if (> (cadr p2) y)                          
               (if (> (isleft p p1 p2) 0) (setq wn (1+ wn)))
            )
            (if (<= (cadr p2) y)
               (if (< (isleft p p1 p2) 0) (setq wn (1- wn)))
            )   
         )
         (setq p1 p2)
      )
      (not (zerop wn)) ;; Returns t if wn not equal to zero.                  ;
   )
 
  
   (princ "\nSelect Polyline Under Test: ")
   (setq en (car (entsel))
         ;l (listpol en)           ;   Use this if poly has no bulges         ;
          l (approxpoly en 0.001)  ;   Use this if poly has bulges.           ;
   )
   
   (setvar 'PDMODE 34) (setvar 'PDSIZE -3.5)
   (while (setq p (getpoint "\nPick a Point: "))
      (if (ptinpoly_p p l)
         (entmakex (list (cons 0 "POINT") (cons 10 p) (cons 62 1)))
         (entmakex (list (cons 0 "POINT") (cons 10 p) (cons 62 7)))
      )
   )
   (*error* nil)
)  
 

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ronjonp on April 29, 2015, 10:30:33 AM

THIS (http://www.theswamp.org/index.php?topic=10451.msg426390#msg426390) could be used to trace the polyline rather than relying on ET functions.
Here is a quick test with your code above.

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on April 29, 2015, 10:39:11 AM

Ronjomp,

Looks good!! to me.

I'll do some test to see what happen when
there is no or little bulges.

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on April 29, 2015, 11:21:43 AM

Ronjomp,

Looks better!!, did a fast benchmark on that entity.

Quote

benchmark '((approxpoly en 0.001) (tracepline en 0.11765)))
Benchmarking .....Elapsed milliseconds / relative speed for 4 iteration(s):

(TRACEPLINE EN 0.11765).....1466 / 1.10 <fastest>
(APPROXPOLY EN 0.001).......1606 / 1.00 <slowest>

Only difficulty is the angular parameter.

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on April 30, 2015, 05:47:31 AM

Here's another way to skin the cat.

A Winding Number and Point-in-Polygon Algoritm
by David G. Alciatore and Rick Miranda
http://www.engr.colostate.edu/~dga/dga/papers/point_in_polygon.pdf

This is again the winding number algorithm.
But instead of doing the onleft cross product
test, we translate the point of the polyline
to point p as origin of the coordinate system.
We then proceed to count how many times
the y coordinates cross the positive x axis.

One interesting note about the winding number
algorithm is that the sign of the wn also gives
you the direction the polyline is drawn. Negative
wn is ccw and vice-versa.

Code - Auto/Visual Lisp: [Select]

;;                                                                            ;
;; inside_p     by   ymg                                                      ;
;;                                                                            ;
;;           A Winding umber and Point-in-Polygon Algoritm                    ;
;;              by  David G. Alciatore and Rick Miranda                       ;
;;     http://www.engr.colostate.edu/~dga/dga/papers/point_in_polygon.pdf     ;
;;                                                                            ;
;; Here instead of onleft cross product test, we translate the polyline       ;
;; to the point.  We then count the crossing of the y coordinates above       ;
;; zero.                                                                      ;
;;                                                                            ;
;;       (Under Test)                                                         ;
;;                                                                            ;
 
(defun inside_p (p l)
   (setq w 0
          xp (car p)          yp (cadr p)
          x1 (- (caar l) xp)  y1 (- (cadar l) yp)
   )
   (foreach a (cdr l)
      (setq x2 (- (car  a) xp)  y2 (- (cadr a) yp))
      (cond
         ((< (* y1 y2) 0)  (if (> (+ x1 (* y1 (/ (- x2 x1) (- y1 y2)))) 0)
                                 (if (minusp y1) (setq w (1+ w)) (setq w (1- w)))
                           ))
         ((and (zerop  y1) (>  x1 0)) (if (>  y2   0) (setq w (+ w 0.5)) (setq w (- w 0.5))))
         ((and (zerop  y2) (>  x2 0)) (if (minusp y1) (setq w (+ w 0.5)) (setq w (- w 0.5))))
      )
      (setq x1 x2  y1 y2)  
   )
   (not (zerop w)) 
)
 

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ronjonp on April 30, 2015, 09:43:26 AM

Looks like inside_p does not work as well.

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on April 30, 2015, 10:46:31 AM

Ronjomp,

I'll check it, but the concept is sound.

By the way I like your illustration and poly a lot!!!

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ronjonp on April 30, 2015, 10:48:26 AM

Quote from: ymg on April 30, 2015, 10:46:31 AM

...

By the way I like your illustration and poly a lot!!!

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on May 02, 2015, 04:39:58 PM

ronjomp,

Don't know what happen with your last test, but I did re-test isinside_p and my results are OK.

Maybe you were missing the last repeating point in your poly.

Don't know if you had time to read Alciatore's paper but in it
the Update Criterion for w the winding number are as follow:

Code - Auto/Visual Lisp: [Select]

;;                                                                            ;
;; inside_p     by   ymg                                                      ;
;;                                                                            ;
;;           A Winding umber and Point-in-Polygon Algoritm                    ;
;;              by  David G. Alciatore and Rick Miranda                       ;
;;     http://www.engr.colostate.edu/~dga/dga/papers/point_in_polygon.pdf     ;
;;                                                                            ;
;; Here instead of onleft cross product test, we translate the polyline       ;
;; to the point.  We then count the crossing of the y coordinates above       ;
;; zero.                                                                      ;
;;                                                                            ;
;;                                                                            ;
 
(defun inside_p (p l / w x1 x2 xp y1 y2 yp)
   (setq w 0
         xp (car p)          yp (cadr p)
         x1 (- (caar l) xp)  y1 (- (cadar l) yp)
   )
   (foreach a (cdr l)
      (setq x2 (- (car  a) xp)  y2 (- (cadr a) yp))
      (cond
         ((< (* y1 y2) 0)  (if (> (+ x1 (* y1 (/ (- x2 x1) (- y1 y2)))) 0)
                                 (if (minusp y1) (setq w (1+ w)) (setq w (1- w)))
                           ))
         ((and (zerop  y1) (>  x1 0)) (if (>  y2   0) (setq w (+ w 0.5)) (setq w (- w 0.5))))
         ((and (zerop  y2) (>  x2 0)) (if (minusp y1) (setq w (+ w 0.5)) (setq w (- w 0.5))))
      )
      (setq x1 x2  y1 y2)  
   )
   (not (zerop w)) 
)
 

Now the funny part is that If I remove the test when we are
smack on the poly ((and (zerop y1) & ((and (zerop y2),
I still get very consistent results.

It is somewhat logical as he states in his paper that the
winding number is undefined when you are on the polyline.

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ronjonp on May 02, 2015, 11:48:20 PM

I just used the same points for each test. Nothing fancy :)

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on May 03, 2015, 10:14:55 AM

ronjonp,

Would you mind posting your testing program and data ?

What are your thoughts on removing the two test ?

Code: [Select]

((and (zerop  y1) (>  x1 0)) (if (>  y2   0) (setq w (+ w 0.5)) (setq w (- w 0.5))))
((and (zerop  y2) (>  x2 0)) (if (minusp y1) (setq w (+ w 0.5)) (setq w (- w 0.5))))

Since we do not really care about the winding number, what we want is true or false
for inside.

If we remove them, we have a 10 % speed advantage over ptinpoly_p1

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ronjonp on May 06, 2015, 10:05:53 AM

Ymg.

Here's what I used to test along with the attached drawing.

Code - Auto/Visual Lisp: [Select]

(defun c:test (/ e en l l2 ss w x x1 x2 xp y1 y2 yp)
  (vl-load-com)
  ;;                                                                            ;
  ;; inside_p     by   ymg                                                      ;
  ;;                                                                            ;
  ;;           A Winding umber and Point-in-Polygon Algoritm                    ;
  ;;              by  David G. Alciatore and Rick Miranda                       ;
  ;;     http://www.engr.colostate.edu/~dga/dga/papers/point_in_polygon.pdf     ;
  ;;                                                                            ;
  ;; Here instead of onleft cross product test, we translate the polyline       ;
  ;; to the point.  We then count the crossing of the y coordinates above       ;
  ;; zero.                                                                      ;
  ;;                                                                            ;
  ;;       (Under Test)                                                         ;
  ;;                                                                            ;
  (defun inside_p (p l)
    (setq w  0
     xp (car p)
     yp (cadr p)
     x1 (- (caar l) xp)
     y1 (- (cadar l) yp)
    )
    (foreach a (cdr l)
      (setq x2 (- (car a) xp)
       y2 (- (cadr a) yp)
      )
      (cond ((< (* y1 y2) 0)
        (if (> (+ x1 (* y1 (/ (- x2 x1) (- y1 y2)))) 0)
          (if (minusp y1)
       (setq w (1+ w))
       (setq w (1- w))
          )
        )
       )
       ((and (zerop y1) (> x1 0))
        (if (> y2 0)
          (setq w (+ w 0.5))
          (setq w (- w 0.5))
        )
       )
       ((and (zerop y2) (> x2 0))
        (if (minusp y1)
          (setq w (+ w 0.5))
          (setq w (- w 0.5))
        )
       )
      )
      (setq x1 x2
       y1 y2
      )
    )
    (not (zerop w))
  )
  ;;=========================================================================;
  ;;                                                                         ;
  ;;      PtInPoly_p(): Winding number test for a point in a polygon         ;
  ;;                                                                         ;
  ;;      Input:    p = a point                                              ;
  ;;               en = ename or vla-object of a closed polyline.            ;
  ;;                                                                         ;
  ;;      Return:  t, if point is in polyline. (wn is not 0)                 ;
  ;;                                                                         ;
  ;; Original code in C++ by Dan Sunday, Translated by ymg                   ;
  ;; See: http://geomalgorithms.com/a03-_inclusion.html                      ;
  ;;=========================================================================;
  (defun ptinpoly_p (p l / i p1 p2 v wn y isleft)
    ;; Returns t if point p is strictly to the left of v1->v2   by ymg      ;
    (defun isleft (p v1 v2 / xp yp)
      (setq xp (car p)
       yp (cadr p)
      )
      (- (* (- (cadr v1) yp) (- (car v2) xp)) (* (- (car v1) xp) (- (cadr v2) yp)))
    )
    ;; Initialize the loop.                                                 ;
    (setq p1 (car l)
     y  (cadr p)
     wn 0
    )
    ;; Loop through all edges of polygon.                                   ;
    (foreach p2   (cdr l)
      (if (<= (cadr p1) y)
   (if (> (cadr p2) y)
     (if (> (isleft p p1 p2) 0)
       (setq wn (1+ wn))
     )
   )
   (if (<= (cadr p2) y)
     (if (< (isleft p p1 p2) 0)
       (setq wn (1- wn))
     )
   )
      )
      (setq p1 p2)
    )
    (not (zerop wn))
    ;; Returns t if wn not equal to zero.                  ;
  )
  (princ "\nSelect Points: ")
  (if (setq ss (ssget '((0 . "point"))))
    (progn (setq l (mapcar '(lambda (e) (cdr (assoc 10 (entget e))))
            (vl-remove-if 'listp (mapcar 'cadr (ssnamex ss)))
         )
      )
      (setq l2 (mapcar '(lambda (p) (list (+ 100 (car p)) (cadr p) (caddr p))) l))
      (command "ERASE" ss)
      (foreach p l
        (if (ptinpoly_p p l)
          (entmakex (list '(0 . "POINT") (cons 10 p) '(62 . 1)))
          (entmakex (list '(0 . "POINT") (cons 10 p) '(62 . 7)))
        )
      )
      (foreach p l2
        (if (inside_p p l2)
          (entmakex (list '(0 . "POINT") (cons 10 p) '(62 . 1)))
          (entmakex (list '(0 . "POINT") (cons 10 p) '(62 . 7)))
        )
      )
    )
  )
  (princ)
)

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on May 06, 2015, 10:53:42 AM

ronjomp,

Thanks, I'll take a look at it.

My other testing without the two mentionned test gives us outside
for any point on the border or directly on a point, unless the border
is into an overlapping zone.

Seems logical to me.

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on May 07, 2015, 05:14:04 AM

ronjomp,

In your test program, you are using the list of all points as being the polyline under Test.

You need to generate pl from the points belonging to the poly densified with either Joe Burke's tracepline
or the slower "Express Tool" equivalent.

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ronjonp on May 07, 2015, 09:37:56 AM

Ah yes ... silly me :)
Can you give the following a test .. the cyan points are the test points and the blue points are the traced polyline. I'm getting really strange results now ( but it's probably just me ).

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on May 07, 2015, 12:48:10 PM

Ron,

You would need at least to add that:

Code: [Select]

(setq b1 (append b1 (list (car b1))))
(setq tp1 (append b1 tp1))

Remember the last point must repeat.
As it is tp1 contains only 255 points.

But I believe that with the selection set as it is, the order of
the polyline is being scrambled.

Would be easier to detect the ename of the polyline
and call approxpoly or tracepline.

Then points could be treated as you are doing.

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ronjonp on May 07, 2015, 12:57:27 PM

Ahh yes ... the order of the points is what is getting hosed. ;)

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on May 10, 2015, 07:08:36 AM

ronjomp,

I've looked into the routine you proposed to replace approxpoly, which calls "Express Tools".

To be fair, tracepoly is limited to polyline only, approxpoly can be used on any type of "vlax-curve".

I rewrote it entirely in order to optimize speed and be able to define the tolerance in terms of the maximum sagitta allowed between the segment and the curve.

Here goes the code followed by a small benchmark on a polyline composed of a single arc.
Note that I had to adjust the tolerance from angular to linear to be able to compare.

Code - Auto/Visual Lisp: [Select]

;;                                                                            ;
;; tracepline2     by ymg                                                     ;
;;                                                                            ;
;; Argument:  en,   Ename of a Polyline                                       ;
;;           tol,  Tolerance (Maximum Sagitta Allowed on Bulges)              ;
;;                                                                            ;
;; Return:  An Ordered Points List Approximating the Polyline                 ;
;;       (Requires ceil function)                                             ;
 
(defun tracepline2 (en tol / b d i j obj pl)
   ;(if (= (type en) 'vla-object) ; 
   ;   (setq obj en   en (vlax-vla-object->ename  obj))
       (setq obj (vlax-ename->vla-object en))
   ;)  
   (setq pl (cons (vlax-curve-getpointatparam en (setq i (vlax-curve-getEndParam en))) pl))
         
   (repeat (fix i)
      (if (not (zerop (setq b (abs (vlax-invoke obj 'getbulge (setq i (1- i)))))))
         (progn
            (setq j (ceil (sqrt (/ (* 0.5 (distance (car pl) (vlax-curve-getpointatparam en i)) b) tol))) 
                  d (/ 1.0 j)
                  i (1+ i)
            )
            (repeat j
                (setq pl (cons (vlax-curve-getpointatparam en (setq i (- i d))) pl))
            )
         )
         (setq pl (cons (vlax-curve-getPointAtParam en i) pl))
      ) 
   )
   pl
)
 
;; Ceiling function, Returns the smallest integer not less than x.            ;
(defun ceil  (x) (if (> (rem x 1) 0)    (+ (fix x) 1) (fix x)))
 
 

Quote

(benchmark '((tracepline en 0.667)(tracepline2 en 0.001) (acet-list-remove-adjacent-dups (acet-geom-object-point-list en 0.001))))
Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):

(TRACEPLINE2 EN 0.001)........................1966 / 6.96 <fastest>
(ACET-LIST-REMOVE-ADJACENT-DUPS (ACE...)......3416 / 4.01
(TRACEPLINE EN 0.667)........................13682 / 1.00 <slowest>
_$ (length (TRACEPLINE2 EN 0.001))
127
_$ (length (acet-list-remove-adjacent-dups (acet-geom-object-point-list en 0.001)))
130
_$ (length (TRACEPLINE EN 0.667))
127

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: Lee Mac on May 10, 2015, 07:30:30 AM

Quote from: ymg on May 10, 2015, 07:08:36 AM

...able to define the tolerance in terms of the maximum sagitta allowed between the segment and the curve.

Code - Auto/Visual Lisp: [Select]
< ... >
(setq j (ceil (sqrt (/ (* 0.5 (distance (car pl) (vlax-curve-getpointatparam en i)) b) tol)))
d (/ 1.0 j)
i (1+ i)
)
(repeat j
(setq pl (cons (vlax-curve-getpointatparam en (setq i (- i d))) pl))
)
< ... >

Nice idea ymg :-)

This (http://lee-mac.com/entitytopointlist.html) was my approach from some time ago, but your method of dealing with bulges is much more elegant.

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on May 10, 2015, 07:52:18 AM

Lee,

Thanks!,

However function tracepline2 supports only polylines, yours is more like the "Express Tools" one.

Another disadvantage to it is that we always interpolate. Thus our resulting point list is always smaller than the original polyline.

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: chlh_jd on May 17, 2015, 07:25:51 AM

Quote from: ymg on May 10, 2015, 07:52:18 AM

...
Another disadvantage to it is that we always interpolate. Thus our resulting point list is always smaller than the original polyline.

Hi , Ymg
If to determine a given point in Polyline with bulge , yours has sufficient accuracy , I suggest add the closest point into pointlist , it can reduce a lot of points builded .

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on May 18, 2015, 08:56:10 AM

chlh_jd,

Quote

I suggest add the closest point into pointlist , it can reduce a lot of points builded .

Not sure I understand your suggestion. Adding the points you are showing would double the number of points to process, and would be equivalent to to reducing the tolerance.

What I meant, is there are some methods where you generate the point just outside the curve.
This way the tangent cuts the curve at the midpoint of the chord.

Now if you calculate the area of the polyline you will be much closer than with the interpolation method
which is always smaller than true value.

But may be I am missing something in your suggestion.

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ymg on May 18, 2015, 08:59:39 AM

chlh_jd,

I thing, I caught what you meant.

I believe it makes sense, I will make some test and post when I got results.

ymg

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: chlh_jd on May 19, 2015, 10:49:08 AM

Hi , Ymg
Test this function's result to determine the given point inside a polyline , will reduce a lot of calculation .

Code - Auto/Visual Lisp: [Select]

(defun tracepline3 (en gp / pl obj i p cp cpa mp)
   ; en -- Polyline
   ; gp -- given point 
   ;(if (= (type en) 'vla-object) ; 
   ;   (setq obj en   en (vlax-vla-object->ename  obj))
       (setq obj (vlax-ename->vla-object en))
   ;)  
   (setq pl (cons (vlax-curve-getpointatparam en (setq i (vlax-curve-getEndParam en))) pl)
         cp (vlax-curve-getclosestpointto en gp)
         cpa (vlax-curve-getparamatpoint en cp))
   (repeat (fix i)     
      (if (not (zerop (car (list (abs (vla-getbulge obj (setq i (1- i))))
                                 (setq p (vlax-curve-getpointatparam en i))))))
        (progn
          (setq mp (vlax-curve-getpointatparam en (+ i 0.5)))
         (if (<= i cpa (1+ i))
           (if (<= i cpa (+ i 0.5))
             (setq pl (vl-list*  p cp  mp  pl))
             (setq pl (vl-list*  p mp cp pl)))
           (setq pl (vl-list* p mp pl))))
         (setq pl (cons p pl)))
     )
   pl
)
 

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: chlh_jd on May 19, 2015, 11:13:58 AM

To judge a point location with a polygon I used following functions :

Function1

Code - Auto/Visual Lisp: [Select]

 
;;;Function : judge a point location with polygon
;;;Arg : pt -- a point
;;;      pts -- points of polygon
;;;      eps -- allowance
;;;return :
;;;     -1 -- out of polygon , 0 -- at , 1 -- in
(defun pipl?  (pt pts eps / is at a)
  ;; by Superb-Machete (this name translated by GSLS(SS), I just knew his chinese name &#29378;&#20992;)
  ;; Edit by GSLS(SS) 2011.03.28
  ;; Solved the problem : if a point at the given polygon , it perhap return T or NIL .  
  (cond
    ((vl-some (function (lambda (x) (equal x pt eps))) pts) 0)
    ((and(equal(abs(apply(function +)(mapcar(function (lambda (x y / a)
                           (setq a (rem (- (angle pt x) (angle pt y)) PI))
                           (if (equal (+ (distance pt x) (distance pt y))(distance x y)Eps)
                             (setq at T))a))(cons (last pts) pts) pts))) pi eps)(not at))1)
    (at 0)(-1)))
 

function2

Code - Auto/Visual Lisp: [Select]

(defun EE:pitp (p l)
  ;; check is a point inside the triangle.
  ;; by ElpanovEvgeniy
  (if (vl-some (function (lambda (x) (equal p x 1e-6)))
               l)    T
    (if (< (sin (- (angle (last l) p) (angle (last l) (car l))))
           -1e-6)
      (vl-every
        (function
          (lambda (a b) (< (sin (- (angle a p) (angle a b))) -1e-6)))
        l
        (cdr l)      )
      (vl-every
        (function
          (lambda (a b) (> (sin (- (angle a p) (angle a b))) 1e-6))     )
        l
        (cdr l)
      )
    )
  )
)
 

function3 widding number method

Code - Auto/Visual Lisp: [Select]

;; This method suggest by Lee Mac from http://en.wikipedia.org/wiki/Winding_number
;; function : get widding number
;; l  ---- point set of a Closed Curve
;; pt ---- a given point to determin position with the Closed Curve
;;  return a list (point_postion_num Clokwise_boolean) 
;;          point_postion_num  ----  -1  pt out of curve
;;                             ----   0  pt at curve
;;                             ----   1  pt in curve
;;          Clokwise_boolean   ----  NIL Counter-Clockwise
;;                             ----  T  Clokwise
;; by GSLS(SS) 2012-08-02
(defun get-widding-number (l pt / n r)
  (if (equal (car l) (last l) 1e-6)
    nil
    (setq l (append l (list (car l)))))  
  ;_(setq n (/ ang 2. pi))
  (setq n (widding l pt))
  (if (< n 0)
    (setq r (list T))
    (setq r (list NIL)))  
  ;;deal widding number
  (if (and (> n 0) (equal (1+ (fix n)) n 1e-2))
    (setq n (1+ (fix n)))
    (if (and (< n 0) (equal (1- (fix n)) n 1e-2))
      (setq n (1- (fix n)))
      (setq n (fix n))))
  (if (= (rem n 2) 0)
    (cons -1 r)
 
;; use function 
(defun widding  (l pt)
  (/ (apply
       (function +)
       (mapcar (function (lambda (p1 p2)
                           (ang<api (- (angle pt p2) (angle pt p1)))
                           ))
               l
               (cdr l)))
     2.
     pi))
 
(defun ang<Api (ang)
  (setq ang (rem ang (+ pi pi)))
  (cond ((< ang (- pi))
         (+ ang (+ pi pi)))
        ((> ang pi)
         (- ang (+ pi pi)))
        (ang)))
 

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: ribarm on January 14, 2017, 12:48:42 PM

Here is my version, slow and for polygons without bulges...

At least it's working fine for me...

Code - Auto/Visual Lisp: [Select]

(defun mr_IsPointInside ( pt ptlst / trianglst ptinsidetriangle-p trl )
 
  (defun trianglst ( ptlst / unique LM:ListClockwise-p clockwise-p l p1 p2 p3 trl )
 
    (defun unique ( l )
      (if l (cons (car l) (unique (vl-remove-if (function (lambda ( x ) (equal x (car l) 1e-6))) l))))
    )
 
    ;; List Clockwise-p - Lee Mac
    ;; Returns T if the point list is clockwise oriented
 
    (defun LM:ListClockwise-p ( lst )
      (minusp
        (apply '+
          (mapcar
            (function
              (lambda ( a b )
                (- (* (car b) (cadr a)) (* (car a) (cadr b)))
              )
            )
            lst (cons (last lst) lst)
          )
        )
      )
    )
 
    (defun clockwise-p ( p1 p2 p3 )
      (< (* (- (car  p2) (car  p1)) (- (cadr p3) (cadr p1)))
         (* (- (cadr p2) (cadr p1)) (- (car  p3) (car  p1)))
      )
    )
 
    (setq l ptlst)
    (while (> (length ptlst) 3)
      (setq p1 (car ptlst) p2 (cadr ptlst) p3 (caddr ptlst))
      (cond
        ( (LM:ListClockwise-p ptlst)
          (if
            (and
              (clockwise-p p1 p2 p3)
              (= (length (unique (vl-remove nil (mapcar (function (lambda ( a b ) (inters p1 p2 a b))) l (cdr (reverse (cons (car l) (reverse l)))))))) 2)
              (= (length (unique (vl-remove nil (mapcar (function (lambda ( a b ) (inters p2 p3 a b))) l (cdr (reverse (cons (car l) (reverse l)))))))) 2)
              (= (length (unique (vl-remove nil (mapcar (function (lambda ( a b ) (inters p3 p1 a b))) l (cdr (reverse (cons (car l) (reverse l)))))))) 2)
            )
            (progn
              (setq trl (cons (list p1 p2 p3) trl))
              (setq ptlst (vl-remove p2 ptlst))
              (setq ptlst (cdr (reverse (cons (car ptlst) (reverse ptlst)))))
            )
            (setq ptlst (cdr (reverse (cons (car ptlst) (reverse ptlst)))))
          )
        )
        ( (not (LM:ListClockwise-p ptlst))
          (if
            (and
              (not (clockwise-p p1 p2 p3))
              (= (length (unique (vl-remove nil (mapcar (function (lambda ( a b ) (inters p1 p2 a b))) l (cdr (reverse (cons (car l) (reverse l)))))))) 2)
              (= (length (unique (vl-remove nil (mapcar (function (lambda ( a b ) (inters p2 p3 a b))) l (cdr (reverse (cons (car l) (reverse l)))))))) 2)
              (= (length (unique (vl-remove nil (mapcar (function (lambda ( a b ) (inters p3 p1 a b))) l (cdr (reverse (cons (car l) (reverse l)))))))) 2)
            )
            (progn
              (setq trl (cons (list p1 p2 p3) trl))
              (setq ptlst (vl-remove p2 ptlst))
              (setq ptlst (cdr (reverse (cons (car ptlst) (reverse ptlst)))))
            )
            (setq ptlst (cdr (reverse (cons (car ptlst) (reverse ptlst)))))
          )
        )
      )
    )
    (setq trl (cons (list (car ptlst) (cadr ptlst) (caddr ptlst)) trl))
    trl
  )
 
  (defun ptinsidetriangle-p ( pt p1 p2 p3 )
    (or
      (and
        (not
          (or
            (inters pt p1 p2 p3)
            (inters pt p2 p1 p3)
            (inters pt p3 p1 p2)
          )
        )
        (not
          (or
            (> (+ (distance pt p1) (distance pt p2)) (+ (distance p3 p1) (distance p3 p2)))
            (> (+ (distance pt p2) (distance pt p3)) (+ (distance p1 p2) (distance p1 p3)))
            (> (+ (distance pt p3) (distance pt p1)) (+ (distance p2 p3) (distance p2 p1)))
          )
        )
      )
      (equal (distance p1 p2) (+ (distance p1 pt) (distance pt p2)) 1e-8)
      (equal (distance p2 p3) (+ (distance p2 pt) (distance pt p3)) 1e-8)
      (equal (distance p3 p1) (+ (distance p3 pt) (distance pt p1)) 1e-8)
    )
  )
 
  (setq trl (trianglst ptlst))
  (and
    (vl-some (function (lambda ( x ) (ptinsidetriangle-p pt (car x) (cadr x) (caddr x)))) trl)
    (not (vl-some (function (lambda ( a b ) (equal (distance a b) (+ (distance a pt) (distance pt b)) 1e-8))) ptlst (cdr (reverse (cons (car ptlst) (reverse ptlst))))))
  )
)
 

I used it here :
https://www.theswamp.org/index.php?topic=52465.msg574455#new

It proofed to be good...
M.R.
(This topic is old, but I decided to revive it as it's very useful..)

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: mailmaverick on January 15, 2017, 12:09:22 AM

In order to check whether the point is within a list of points, why can't we use SSGET _WP (list 'Points') (list (cons 0 "POINT")) and check whether the required point is within the selection set or not.

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: MP on January 15, 2017, 12:36:46 AM

Because ObjectDBX.

Because the point may not be an object but merely a test coordinate.

An aside, ssget is not reliable if the area of interest is not visible.

Title: Re: Point is Inside polyline (Now with Bulges)
Post by: mailmaverick on February 14, 2017, 05:59:54 PM

Quote from: chlh_jd on May 19, 2015, 11:13:58 AM

To judge a point location with a polygon I used following functions :

Function1
.......
.......

function2
.......
.......

function3 widding number method
.......
.......

Dear, you have given three functions. Can these three functions be interchangeably used, or are there certain cases (scenarios) where a particular function should be used ?

TheSwamp

Code Red => AutoLISP (Vanilla / Visual) => Topic started by: ymg on December 10, 2014, 12:56:28 PM