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

0 Members and 1 Guest are viewing this topic.

chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #15 on: July 25, 2012, 02:18:16 AM »
When set step1=100 step2=40 , It get right .
Code: [Select]
...
(progn
            (setq i 1 t1 (getvar "MilliSecs"))
            (setq step1 100) ;--> grid_1
            (setq step2 40) ;--> grid_2
            (setq POLY_vl (vlax-ename->vla-object POLY))
            (setq list_vert_poly (LM:LWPoly->List POLY))
            (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)
        )
...
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  ?
Code: [Select]
    1 2 1
  2 3 4 3 2
1 3 4 5 4 3 1
2 4 5 6 5 4 2
1 3 4 5 4 3 1
  2 3 4 3 2
    1 2 1   1 2 1
          2 3 4 3 2
        1 3 4 5 4 3 1
          2 3 4 3 1
            1 2 1
« Last Edit: July 25, 2012, 02:32:18 AM by chlh_jd »

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #16 on: July 25, 2012, 03:07:14 AM »

Code: [Select]
    1 2 1
  2 3 4 3 2
1 3 4 5 4 3 1
2 4 5 6 5 4 2
1 3 4 5 4 3 1
  2 3 4 3 2
    1 2 1   1 2 1
          2 3 4 3 2
        1 3 4 5 4 3 1
          2 3 4 3 1
            1 2 1

Use a round brush, I tried to explain to another algorithm!
Now I will prepare an explanation ...

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #17 on: July 25, 2012, 03:53:16 AM »
matrix take shape and fill it with a brush matrix
then add up the numbers and find the position of the greatest number.

highflyingbird

  • Bull Frog
  • Posts: 415
  • Later equals never.
Re: =={challenge}==Find the maximum inscribed circle
« Reply #18 on: July 25, 2012, 06:01:37 AM »
Thanks  ElpanovEvgeniy's very good idea , thanks GP's code!
Quote from: lee mac
Here we have:
 
1) It is obvious that circle is inside of the boundary.
 2) Circle must touch the boundary in at least 2 places.
« Last Edit: July 25, 2012, 06:05:11 AM by HighflyingBird »
I am a bilingualist,Chinese and Chinglish.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #19 on: July 25, 2012, 06:24:36 AM »
This is not just an idea - it really works the algorithm used in one of my projects. Allows you to find more space in the lwpolyline and find the skeleton of the contour. The skeleton - the middle line long or branching areas.

GP

  • Newt
  • Posts: 83
  • Vercelli, Italy
Re: =={challenge}==Find the maximum inscribed circle
« Reply #20 on: July 25, 2012, 04:37:32 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
« Last Edit: July 25, 2012, 04:51:04 PM by GP »

highflyingbird

  • Bull Frog
  • Posts: 415
  • Later equals never.
Re: =={challenge}==Find the maximum inscribed circle
« Reply #21 on: July 26, 2012, 02:19:37 AM »
...
GP,Very good explanation,a lot of thanks.

ElpanovEvgeniy, Yes,your algorithm is amazing.
My oalgorithm can get a very accurate answer,but sometimes it doesn't work,and takes a lot of  time.
I am a bilingualist,Chinese and Chinglish.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #22 on: July 26, 2012, 03:11:04 AM »

ElpanovEvgeniy, Yes,your algorithm is amazing.
My oalgorithm can get a very accurate answer,but sometimes it doesn't work,and takes a lot of  time.

I was told algorithm, more than 10 years ago.
He told me a very old wise man.
Ordered to make a shape out of plywood.
Sprinkle dry sand on plywood.
The top of the sand - the largest center of the inscribed circle.
Ridges of - the contour of the skeleton.

highflyingbird

  • Bull Frog
  • Posts: 415
  • Later equals never.
Re: =={challenge}==Find the maximum inscribed circle
« Reply #23 on: July 26, 2012, 03:49:15 AM »
I was told algorithm, more than 10 years ago.
He told me a very old wise man.
Ordered to make a shape out of plywood.
Sprinkle dry sand on plywood.
The top of the sand - the largest center of the inscribed circle.
Ridges of - the contour of the skeleton.

Yes,like this: maybe it's called sand-heap analogy.

let me think of here.
they have some kind of relationship.
« Last Edit: July 26, 2012, 03:55:06 AM by HighflyingBird »
I am a bilingualist,Chinese and Chinglish.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #24 on: July 26, 2012, 04:09:14 AM »
in solving the problem, you can use the exact values ​​in the matrix of the brush.
Then, examining the amount received for each cell in the figure, we can find the actual slope and location of the analyzed edges and center.
But to my task, it was necessary to obtain high speed and the approximate location of the center. Integers have helped increase the speed for large matrices.

a good picture!
perfectly illustrates the algorithm.
So, I created a 3D surface to visualize the results. Z - the amount for each cell

Stefan

  • Bull Frog
  • Posts: 319
  • The most I miss IRL is the Undo button
Re: =={challenge}==Find the maximum inscribed circle
« Reply #25 on: July 26, 2012, 06:49:33 AM »
My version
Code: [Select]
;max circle inside polyline
;Stefan M. 26.07.2012
(defun C:TEST ( / space e l m c o r p offtype)
  (setq space (vlax-get (vla-get-ActiveDocument (vlax-get-acad-object)) (if (= (getvar 'cvport) 1) 'PaperSpace 'ModelSpace)))
  (setq offtype (getvar 'offsetgaptype))
  (setvar 'offsetgaptype 1)
  (if (setq e (ssget ":E:S:L" '((0 . "LWPOLYLINE"))))
     (progn
(setq e (vlax-ename->vla-object (ssname e 0))
      l (list (vla-copy e))
      m 0.0
)
(while l
   (foreach x l
      (if
(setq c (cond ((and
                                  (= (vlax-curve-GetEndParam x) 2.0)
                                  (or
                                    (vl-some 'zerop (mapcar '(lambda (a) (vla-getbulge x a)) '(0 1)))
                                    (<=
                                      (distance
                                        (vlax-curve-GetPointAtParam x 0.5)
                                        (vlax-curve-GetPointAtParam x 1.5)
                                        )
                                      (distance
                                        (vlax-curve-GetPointAtParam x 0.0)
                                        (vlax-curve-GetPointAtParam x 1.0)
                                        )
                                      )
                                    )
                                  )
(mapcar '(lambda (a b) (* 0.5 (+ a b)))
(vlax-curve-GetPointAtParam x 0.5)
(vlax-curve-GetPointAtParam x 1.5)
)
       )
       ((and
   (= (vlax-curve-GetEndParam x) 3.0)
                                   (vlax-curve-IsClosed x)
   (vl-every 'zerop (mapcar '(lambda (a) (vla-getbulge x a)) '(0 1 2)))
)
(incircle x)
       )
                               ((and
   (= (vlax-curve-GetEndParam x) 4.0)
                                   (equal '(0. 0. 0.) (mapcar '+ (vlax-curve-GetFirstDeriv x 0.5) (vlax-curve-GetFirstDeriv x 2.5)) 1e-8)
   (equal '(0. 0. 0.) (mapcar '+ (vlax-curve-GetFirstDeriv x 1.5) (vlax-curve-GetFirstDeriv x 3.5)) 1e-8)
)
                                (median x)
                                )
       ((< (vla-get-area x) 1e-7) (median x))
)
)
(if
    (equal (setq r (distance c (vlax-curve-GetClosestPointTo e c))) m 1e-8)
    (setq p (cons (list c r) p))
    (if (> r m) (setq p (list (list c r)) m r))
)
(setq o (append (offset_in x) o))
      )
      (vla-delete x)
   )
   (setq l o o nil)
)
(foreach x p (vla-put-Color (vla-AddCircle space (vlax-3D-point (car x)) (cadr x)) acRed))
     )
  )
  (setvar 'offsetgaptype offtype)
  (princ)
)

(defun incircle (e / a b c p pt)
  (setq a (vlax-curve-GetDistAtParam e 1)
        b (- (vlax-curve-GetDistAtParam e 2) a)
        c (- (setq p (vlax-curve-GetDistAtParam e 3)) a b)
        pt (mapcar 'vlax-curve-GetPointAtParam (list e e e) '(2 3 1))
        )
  (mapcar
    '(lambda (x) (/ (apply '+ (mapcar '* (list a b c) x)) p))
    (list
      (mapcar 'car pt)
      (mapcar 'cadr pt)
      )
    )
  )

(defun median (e / i l n)
  (repeat
    (setq n (fix (setq i (vlax-curve-GetEndParam e))))
    (setq l (cons (vlax-curve-GetPointAtParam e (setq n (1- n))) l))
    )
  (mapcar
    '(lambda (x) (/ (apply '+ x) i))
    (list
      (mapcar 'car l)
      (mapcar 'cadr l)
      )
    )
  )

(defun offset_in (e / i)
   (setq i (/ (vla-get-Area e) (vla-get-Length e) 10.0))
   (apply
      'append
      (mapcar
         (function
            (lambda (x / o)
               (if
                  (not (vl-catch-all-error-p (setq o (vl-catch-all-apply 'vlax-invoke (list e 'Offset x)))))
                    (vl-remove-if
                       '(lambda (a)
                           (and
                              (or
                                 (> (vla-get-Area a) (vla-get-Area e))
                                 (> (vla-get-Length a) (vla-get-Length e))
                              )
                              (not (vla-delete a))
                           )
                        )
                       o
                    )
               )
            )
         )
         (list i (- i))
      )
   )
)

EDIT: fixed some bugs
« Last Edit: July 26, 2012, 08:16:03 AM by Stefan »

DEVITG

  • Bull Frog
  • Posts: 479
Re: =={challenge}==Find the maximum inscribed circle
« Reply #26 on: July 26, 2012, 11:56:31 PM »

For the 2 solution , amazing , outstanding

Thanks for such beatifull works.
Location @ Córdoba Argentina Using ACAD 2019  at Window 10

GP

  • Newt
  • Posts: 83
  • Vercelli, Italy
Re: =={challenge}==Find the maximum inscribed circle
« Reply #27 on: July 27, 2012, 03:34:05 AM »
Stefan,
great code!  :kewl:

highflyingbird

  • Bull Frog
  • Posts: 415
  • Later equals never.
Re: =={challenge}==Find the maximum inscribed circle
« Reply #28 on: July 27, 2012, 04:22:59 AM »
Stefan,Excellent!! 8-)
Both of you are geniuses!
I am a bilingualist,Chinese and Chinglish.

Stefan

  • Bull Frog
  • Posts: 319
  • The most I miss IRL is the Undo button
Re: =={challenge}==Find the maximum inscribed circle
« Reply #29 on: July 27, 2012, 05:17:25 AM »
Thank you guys!
It is working in most situations, but I found some when is giving a wrong result (see image 1)
Beside, there is an issue about what is "inside" and "outside" of a pline. (see img2)

P.S. How to embed an image into a post?  :oops:
« Last Edit: July 27, 2012, 06:39:34 AM by Stefan »