Author Topic: =={challenge}==Find the maximum inscribed circle  (Read 26883 times)

0 Members and 1 Guest are viewing this topic.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #45 on: July 31, 2012, 12:07:01 AM »
I think ElpanovEvgeniy's  algorithm for Self-intersecting curves may be invalid!

Yes!  :-)
I developed an algorithm for use in production.
You can not make the part that has self-intersection...
« Last Edit: July 31, 2012, 12:12:11 AM by ElpanovEvgeniy »

VVA

  • Newt
  • Posts: 166
Re: =={challenge}==Find the maximum inscribed circle
« Reply #46 on: July 31, 2012, 04:07:49 AM »
I have long been using the algorithm proposed by Eugene. Thank him again.   :lol: On the topic of all polylinienrichtungen counterclockwise Irneb offered another option for the Self-intersecting curves

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: =={challenge}==Find the maximum inscribed circle
« Reply #47 on: July 31, 2012, 11:16:38 AM »
That code of mine still doesn't work on the PL as per Evgeniy's example in post #42. And it's debatable on which direction you "say" a self-intersecting polyline is. All my code does is to sum the changes in angles between vectors - then testing if the sum is positive / negative. So a very large vector has the same weighting as a very small one. I think this is where the issue might be resolved.

As I understand it, a "true" reflection of self-intersecting polylines might be derived by generating the intersection areas, calculating their directions and weighting by their areas.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: =={challenge}==Find the maximum inscribed circle
« Reply #48 on: July 31, 2012, 11:38:45 AM »
Perhaps using a similar approach to my original, but splitting the polyline into equal parts instead of simply by vectors:
Code - Auto/Visual Lisp: [Select]
  1. (defun pl-ccw-p  (obj / angle@par EndPar grain par delta aT a1 a2)
  2.   (defun angle@par (par) (angle '(0.0 0.0 0.0) (vlax-curve-getFirstDeriv obj par)))
  3.   (setq grain 1000
  4.         delta (/ (setq EndPar (vlax-curve-getEndParam obj)) grain)
  5.         par   0.0
  6.         a1    (angle@par par)
  7.         aT 0.0)
  8.   (repeat grain
  9.     (setq a2 (angle@par (min EndPar (setq par (+ par delta))))
  10.           a  (- a2 a1))
  11.     (if (> (abs a) pi)
  12.       (setq a (* (if (< a 0.0)
  13.                    -1.0
  14.                    1.0)
  15.                  (- (abs a) (* pi 2)))))
  16.     (setq aT (+ aT a)
  17.           a1 a2))
  18.   (>= aT 0.0))
Though it's still not working for the self-intersecting PL as per Faster's post #45.  ::)
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
Re: =={challenge}==Find the maximum inscribed circle
« Reply #49 on: July 31, 2012, 03:41:14 PM »
When a pline crosses over itself how do you define direction?
And does you definition have exceptions?
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

Faster

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #50 on: August 01, 2012, 12:36:17 AM »
We should define the direction of self-intersecting PL   each loop!
We cannot say the self-intersecting PL is clockwise or counter-clockwise.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: =={challenge}==Find the maximum inscribed circle
« Reply #51 on: August 01, 2012, 04:02:41 AM »
Exactly! If you want to define a direction for a self-crossing polyline as a whole, all I can think of is to use each loop's area as a weighting. E.g. see attached: If using this definition the left PL would be CCW and the right CW.

But it's a moot point. As Faster's said, the more important idea is figuring out the direction of each loop. Thus you have to somehow split the polyline into it's component loops, then calculate each one's direction individually (which you'd have to do in any case to figure the area weighted version as I'm suggesting).
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Lee Mac

  • Seagull
  • Posts: 12914
  • London, England
Re: =={challenge}==Find the maximum inscribed circle
« Reply #52 on: August 01, 2012, 04:31:11 AM »
Why not use the winding number of th curve to determine the overall direction?

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: =={challenge}==Find the maximum inscribed circle
« Reply #53 on: August 01, 2012, 06:25:21 AM »
I suppose that's a good idea, but it's extremely dependent on the selection of a centroid point. E.g. following this:
Code - Auto/Visual Lisp: [Select]
  1. (defun pl-ccw-p1 (obj / len grain delta dist pts cent a1 a2 a wind)
  2.         grain 1000.
  3.         delta (/ len grain)
  4.         dist 0.
  5.         pts (list (vlax-curve-getPointAtDist obj dist))
  6.         cent (car pts))
  7.   (while (<= (setq dist (+ dist delta)) len)
  8.     (setq pts (cons (vlax-curve-getPointAtDist obj dist) pts)
  9.           cent (mapcar '+ cent (car pts))))
  10.   (setq cent (mapcar '(lambda (n) (/ n grain)) cent)
  11.         wind 0.
  12.         pts (reverse pts)
  13.         a1 (angle cent (car pts)))
  14.   (foreach pt (cdr pts)
  15.     (setq a2 (angle cent pt)
  16.           a (- a2 a1))
  17.     (if (> (abs a) pi)
  18.       (setq a (* (if (< a 0.0)
  19.                    -1.0
  20.                    1.0)
  21.                  (- (abs a) (* pi 2)))))
  22.     (setq wind (+ wind a)
  23.           a1 a2))
  24.   (>= wind 0.))
It returns CW for the left poly in my previous post, but CCW for the right one. Exactly the opposite of what I'd expect.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #54 on: August 01, 2012, 11:59:52 AM »
Why not use the winding number of th curve to determine the overall direction?
Hi Lee Mac , I try to use the method you suggest .
It can determine CW or CCW easily ,
but I don't know how to use the counts-number to determine the point is in or out for self-intersecting curves , Even get the wrong counts-number for star-polygon.
following is poor codes .
Code: [Select]
(defun c:test (/ en pt l num)
  (setq en (car (entsel "\n Select a curve :")))
  (setq l (get_closed_curve_pts en))
  (while (setq pt (getpoint "\nSelect a point :"))
    (if (equal (vlax-curve-getclosestpointto en pt) pt 1e-6)
      ;_point at curve
      (princ "\Point at the curve .")
      (progn
    (setq num (get-widding-number l pt))
   (princ (strcat "\n Counts" (rtos num 2 1)))
    ;_this often wrong result ...
    (setq num (fix num));_?
    ;_how to use counts number ?
    (cond ((< -1 num 1)
   (alert "OUT ")
  )
  ((< num 0)
   (if (= (rem num 2) 0);_does this is correct ?
     (alert "Curve clockwise , \n\r Point OUT")
     (alert "Curve clockwise , \n\r Point IN")
   )
  )
  (t
   (if (= (rem num 2) 0);_does this is correct ?
     (alert "Curve counter-clockwise , \n\r Point OUT")
     (alert "Curve counter-clockwise , \n\r Point IN")
   )
  )
    )   
  )))
  (princ)
)
;;get points of a closed curve
(defun get_closed_curve_pts (en / ent et)
  (setq
    ent (entget en)
    et (cdr (assoc 0 ent))
  )
  (cond
    ((= et "LWPOLYLINE")
     ((lambda (/ a b vetex bu p1 p2 l r ang an1 N)
(while (setq ent (member (assoc 10 ent) ent))
  (setq b     (cons (cdar ent) b)
ent   (member (assoc 42 ent) ent)
b     (cons (cdar ent) b)
ent   (cdr ent)
vetex (cons b vetex)
b     nil
  )
)
(while vetex
  (setq a     (car vetex)
vetex (cdr vetex)
bu    (car a)
p1    (cadr a)
  )
  (if l
    (setq p2 (car l))
    (setq p2 (cadr (last vetex))
  l  (cons p2 l)
    )
  )
  (if (equal bu 0 1e-6)
    (setq l (cons p1 l))
    (progn
      (setq ang (* 2 (atan bu))
    r (/ (distance p1 p2)
   (* 2 (sin ang))
)
    c (polar p1
       (+ (angle p1 p2) (- (/ pi 2) ang))
       r
)
    r (abs r)
    ang (abs (* ang 2.0))
    N (abs (fix (/ ang 0.0174532925199433)))
      )
      (if (= N 0)
(setq l (cons p1 l))
(progn
  (setq an1 (/ ang N)
ang (angle c p2)
  )
  (if (not (minusp bu))
    (setq an1 (- an1))
  )
  (repeat (1- N)
    (setq ang (+ ang an1))
    (setq l (cons (polar c ang r) l))
  )
  (setq l (cons p1 l))
)
      )
    )
  )
)
l
      )
     )
    )
    ((= et "CIRCLE")
     ((lambda (c R / sa ptl)
(setq sa 0.0)
(repeat 180
  (setq ptl (cons (polar c sa R) ptl)
sa  (+ sa 0.0174532925199433)
  )
)
(setq ptl (reverse ptl))
(append
  ptl
  (mapcar (function
    (lambda (p)
      (mapcar (function +) c (mapcar (function -) c p))
    )
  )
  ptl
  )
)
      )
       (dxf 10 ent)
       (dxf 40 ent)
     )
    )
    ((= et "SPLINE")
     ((lambda (/ r l _oce)
(setq _oce (getvar "CMDECHO"))
(setvar "CMDECHO" 0)
(if (vl-catch-all-apply
      (function vl-cmdf)
      (list "_PEDIT"
    (vlax-vla-object->ename
      (vla-copy (vlax-ename->vla-object en))
    )
    ""
    10
    ""
      )
    )
  (progn
    (setq l (ss-assoc 10 (entget (setq r (entlast)))))
    (if (vlax-curve-isClosed r)
      (setq l (append l (list (car l))))
    )
    (entdel r)
  )
)
(setvar "CMDECHO" _oce)
l
      )
     )
    )
    ((= et "ELLIPSE")
     ((lambda (/ e l _os)
(setq _os (getvar "OSMODE"))
(setvar "OSMODE" 0)
(vl-catch-all-apply
  (function vla-offset)
  (list (vlax-ename->vla-object en) 0.1)
)
(setq e (entlast))
(vl-catch-all-apply
  (function vla-offset)
  (list (vlax-ename->vla-object (entlast)) -0.1)
)
(entdel e)
(setq e (entlast))
(setq l (ss-assoc 10 (entget e)))
(entdel e)
(setvar "OSMODE" _os)
l
      )
     )
    )
  )
)
;;
(defun get-widding-number (l pt / ang p1 p2)
  (if (equal (car l) (last l) 1e-6)
    nil
    (setq l (append l (list (car l))))
  )
  (setq ang 0.0)
  (while (cadr l)
    (setq p1 (car l)
  p2 (cadr l)
  l  (cdr l)
    )
    (if (equal p1 p2)
      (setq an1 0.0)
    (setq an1
   ((lambda (/  a  b c d e f g)    
    (setq b (distance p1 pt)
  c (distance p2 pt)
  a (distance p1 p2)
  d (- (* (- (car p1) (car pt)) (- (cadr p2) (cadr pt)))
       (* (- (car p2) (car pt)) (- (cadr p1) (cadr pt)))
    )
  e  (+ (* b b) (* c c) (* -1 a a))
  f (acos (/ e 2. b c))
  g (/ d (abs d)))
    (if (< e 0) (* g (- pi f))(* g f))) 
)
    ))
    (setq ang (+ ang an1))
  )
  (/ ang 2. pi)
)
;;------------------
(defun dxf (co el)
  (cdr (assoc co el))
  )
;;
(defun acos (a)
  (if (and (= (numberp a) T)
   (<= (abs a) 1.0)
      )
    (if (= a 0.0)
      (* pi 0.5)
      (atan (/ (sqrt (- 1 (* a a)))
       a
    )
      )
    )   
  )
)
;;
(defun ss-assoc (a lst / b res)
  (while (setq b (assoc a lst))
    (setq lst  (cdr (member b lst))
  res (cons (cdr b) res)
    ))(reverse res))
« Last Edit: August 01, 2012, 03:15:17 PM by chlh_jd »

chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #55 on: August 01, 2012, 02:04:06 PM »
correct counts-number's error caused by the decimal precision and non-positive error in solving the angle by Law of cosines .
Now it run well .
Code: [Select]
(defun c:test (/ en pt l num)
  (setq en (car (entsel "\n Select a curve :")))
  (setq l (get_closed_curve_pts en))
  (while (setq pt (getpoint "\nSelect a point :"))
    (if (equal (vlax-curve-getclosestpointto en pt) pt 1e-6)
 ;_point at curve
      (princ "\Point at the curve .")
      (progn
(setq num (get-widding-number l pt))
(princ (strcat "\n Counts" (rtos num 2 1)))
 ;_this often wrong result , because of decimal precision ; Now correct .
(if (equal (fix num) num 1e-4)
  (setq num (fix num))
  (if (and (> num 0) (equal (1+ (fix num)) num 1e-4))
    (setq num (1+ (fix num)))
    (if (and (< num 0) (equal (1- (fix num)) num 1e-4))
      (setq num (1- (fix num)))
      (setq num (fix num)))))
 ;_how to use counts number ?
(cond ((< -1 num 1)
       (alert "OUT ")
      )
      ((< num 0)
       (if (= (rem num 2) 0) ;_does this is correct ?
(alert "Curve clockwise , \n\r Point OUT")
(alert "Curve clockwise , \n\r Point IN")
       )
      )
      (t
       (if (= (rem num 2) 0) ;_does this is correct ?
(alert "Curve counter-clockwise , \n\r Point OUT")
(alert "Curve counter-clockwise , \n\r Point IN")
       )
      )
)
      )
    )
  )
  (princ)
)
;;get points of a closed curve
(defun get_closed_curve_pts (en / ent et)
  (setq
    ent (entget en)
    et (cdr (assoc 0 ent))
  )
  (cond
    ((= et "LWPOLYLINE")
     ((lambda (/ a b vetex bu p1 p2 l r ang an1 N)
(while (setq ent (member (assoc 10 ent) ent))
  (setq b     (cons (cdar ent) b)
ent   (member (assoc 42 ent) ent)
b     (cons (cdar ent) b)
ent   (cdr ent)
vetex (cons b vetex)
b     nil
  )
)
(while vetex
  (setq a     (car vetex)
vetex (cdr vetex)
bu    (car a)
p1    (cadr a)
  )
  (if l
    (setq p2 (car l))
    (setq p2 (cadr (last vetex))
  l  (cons p2 l)
    )
  )
  (if (equal bu 0 1e-6)
    (setq l (cons p1 l))
    (progn
      (setq ang (* 2 (atan bu))
    r (/ (distance p1 p2)
   (* 2 (sin ang))
)
    c (polar p1
       (+ (angle p1 p2) (- (/ pi 2) ang))
       r
)
    r (abs r)
    ang (abs (* ang 2.0))
    N (abs (fix (/ ang 0.0174532925199433)))
      )
      (if (= N 0)
(setq l (cons p1 l))
(progn
  (setq an1 (/ ang N)
ang (angle c p2)
  )
  (if (not (minusp bu))
    (setq an1 (- an1))
  )
  (repeat (1- N)
    (setq ang (+ ang an1))
    (setq l (cons (polar c ang r) l))
  )
  (setq l (cons p1 l))
)
      )
    )
  )
)
l
      )
     )
    )
    ((= et "CIRCLE")
     ((lambda (c R / sa ptl)
(setq sa 0.0)
(repeat 180
  (setq ptl (cons (polar c sa R) ptl)
sa  (+ sa 0.0174532925199433)
  )
)
(setq ptl (reverse ptl))
(append
  ptl
  (mapcar (function
    (lambda (p)
      (mapcar (function +) c (mapcar (function -) c p))
    )
  )
  ptl
  )
)
      )
       (dxf 10 ent)
       (dxf 40 ent)
     )
    )
    ((= et "SPLINE")
     ((lambda (/ r l _oce)
(setq _oce (getvar "CMDECHO"))
(setvar "CMDECHO" 0)
(if (vl-catch-all-apply
      (function vl-cmdf)
      (list "_PEDIT"
    (vlax-vla-object->ename
      (vla-copy (vlax-ename->vla-object en))
    )
    ""
    10
    ""
      )
    )
  (progn
    (setq l (ss-assoc 10 (entget (setq r (entlast)))))
    (if (vlax-curve-isClosed r)
      (setq l (append l (list (car l))))
    )
    (entdel r)
  )
)
(setvar "CMDECHO" _oce)
l
      )
     )
    )
    ((= et "ELLIPSE")
     ((lambda (/ e l _os)
(setq _os (getvar "OSMODE"))
(setvar "OSMODE" 0)
(vl-catch-all-apply
  (function vla-offset)
  (list (vlax-ename->vla-object en) 0.1)
)
(setq e (entlast))
(vl-catch-all-apply
  (function vla-offset)
  (list (vlax-ename->vla-object (entlast)) -0.1)
)
(entdel e)
(setq e (entlast))
(setq l (ss-assoc 10 (entget e)))
(entdel e)
(setvar "OSMODE" _os)
l
      )
     )
    )
  )
)
;;
(defun get-widding-number (l pt / ang p1 p2)
  (if (equal (car l) (last l) 1e-6)
    nil
    (setq l (append l (list (car l))))
  )
  (setq ang 0.0)
  (while (cadr l)
    (setq p1 (car l)
  p2 (cadr l)
  l  (cdr l)
    )
    (if (equal p1 p2)
      (setq an1 0.0)
      (setq an1
     ((lambda (/ a b c d e f g)
(setq b (distance p1 pt)
      c (distance p2 pt)
      a (distance p1 p2)
      d (- (* (- (car p1) (car pt)) (- (cadr p2) (cadr pt)))
   (* (- (car p2) (car pt)) (- (cadr p1) (cadr pt)))
)
      e (+ (* b b) (* c c) (* -1 a a))
      f (abs (acos (/ e 2. b c)));_here must be Positive
      g (/ d (abs d))
)
(if (< e 0)
  (* g (- pi f))
  (* g f)
)
      )
     )
      )
    )
    (setq ang (+ ang an1))
  )
  (/ ang 2. pi)
)

;;------------------
(defun dxf (co el)
  (cdr (assoc co el))
  )
;;
(defun acos (a)
  (if (and (= (numberp a) T)
   (<= (abs a) 1.0)
      )
    (if (= a 0.0)
      (* pi 0.5)
      (atan (/ (sqrt (- 1 (* a a)))
       a
    )
      )
    )   
  )
)
;;
(defun ss-assoc (a lst / b res)
  (while (setq b (assoc a lst))
    (setq lst  (cdr (member b lst))
  res (cons (cdr b) res)
    ))(reverse res))
« Last Edit: August 01, 2012, 03:02:08 PM by chlh_jd »

chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #56 on: August 01, 2012, 02:41:06 PM »
For function unit .
Code: [Select]
;;; SS:ClosedCurve:Pinp&CW?
;;; function ---- Get Given Point position with a closed curve ,
;;;               and determin Curve is Clokwise ?
;;; Curve    ---- A closed curve , Curve-type must be "LWPOLYLINE" "CIRCLE" "ELLIPSE" "SPLINE" ;
;;; pt       ---- a given point (in wcs)
;;; 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-8-2
(defun SS:ClosedCurve:Pinp&CW? (curve pt / p l n r)
  (if (vlax-curve-isclosed curve)
    (progn
      (setq l (get_closed_curve_pts curve))
      (if (equal (setq p (vlax-curve-getclosestpointto en pt))
pt
1e-6
  )
(progn
  (setq n (get-widding-number
    l
    (polar p
   (- (angle (list 0 0 0)
     (vlax-curve-getfirstderiv
       en
       (vlax-curve-getparamatpoint
en
p
       )
     )
      )
      (* 0.5 pi)
   )
                                  0.1
    )    
  )
  )
  (if (< n 0)
    (list 0 T)
    (list 0 NIL)
  )
)
(progn
  (setq n (get-widding-number l pt))
  (if (< n 0)
    (setq r (list T))
    (setq r (list NIL))
  )
  (if (equal (fix n) n 1e-4)
    (setq n (fix n))
    (if (and (> n 0) (equal (1+ (fix n)) n 1e-4))
      (setq n (1+ (fix n)))
      (if (and (< n 0) (equal (1- (fix n)) n 1e-4))
(setq n (1- (fix n)))
(setq n (fix n))
      )
    )
  )
  (if (= (rem n 2) 0)
    (cons -1 r)
    (cons 1 r)
  )
)
      )
    )
  )
)
;;;---------------------
;;
(defun ss-assoc (a lst / b res)
  (while (setq b (assoc a lst))
    (setq lst  (cdr (member b lst))
  res (cons (cdr b) res)
    ))(reverse res))
;;
(defun acos (a)
  (if (and (= (numberp a) T)
   (<= (abs a) 1.0)
      )
    (if (= a 0.0)
      (* pi 0.5)
      (atan (/ (sqrt (- 1 (* a a)))
       a
    )
      )
    )   
  )
)
;; get point set of a closed curve by order
;; this function you improve by yourself acordding your need .
(defun get_closed_curve_pts (en / ent et)
  ;;by GSLS(SS)
  (setq
    ent (entget en)
    et (cdr (assoc 0 ent))
  )
  (cond
    ((= et "LWPOLYLINE")
     ((lambda (/ a b vetex bu p1 p2 l r ang an1 N)
(while (setq ent (member (assoc 10 ent) ent))
  (setq b     (cons (cdar ent) b)
ent   (member (assoc 42 ent) ent)
b     (cons (cdar ent) b)
ent   (cdr ent)
vetex (cons b vetex)
b     nil
  )
)
(while vetex
  (setq a     (car vetex)
vetex (cdr vetex)
bu    (car a)
p1    (cadr a)
  )
  (if l
    (setq p2 (car l))
    (setq p2 (cadr (last vetex))
  l  (cons p2 l)
    )
  )
  (if (equal bu 0 1e-6)
    (setq l (cons p1 l))
    (progn
      (setq ang (* 2 (atan bu))
    r (/ (distance p1 p2)
   (* 2 (sin ang))
)
    c (polar p1
       (+ (angle p1 p2) (- (/ pi 2) ang))
       r
)
    r (abs r)
    ang (abs (* ang 2.0))
    N (abs (fix (/ ang 0.0174532925199433)))
      )
      (if (= N 0)
(setq l (cons p1 l))
(progn
  (setq an1 (/ ang N)
ang (angle c p2)
  )
  (if (not (minusp bu))
    (setq an1 (- an1))
  )
  (repeat (1- N)
    (setq ang (+ ang an1))
    (setq l (cons (polar c ang r) l))
  )
  (setq l (cons p1 l))
)
      )
    )
  )
)
l
      )
     )
    )
    ((= et "CIRCLE")
     ((lambda (c R / sa ptl)
(setq sa 0.0)
(repeat 180
  (setq ptl (cons (polar c sa R) ptl)
sa  (+ sa 0.0174532925199433)
  )
)
(setq ptl (reverse ptl))
(append
  ptl
  (mapcar (function
    (lambda (p)
      (mapcar (function +) c (mapcar (function -) c p))
    )
  )
  ptl
  )
)
      )
       (cdr (assoc 10 ent))
       (cdr (assoc 40 ent))
     )
    )
    ((= et "SPLINE")
     ((lambda (/ r l _oce)
(setq _oce (getvar "CMDECHO"))
(setvar "CMDECHO" 0)
(if (vl-catch-all-apply
      (function vl-cmdf)
      (list "_PEDIT"
    (vlax-vla-object->ename
      (vla-copy (vlax-ename->vla-object en))
    )
    ""
    10
    ""
      )
    )
  (progn
    (setq l (ss-assoc 10 (entget (setq r (entlast)))))
    (if (vlax-curve-isClosed r)
      (setq l (append l (list (car l))))
    )
    (entdel r)
  )
)
(setvar "CMDECHO" _oce)
l
      )
     )
    )
    ((= et "ELLIPSE")
     ((lambda (/ e l _os)
(setq _os (getvar "OSMODE"))
(setvar "OSMODE" 0)
(vl-catch-all-apply
  (function vla-offset)
  (list (vlax-ename->vla-object en) 0.1)
)
(setq e (entlast))
(vl-catch-all-apply
  (function vla-offset)
  (list (vlax-ename->vla-object (entlast)) -0.1)
)
(entdel e)
(setq e (entlast))
(setq l (ss-assoc 10 (entget e)))
(entdel e)
(setvar "OSMODE" _os)
l
      )
     )
    )
  )
)
;;
;; 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 widding number
;; by GSLS(SS) 2012-08-02
(defun get-widding-number (l pt / ang p1 p2)
  (if (equal (car l) (last l) 1e-6)
    nil
    (setq l (append l (list (car l))))
  )
  (setq ang 0.0)
  (while (cadr l)
    (setq p1 (car l)
  p2 (cadr l)
  l  (cdr l)
    )
    (if (equal p1 p2)
      (setq an1 0.0)
      (setq an1
     ((lambda (/ a b c d e f g)
(setq b (distance p1 pt)
      c (distance p2 pt)
      a (distance p1 p2)
      d (- (* (- (car p1) (car pt)) (- (cadr p2) (cadr pt)))
   (* (- (car p2) (car pt)) (- (cadr p1) (cadr pt)))
)
      e (+ (* b b) (* c c) (* -1 a a))
      f (abs (acos (/ e 2. b c)));_here must be Positive
      g (/ d (abs d))
)
(if (< e 0)
  (* g (- pi f))
  (* g f)
)
      )
     )
      )
    )
    (setq ang (+ ang an1))
  )
  (/ ang 2. pi)
)
Test function
Code: [Select]
(defun c:test (/ en pt n)
  (setq en (car (entsel "\n Select a Closed Curve :")))
  (while (setq pt (getpoint "\nSelect a point :"))
    (setq n (SS:ClosedCurve:Pinp&CW? en pt))
    (cond ((and (< (car n) 0) (cadr n))
   (alert "Out , CW")
  )
  ((and (< (car n) 0) (not (cadr n)))
   (alert "Out , CCW")
  )
  ((and (= (car n) 0) (cadr n))
   (alert "At , CW")
  )
  ((and (= (car n) 0) (not (cadr n)))
   (alert "At , CCW")
  )
  ((and (> (car n) 0) (cadr n))
   (alert "In , CW")
  )
  ((and (> (car n) 0) (not (cadr n)))
   (alert "In , CCW")
  )
    )
  )
  (princ)
)
« Last Edit: August 01, 2012, 03:11:31 PM by chlh_jd »

chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #57 on: August 01, 2012, 03:09:01 PM »
The Clockwise case of a closed curve , seem like Associating with the point position ?
Just like the right shape on the up post , is it correct ?

chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #58 on: August 02, 2012, 07:34:21 AM »
Acordding GP's method and codes , and determine pt-in-curve by the method Lee Mac suggest .
It can supports self-intersection , butthe problem that it ps. not correct result yet be there , unless the setp1 is enough great .
The codes get-widding-number seems so poor, Need your improving .( I guess this method used in AutoCAD interface , but didn't know how get it )
Code: [Select]
;;; maximum circle inscribed in a closed polyline
;;; Gian Paolo Cattaneo

(defun C:TesT (/ POLY    POLY_vl   Dx        Dy
       Lp List_vert_poly      list_p_int
       P_center dist    step1     step2     t1
       t2
      )
  (prompt "\nSelect Polyline: ")
  (if (setq POLY (ssname (ssget ":S" '((0 . "LWPOLYLINE"))) 0))
    (progn
      (setq i  1
    t1 (getvar "MilliSecs")
      )
      (setq step1 40) ;--> grid_1
      (setq step2 20) ;--> grid_2
      (setq list_vert_poly (LWPoly->List POLY 10))
      (grid_1)
      (Point_int)
      (grid+)
      (Point_center)
      (repeat 2
(grid_2)
(Point_center)
      )
      (entmake
(list
  (cons 0 "CIRCLE")
  (cons 10 P_center)
  (cons 40 dist)
)
      )
      (setq t2 (getvar "MilliSecs"))
      (princ (strcat "time = " (rtos (- t2 t1) 2 0) " MilliSecs"))
      (princ)
    )
  )
)

;; Restituisce una griglia di punti all'interno del getboundingbox della poly selezionata
;; Returns a grid of points within the BoundingBox of the selected poly
(defun grid_1 (/   p1 p2 X1 Y1 l1)
  (vla-getboundingbox (vlax-ename->vla-object POLY) 'p1 'p2)
  (setq p1 (vlax-safearray->list p1)
p2 (vlax-safearray->list p2)
p1 (list (car p1) (cadr p1))
p2 (list (car p2) (cadr p2))
  )
  (setq Dx (/ (- (car p2) (car p1)) step1))
  (setq Dy (/ (- (cadr p2) (cadr p1)) step1)) 
  (setq Lp (list p1)
X1 (car p1)
Y1 (cadr p1)
  )
  (repeat step1
    (setq Lp (cons (list (setq X1 (+ X1 Dx)) Y1) Lp))
  )
  (setq Lp (list Lp))
  (repeat step1
    (setq  Lp (cons (mapcar (function (lambda (x)
       (list (car x) (+ (cadr x) Dy))
     )
   )
   (car lp)
   )  Lp)
    )
  )
  (setq Lp (apply (function append) Lp))
)


;; Restituisce una griglia di punti intorno al punto centrale (provvisorio)
;; Returns a grid of points around the center point (provisional)
(defun grid_2 (/ P1_ P> n)
  (setq list_p_int nil)
  (setq P1_ (list (- (car P_center) (* Dx 2))
  (- (cadr P_center) (* Dy 2))
    )
  )
  (setq Dx (/ (* 4 Dx) step2))
  (setq Dy (/ (* 4 Dy) step2))
  (setq n 0)
  (setq P> P1_)
  (setq list_p_int (list P1_))
  (repeat (* (1+ step2) step2)
    (setq P> (list (+ (car P>) Dx) (cadr P>)))
    (setq list_p_int (cons P> list_p_int))
    (setq n (1+ n))
    (if (= n step2)
      (progn
(setq n 0)
(setq P1_ (list (car P1_) (+ (cadr P1_) Dy)))
(setq P> P1_)
(setq list_p_int (cons P> list_p_int))
      )
    )
  )
)


;; restituisce la lista dei punti interni ad un poligono
;; dati:  - lista coordinate dei punti -> Lp
;;        - lista coordinate vertici poligono -> list_vert_poly
;; Returns the list of points inside the polyline
(defun Point_int (/ n Pr cont attr p# Pa Pa_ Pb)
  (setq list_p_int nil)
  (foreach Pr Lp
    (if (> (Point-in-ClosedCurve-p list_vert_poly Pr) 0)
      (setq list_p_int (cons Pr list_p_int))
    )
  )
)
;; Infittisce la griglia inserendo altri punti
;; nel centro delle diagonali tra i punti interni
;; Insert points (interior) to increase the density of the grid
(defun grid+ (/ G+)
  (setq G+
(mapcar '(lambda (x)
    (list (+ (car x) (/ Dx 2)) (+ (cadr x) (/ Dy 2)))
  )
list_p_int
)
  )
  (setq list_p_int (append G+ list_p_int))
)


;; Da una lista di punti restituisce quello più lontano da un oggetto
;; dati:  - lista dei punti -> list_p_int
;;        - oggetto -> POLY_vl
;; Returns the farthest point from the polyline
(defun Point_center (/ Pa n Pvic)
  (setq Dist 1e-7)
  (setq P_center nil)
  (foreach Pa list_p_int
    (setq Pvic (vlax-curve-getClosestPointTo Poly Pa))
    (if (> (distance Pa Pvic) Dist)
      (progn
(setq P_center Pa)
(setq Dist (distance Pa Pvic))
      )
    )
  )
)
;;
(defun LWPoly->List (en acc / a b vetex bu p1 p2 l r ang an1 N)
  ;;Acc --- 0 ~ 99
  (setq ent (entget en))
  (while (setq ent (member (assoc 10 ent) ent))
    (setq b (cons (cdar ent) b)
  ent (member (assoc 42 ent) ent)
  b (cons (cdar ent) b)
  ent (cdr ent)
  vetex (cons b vetex)
  b nil
    )
  )
  (while vetex
    (setq a (car vetex)
  vetex (cdr vetex)
  bu (car a)
  p1 (cadr a)
    )
    (if l
      (setq p2 (car l))
      (setq p2 (cadr (last vetex))
    l  (cons p2 l)
      )
    )
    (if (equal bu 0 1e-6)
      (setq l (cons p1 l))
      (progn
(setq ang (* 2 (atan bu))
      r   (/ (distance p1 p2)
     (* 2 (sin ang))
  )
      c   (polar p1
(+ (angle p1 p2) (- (/ pi 2) ang))
r
  )
      r   (abs r)
      ang (abs (* ang 2.0))
      N   (abs (fix (/ ang 0.0174532925199433)))
      N   (min N (1+ Acc))
)
(if (= N 0)
  (setq l (cons p1 l))
  (progn
    (setq an1 (/ ang N)
  ang (angle c p2)
    )
    (if (not (minusp bu))
      (setq an1 (- an1))
    )
    (repeat (1- N)
      (setq ang (+ ang an1))
      (setq l (cons (polar c ang r) l))
    )
    (setq l (cons p1 l))
  )
)
      )
    )
  )
  l
)
;;
;; This method suggest by Lee Mac from http://en.wikipedia.org/wiki/Winding_number
;; function : determin the point position with the closed curve by widding-number method
;; l  ---- point set of a Closed Curve , First item must same as Last item .
;; pt ---- a given point to determin position with the Closed Curve
;;; return a num
;;;           ----  -1  pt out of curve
;;;           ----   0  pt at curve
;;;           ----   1  pt in curve
;; by GSLS(SS) 2012-08-02
(defun Point-in-ClosedCurve-p (l pt / ang p1 p2 n r at)
  (setq ang 0.0
at  nil
  )
  (while (and (cadr l) (not at))
    (setq p1 (car l)
  p2 (cadr l)
  l  (cdr l)
    )
    (if (equal p1 p2 1e-6)
      (setq an1 0.0)
      (setq an1
     ((lambda (/ a b c d e f g)
(setq b (distance p1 pt)
      c (distance p2 pt)
      a (distance p1 p2)
      d (- (* (- (car p1) (car pt)) (- (cadr p2) (cadr pt)))
   (* (- (car p2) (car pt)) (- (cadr p1) (cadr pt)))
)
)
(if (and (equal d 0.0 1e-4) (setq at T))
  pi
  (progn
    (setq
      e (+ (* b b) (* c c) (* -1 a a))
      f (abs ((lambda (x)
(cond ((equal x 0.0 1e-6)(* pi 0.5))
      ((equal x 1.0 1e-6)0.0)
      ((atan (/ (sqrt (- 1 (* x x)))
x
     )
       ))
))
       (/ e 2. b c)
     )
)
      g (if (> d 0)  1  -1)
    )
    (if (< e 0)
      (* g (- pi f))
      (* g f)
    )
  )
)
      )
     )
      )
    )
    (setq ang (+ ang an1))
  )
  ;;deal widding number 
  (if at
    0
    (progn
      (setq n (/ ang 2. pi))
      (if (equal (fix n) n 1e-4)
(setq n (fix n))
(if (and (> n 0) (equal (1+ (fix n)) n 1e-4))
  (setq n (1+ (fix n)))
  (if (and (< n 0) (equal (1- (fix n)) n 1e-4))
    (setq n (1- (fix n)))
    (setq n (fix n))
  )
)
      )
      (if (= (rem n 2) 0)
-1
1
      )
    )
  )
)
;|
(defun c:t1 ( / en l n)
  (setq en (car (entsel))
l (LWPoly->List en 10))
  (while (setq pt (getpoint ))
    (setq n (Point-in-ClosedCurve-p l pt))
   (cond ((> n 0)
     (alert "IN"))
((= n 0)
     (alert "AT"))
(t
  (alert "OUT")))))
  |;
« Last Edit: August 02, 2012, 07:51:07 AM by chlh_jd »

GP

  • Newt
  • Posts: 83
  • Vercelli, Italy
Re: =={challenge}==Find the maximum inscribed circle
« Reply #59 on: August 02, 2012, 10:58:57 AM »
Acordding GP's method and codes , and determine pt-in-curve by the method Lee Mac suggest .
It can supports self-intersection , butthe problem that it ps. not correct result yet be there , unless the setp1 is enough great .
The codes get-widding-number seems so poor, Need your improving .( I guess this method used in AutoCAD interface , but didn't know how get it )
Code: [Select]
.................
.................
;; Returns the list of points inside the polyline
(defun Point_int (/ n Pr cont attr p# Pa Pa_ Pb)
  (setq list_p_int nil)
  (foreach Pr Lp
    (if (> (Point-in-ClosedCurve-p list_vert_poly Pr) 0)
      (setq list_p_int (cons Pr list_p_int))
    )
  )
)
...................
...................

The points inside are not calculated correctly.