Topic: Point is Inside polyline (Now with Bulges)

[ymg]

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]

1. ;;============================================================================;
2. ;;                                                                            ;
3. ;;      PtInPoly_p(): Winding number test for a point in a polygon            ;
4. ;;                                                                            ;
5. ;;      Input:    p = a point                                                 ;
6. ;;               en = ename or vla-object of a closed polyline.               ;
7. ;;                                                                            ;
8. ;;      Return:  t, if point is in polyline. (wn is not 0)                    ;
9. ;;                                                                            ;
10. ;; Original code in C++ by Dan Sunday                                         ;
11. ;; See: http://geomalgorithms.com/a03-_inclusion.html                         ;
12. ;;============================================================================;
13.  
14. (defun PtInPoly_p (p en / i l p1 p2 v wn y)
15.  
16.    ;; Returns t if point p is strictly to the left of v1->v2   by ymg         ;
17.    (defun isleft (p v1 v2 / xp yp)
18.        (setq  xp (car  p)  yp (cadr  p))
19.        (minusp (- (* (- (cadr v1) yp) (- (car v2) xp)) (* (- (car v1) xp) (- (cadr v2) yp))))
20.    )
21.  
22.  
23.    (setq i (+ (vlax-curve-getEndParam en) 1))                
24.    (while (setq v (vlax-curve-getPointAtParam en (setq i (1- i))))
25.        (setq l (cons v l))
26.    )
27.    
28.  
29.    (setq p1 (car  l)
30.           y (cadr p)
31.          wn 0                              
32.    )     
33.  
34.    ;; Loop through all edges of polygon.                                      ;
35.    (foreach p2 (cdr l)
36.       (if (<= (cadr p1) y)
37.          (if (> (cadr p2) y)                          
38.             (if (isleft p p1 p2) (setq wn (1+ wn)))
39.          )  
40.          (if (<= (cadr p2) y)
41.             (if (isleft p p2 p1) (setq wn (1- wn)))
42.          )
43.       )
44.       (setq p1 p2)
45.    )
46.    (not (zerop wn))
47. )
48.  

[VovKa]

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

[ymg]

VovKa,

Yes essentially the same method.

You did it recursively, nice!

ymg

[AARYAN]

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

[ymg]

AARYAN,

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

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


ymg

[Marc'Antonio Alessi]

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

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)
)     

[VovKa]

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
  )
)

[Marc'Antonio Alessi]

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

[VovKa]

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

[Marc'Antonio Alessi]

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...

[ymg]

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

[Marc'Antonio Alessi]

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

[Marc'Antonio Alessi]

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 )
  )
)

[AARYAN]

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

Great routine Mr. Vovka.

Thanks for sharing.

[VovKa]

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