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

0 Members and 1 Guest are viewing this topic.

chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #30 on: July 27, 2012, 01:56:21 PM »
Perhaps , When the grid division is not small enough in step1 ,  ALL close to the max-dia zone from step1 must be calculated in step2  ?

Is very important to the value of (step1)
If there are areas of similar size could potentially contain the maximum circle, it is appropriate to increase this value, to the detriment of the time required.
Increasing the value of (repeat N (grid_2) (Point_center)) is then refined the position of point searched.

(grid_1) ---> subdivision = step1 x step1

(grid_2) ---> subdivision = step2 x step2
Wonderful explanation, GP, Thank you very much.


chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #31 on: July 27, 2012, 02:34:24 PM »
Stefan,Excellent!! 8-)
Both of you are geniuses!
1+

I guess, AutoCAD has its own regulations on the offset curve .

chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #32 on: July 27, 2012, 02:41:23 PM »
matrix take shape and fill it with a brush matrix
then add up the numbers and find the position of the greatest number.
Excellent algorithm !
Look forward to further implementation .

Does it has been used in the AutoCAD Core Applications ?

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #33 on: July 27, 2012, 11:34:22 PM »
matrix take shape and fill it with a brush matrix
then add up the numbers and find the position of the greatest number.
Excellent algorithm !
Look forward to further implementation .

Does it has been used in the ?

Yes, I have used this algorithm in one of the commercial programs. I can not publish the code here, and details of use. But I have shown the way!

I do not work in the autodesk, though, I am now a member of the ADN.
I think that these algorithms are not used in AutoCAD Core Applications, but can not be sure...

chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #34 on: July 28, 2012, 02:34:16 AM »
Yes, I have used this algorithm in one of the commercial programs. I can not publish the code here, and details of use. But I have shown the way!
Depth explanation of the grid method , Thanks again .
I think that these algorithms are not used in AutoCAD Core Applications, but can not be sure...
In some old acad versions , I miss seen that boundary can be created by two method , one is Filling Method , another is Ray Method .

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #35 on: July 28, 2012, 03:04:00 AM »
"Ray Method" is a method for determining the inside or the outside.
In their programs, I use another method to determine the inside or the outside. It does not require checking the intersection and running quickly.

need to check the direction of a polyline, the angle between the direction of the polyline and the first derivative. If 0 < A < pi and polyline counter-clockwise, the point is inside. If the nearest point on the polyline gets on top, should be repeated to a neighboring segment. further

PS. ray method sometimes gives an error - if the beam passes through the tangent to the path and not falling into one point of intersection gives the...
therefore, I developed another method that works fast enough...
« Last Edit: July 28, 2012, 03:07:12 AM by ElpanovEvgeniy »

chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #36 on: July 29, 2012, 02:47:33 PM »
"Ray Method" is a method for determining the inside or the outside.
In their programs, I use another method to determine the inside or the outside. It does not require checking the intersection and running quickly.

need to check the direction of a polyline, the angle between the direction of the polyline and the first derivative. If 0 < A < pi and polyline counter-clockwise, the point is inside. If the nearest point on the polyline gets on top, should be repeated to a neighboring segment. further

PS. ray method sometimes gives an error - if the beam passes through the tangent to the path and not falling into one point of intersection gives the...
therefore, I developed another method that works fast enough...
Thanks ElpanovEvgeniy .
Agree with you , but I have not understood that how to determine which point's and how many point's First derivative in the Curve ?
For polygon ,  one by one ; For Polyline (contained arcs) or other type curve ?

Faster

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #37 on: July 29, 2012, 10:29:31 PM »
According to ElpanovEvgeniy's algorithm,I wrote the following codes:
Code - Auto/Visual Lisp: [Select]
  1. (defun PtInPOLY-P  (POLY PT / CP PL PARAM DEV A)
  2.   (defun LM:ListClockwise-p ( lst )
  3.     (minusp
  4.         (apply '+
  5.             (mapcar
  6.                 (function
  7.                     (lambda ( a b )
  8.                         (- (* (car b) (cadr a)) (* (car a) (cadr b)))
  9.                     )
  10.                 )
  11.                 lst (cons (last lst) lst)
  12.             )
  13.         )
  14.     )
  15. )
  16.  
  17.  
  18.   (cond
  19.     ((equal pt
  20.             (setq cp (vlax-curve-getclosestpointto poly pt))
  21.             1e-8))
  22.     (t
  23.      (setq pl
  24.             (mapcar
  25.               'cdr
  26.               (vl-remove-if-not
  27.                 '(lambda (x) (= 10 (car x)))
  28.                 (entget poly)
  29.                 )
  30.               )
  31.            )
  32.      (setq param (vlax-curve-getparamatpoint poly cp))
  33.      (if (not (setq dev (vlax-curve-getFirstDeriv poly param)))
  34.        (if (not (setq dev (vlax-curve-getFirstDeriv
  35.                             poly
  36.                             (setq param (+ 1e-8 param)))))
  37.          (setq dev (vlax-curve-getFirstDeriv
  38.                      poly
  39.                      (setq param (- param 1e-8 1e-8))))
  40.          )
  41.        )
  42.      (setq cp (vlax-curve-getpointatparam poly param))
  43.      (setq a (- (angle cp pt) (angle '(0 0 0) dev)))
  44.      (if (MINUSP a)
  45.        (setq a (+ a pi pi)))
  46.      (if (LM:ListClockwise-p pl)
  47.        (> a pi)
  48.        (< a pi)
  49.        )
  50.      )
  51.     )
  52.   )
  53.  

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #38 on: July 29, 2012, 11:44:16 PM »
good code
It does not take into account details.
1. As I said, if the closest point falls on the top, you need to jointly consider both segments.
2. check the direction of a polyline, written by Lee does not work with polylines having arc segments.
« Last Edit: July 29, 2012, 11:59:31 PM by ElpanovEvgeniy »

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)

Faster

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #40 on: July 30, 2012, 02:41:24 AM »
good code
It does not take into account details.
1. As I said, if the closest point falls on the top, you need to jointly consider both segments.
2. check the direction of a polyline, written by Lee does not work with polylines having arc segments.
Thank you  ElpanovEvgeniy!
This is improved version:
I wondered why the function "LM:ListClockwise-p " does not work with polylines having arc segments.
Code - Auto/Visual Lisp: [Select]
  1. (defun PtInPOLY-P  (POLY PT        /       CP      LW
  2.                                    MINP    MAXP    MINX    MINY
  3.                                    MAXX    MAXY    X       Y
  4.                                    LST     CLOCKWISEP      ENDPARAM
  5.                                    CURVELENGTH     PARAM   DIST
  6.                                    D1      D2      DEV     A)
  7.   (cond
  8.     ((equal pt
  9.             (setq cp (vlax-curve-getclosestpointto poly pt))
  10.             1e-8))
  11.     ((progn
  12.        (vla-GetBoundingBox
  13.          (setq lw (vlax-ename->vla-object POLY))
  14.          'MinP
  15.          'MaxP)
  16.        (setq MinP (vlax-safearray->list MinP))
  17.        (setq MaxP (vlax-safearray->list MaxP))
  18.        (setq minx (car MinP)
  19.              miny (cadr MinP)
  20.              maxx (car MaxP)
  21.              maxy (cadr MaxP)
  22.              x    (car pt)
  23.              y    (cadr pt)
  24.              )
  25.        (or (< x minx)
  26.            (> x maxx)
  27.            (< y miny)
  28.            (> y maxy)
  29.            )
  30.        )
  31.      NIL
  32.      )
  33.     (t
  34.      (setq
  35.        lst (mapcar
  36.              (function
  37.                (lambda (x)
  38.                  (vlax-curve-getParamAtPoint
  39.                    lw
  40.                    (vlax-curve-getClosestPointTo lw x)
  41.                    )
  42.                  )
  43.                )
  44.              (list minp
  45.                    (list minx maxy)
  46.                    MaxP
  47.                    (list maxx miny)
  48.                    )
  49.              )
  50.        )
  51.      (setq ClockwiseP
  52.             (if (or
  53.                   (<= (car lst) (cadr lst) (caddr lst) (cadddr lst))
  54.                   (<= (cadr lst) (caddr lst) (cadddr lst) (car lst))
  55.                   (<= (caddr lst) (cadddr lst) (car lst) (cadr lst))
  56.                   (<= (cadddr lst) (car lst) (cadr lst) (caddr lst))
  57.                   ) ;_  or
  58.               t
  59.               ) ;_  if
  60.            )
  61.      (setq endparam    (vlax-curve-getendparam poly)
  62.            curvelength (vlax-curve-getDistAtParam poly endparam)
  63.            )
  64.      (setq param (vlax-curve-getparamatpoint poly cp)
  65.            dist  (vlax-curve-getDistAtParam poly param)
  66.            )
  67.      (if (equal param (fix param) 1e-8)
  68.        (progn
  69.          (setq d1 (- dist 1e-8))
  70.          (if (minusp d1)
  71.            (setq d1 (+ curvelength d1))
  72.            )
  73.          (setq d2 (+ dist 1e-8))
  74.          (if (> d2 curvelength)
  75.            (setq d2 (- d2 curvelength)))
  76.          (if (< (distance pt (vlax-curve-getpointatdist poly d1))
  77.                 (distance pt (vlax-curve-getpointatdist poly d2))
  78.                 )
  79.            (setq param (vlax-curve-getparamatdist poly d1))
  80.            (setq param (vlax-curve-getparamatdist poly d2))
  81.            )
  82.          )
  83.        )
  84.      (setq dev (vlax-curve-getFirstDeriv poly param)
  85.            cp  (vlax-curve-getpointatparam poly param)
  86.            )
  87.      ;|(setq a (- (angle cp pt) (angle '(0 0 0) dev)))
  88.      (if (MINUSP a)
  89.        (setq a (+ a pi pi)))
  90.      (if ClockwiseP
  91.        (> a pi)
  92.        (< a pi)
  93.        )|;
  94.   ;;Another alternative judge method
  95.        (=       ClockwiseP
  96.         (
  97.          (lambda (p1 p2 p3)
  98.            (<
  99.              (* (- (car p2) (car p1)) (- (cadr p3) (cadr p1)))
  100.              (* (- (cadr p2) (cadr p1)) (- (car p3) (car p1)))
  101.              )
  102.            )
  103.           pt
  104.           cp
  105.           (mapcar '+ cp dev)
  106.           )
  107.         )
  108.      )
  109.     )
  110.   )
  111.  
« Last Edit: July 31, 2012, 01:48:22 AM by Faster »

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #41 on: July 30, 2012, 03:49:55 AM »
I wondered why the function "LM:ListClockwise-p " does not work with polylines having arc segments.

which direction this lwpolyline?

The code Lee will give the wrong direction...

Faster

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #42 on: July 30, 2012, 04:09:42 AM »
I wondered why the function "LM:ListClockwise-p " does not work with polylines having arc segments.

which direction this lwpolyline?

The code Lee will give the wrong direction...
I see, thank you very much.

chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #43 on: July 30, 2012, 11:41:17 AM »
This is improved version:
I wondered why the function "LM:ListClockwise-p " does not work with polylines having arc segments.
Hi Faster , good codes.
Test not ok for Self-intersecting curves , I post the test dwg .

Faster

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #44 on: July 30, 2012, 08:45:59 PM »
This is improved version:
I wondered why the function "LM:ListClockwise-p " does not work with polylines having arc segments.
Hi Faster , good codes.
Test not ok for Self-intersecting curves , I post the test dwg .
I think ElpanovEvgeniy's  algorithm for Self-intersecting curves may be invalid!
« Last Edit: July 30, 2012, 11:19:52 PM by Faster »