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

0 Members and 1 Guest are viewing this topic.

highflyingbird

  • Bull Frog
  • Posts: 414
  • Later equals never.
=={challenge}==Find the maximum inscribed circle
« on: July 22, 2012, 01:56:09 PM »
Is there an simple algorithm for calculating maximum inscribed circle into a convex polygon (even a curve)?
It's  also called MIC problem.
See here.

I wrote a routine,but it's very slow and it's  wrong sometimes.
I will post my lisp code later.
« Last Edit: July 22, 2012, 11:09:13 PM by HighflyingBird »
I am a bilingualist,Chinese and Chinglish.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1540
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #1 on: July 23, 2012, 01:56:02 AM »
I'm sorry. It is challenging and I can not spend as much time to solve it.

On the solution of this problem have to spend two days. On the qualitative solution - Week...
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1540
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #2 on: July 23, 2012, 02:03:55 AM »
I was faced with similar challenges.
At various times I used the three algorithms
1. analysis of the geometry of the bounding segments (perpendicular, the centers of arcs, etc).
2. approximation of the internal space of the pixels and finding the greatest area filled with pixels.
3. method of inflating the bubble.

was the most efficient region filling in squares, and further analysis of the internal squares as pixels, as points.
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

highflyingbird

  • Bull Frog
  • Posts: 414
  • Later equals never.
Re: =={challenge}==Find the maximum inscribed circle
« Reply #3 on: July 23, 2012, 06:19:27 AM »
I was faced with similar challenges.
At various times I used the three algorithms
1. analysis of the geometry of the bounding segments (perpendicular, the centers of arcs, etc).
2. approximation of the internal space of the pixels and finding the greatest area filled with pixels.
3. method of inflating the bubble.

was the most efficient region filling in squares, and further analysis of the internal squares as pixels, as points.
ElpanovEvgeniy,thank you!
I am a bilingualist,Chinese and Chinglish.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1540
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #4 on: July 23, 2012, 10:57:42 AM »
ElpanovEvgeniy,thank you!

thanks for that I will not participate in the contest...
Do I understand correctly?  :-D :-D :-D
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

highflyingbird

  • Bull Frog
  • Posts: 414
  • Later equals never.
Re: =={challenge}==Find the maximum inscribed circle
« Reply #5 on: July 23, 2012, 11:37:30 AM »
ElpanovEvgeniy,thank you!

thanks for that I will not participate in the contest...
Do I understand correctly?  :-D :-D :-D

No, my thanks for your good idea indeed,sometimes your idea helped me a lot.
maybe it's really  hard problem,but some genius  will solve it.who knows? :lmao:
I am a bilingualist,Chinese and Chinglish.

GP

  • Newt
  • Posts: 82
  • Vercelli, Italy
Re: =={challenge}==Find the maximum inscribed circle
« Reply #6 on: July 23, 2012, 06:16:27 PM »
You can approximate?  :-)

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)
    (prompt "\nSelect Polyline: ")
    (if (setq POLY (ssname (ssget ":S" '((0 . "LWPOLYLINE"))) 0))
        (progn
            (setq i 1 timer (date2sec))
            (setq step1 60) ;--> grid_1
            (setq step2 20) ;--> 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 3
                (grid_2)
                (Point_center)
            )
            (entmake
                (list
                    (cons 0 "CIRCLE")
                    (cons 8 (getvar "clayer"))
                    (cons 10 P_center)
                    (cons 40 dist)
                )
            )
            (setq endtimer (date2sec))
            (princ (strcat "time = "(rtos (- endtimer timer) 2 3) " seconds")) 
            (princ)
        )
    )
)


;; LWPolyline to Point List  -  Lee Mac
;; Returns a list of points describing the supplied LWPolyline
(defun LM:LWPoly->List ( ent / der di1 di2 inc lst par rad )
    (setq par 0)
    (repeat (cdr (assoc 90 (entget ent)))
        (if (setq der (vlax-curve-getsecondderiv ent par))
            (if (equal der '(0.0 0.0 0.0) 1e-8)
                (setq lst (cons (vlax-curve-getpointatparam ent par) lst))
                (if
                    (setq rad (distance '(0.0 0.0) (vlax-curve-getfirstderiv ent par))
                          di1 (vlax-curve-getdistatparam ent par)
                          di2 (vlax-curve-getdistatparam ent (1+ par))
                    )
                    (progn
                        (setq inc (/ (- di2 di1) (1+ (fix (* 25 (/ (- di2 di1) rad (+ pi pi)))))))
                        (while (< di1 di2)
                            (setq lst (cons (vlax-curve-getpointatdist ent di1) lst)
                                  di1 (+ di1 inc)
                            )
                        )
                    )
                )
            )
        )
        (setq par (1+ par))
    )
    lst
)

; 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_ n P> )
    (vla-getboundingbox POLY_vl 'p1 'p2)
    (setq P1_ (vlax-safearray->list p1))
    (setq P2_ (vlax-safearray->list p2))
    (setq P1_ (list (car P1_) (cadr P1_)))
    (setq P2_ (list (car P2_) (cadr P2_)))
    (setq Dx (/ (- (car P2_) (car P1_)) step1))
    (setq Dy (/ (- (cadr P2_) (cadr P1_)) step1))
    (setq n 0)
    (setq P> P1_)
    (setq Lp (list P1_))
    (repeat (* (1+ step1) step1)
        (setq P> (list (+ (car P>) Dx) (cadr P>)))
        (setq Lp (cons P> Lp))
        (setq n (1+ n))
        (if (= n step1)
            (progn
                (setq n 0)
                (setq P1_ (list (car P1_) (+ (cadr P1_) Dy)))
                (setq P> P1_)
                (setq Lp (cons P> Lp))
            )
        )
    )
    (setq Lp (cdr 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 (/ P_distant n Pr cont attr p# Pa Pa_ Pb )
    (setq P_distant (list (car (getvar "extmax")) (* 2 (cadr (getvar "extmax")))))   
    (setq list_p_int nil)
    (foreach Pr Lp
        (setq cont -1)
        (setq attr 0)
        (setq p# nil)
        (setq Pa (nth (setq cont (1+ cont)) list_vert_poly))
        (setq Pa_ Pa)
        (repeat (length list_vert_poly)
            (setq Pb (nth (setq cont (1+ cont)) list_vert_poly))
            (if (= cont (length list_vert_poly)) (setq Pb Pa_))
            (setq P# (inters Pa Pb Pr P_distant))
            (if (/= P# nil) (setq attr (1+ attr)))
            (setq Pa Pb)
        )
        (if (> (rem attr 2) 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 0.0000001)
    (setq P_center nil)
    (foreach Pa list_p_int
(setq Pvic (vlax-curve-getClosestPointTo POLY_vl Pa))
        (if (> (distance Pa Pvic) Dist)
            (progn
                (setq P_center Pa)
                (setq Dist (distance Pa Pvic))
            )
        )
    )
)


(defun date2sec ()
  (setq s (getvar "DATE"))
  (setq seconds (* 86400.0 (- s (fix s))))
)

(vl-load-com)
(princ)

highflyingbird

  • Bull Frog
  • Posts: 414
  • Later equals never.
Re: =={challenge}==Find the maximum inscribed circle
« Reply #7 on: July 23, 2012, 09:29:57 PM »
You can approximate?  :-)

Code: [Select]
...

Wonderful!!GP!thank you so much.
I will take some time to study your code.
I am a bilingualist,Chinese and Chinglish.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1540
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #8 on: July 24, 2012, 02:30:31 AM »
You can approximate?  :-)

good implementation of my algorithm!  :-)
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1540
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #9 on: July 24, 2012, 02:42:10 AM »
I'll talk about more than performance of the algorithm - a lot of simple calculations...

1. create a matrix of pixels inside the contour.
2. take a round brush (mathematics) and fill points inside
3. find the most shaded area - there must be a center.

example of the brush:
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
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1540
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #10 on: July 24, 2012, 02:50:24 AM »
example of the brush:

if the area of maximizing the numbers are very large, you can re-paint only to this area or use a larger brush at once, for large polyline.

just the algorithm is very good for finding the middle line - skilet for any shape, such as a tree.
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #11 on: July 24, 2012, 07:15:41 AM »
You can approximate?  :-)

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)
    (prompt "\nSelect Polyline: ")
    (if (setq POLY (ssname (ssget ":S" '((0 . "LWPOLYLINE"))) 0))
        (progn
            (setq i 1 timer (date2sec))
            (setq step1 60) ;--> grid_1
            (setq step2 20) ;--> 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 3
                (grid_2)
                (Point_center)
            )
            (entmake
                (list
                    (cons 0 "CIRCLE")
                    (cons 8 (getvar "clayer"))
                    (cons 10 P_center)
                    (cons 40 dist)
                )
            )
            (setq endtimer (date2sec))
            (princ (strcat "time = "(rtos (- endtimer timer) 2 3) " seconds")) 
            (princ)
        )
    )
)


;; LWPolyline to Point List  -  Lee Mac
;; Returns a list of points describing the supplied LWPolyline
(defun LM:LWPoly->List ( ent / der di1 di2 inc lst par rad )
    (setq par 0)
    (repeat (cdr (assoc 90 (entget ent)))
        (if (setq der (vlax-curve-getsecondderiv ent par))
            (if (equal der '(0.0 0.0 0.0) 1e-8)
                (setq lst (cons (vlax-curve-getpointatparam ent par) lst))
                (if
                    (setq rad (distance '(0.0 0.0) (vlax-curve-getfirstderiv ent par))
                          di1 (vlax-curve-getdistatparam ent par)
                          di2 (vlax-curve-getdistatparam ent (1+ par))
                    )
                    (progn
                        (setq inc (/ (- di2 di1) (1+ (fix (* 25 (/ (- di2 di1) rad (+ pi pi)))))))
                        (while (< di1 di2)
                            (setq lst (cons (vlax-curve-getpointatdist ent di1) lst)
                                  di1 (+ di1 inc)
                            )
                        )
                    )
                )
            )
        )
        (setq par (1+ par))
    )
    lst
)

; 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_ n P> )
    (vla-getboundingbox POLY_vl 'p1 'p2)
    (setq P1_ (vlax-safearray->list p1))
    (setq P2_ (vlax-safearray->list p2))
    (setq P1_ (list (car P1_) (cadr P1_)))
    (setq P2_ (list (car P2_) (cadr P2_)))
    (setq Dx (/ (- (car P2_) (car P1_)) step1))
    (setq Dy (/ (- (cadr P2_) (cadr P1_)) step1))
    (setq n 0)
    (setq P> P1_)
    (setq Lp (list P1_))
    (repeat (* (1+ step1) step1)
        (setq P> (list (+ (car P>) Dx) (cadr P>)))
        (setq Lp (cons P> Lp))
        (setq n (1+ n))
        (if (= n step1)
            (progn
                (setq n 0)
                (setq P1_ (list (car P1_) (+ (cadr P1_) Dy)))
                (setq P> P1_)
                (setq Lp (cons P> Lp))
            )
        )
    )
    (setq Lp (cdr 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 (/ P_distant n Pr cont attr p# Pa Pa_ Pb )
    (setq P_distant (list (car (getvar "extmax")) (* 2 (cadr (getvar "extmax")))))   
    (setq list_p_int nil)
    (foreach Pr Lp
        (setq cont -1)
        (setq attr 0)
        (setq p# nil)
        (setq Pa (nth (setq cont (1+ cont)) list_vert_poly))
        (setq Pa_ Pa)
        (repeat (length list_vert_poly)
            (setq Pb (nth (setq cont (1+ cont)) list_vert_poly))
            (if (= cont (length list_vert_poly)) (setq Pb Pa_))
            (setq P# (inters Pa Pb Pr P_distant))
            (if (/= P# nil) (setq attr (1+ attr)))
            (setq Pa Pb)
        )
        (if (> (rem attr 2) 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 0.0000001)
    (setq P_center nil)
    (foreach Pa list_p_int
(setq Pvic (vlax-curve-getClosestPointTo POLY_vl Pa))
        (if (> (distance Pa Pvic) Dist)
            (progn
                (setq P_center Pa)
                (setq Dist (distance Pa Pvic))
            )
        )
    )
)


(defun date2sec ()
  (setq s (getvar "DATE"))
  (setq seconds (* 86400.0 (- s (fix s))))
)

(vl-load-com)
(princ)
Great routine !
May need higher accuracy ?

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1540
  • Moscow (Russia)
Re: =={challenge}==Find the maximum inscribed circle
« Reply #12 on: July 24, 2012, 07:32:19 AM »
...
Great routine !
May need higher accuracy ?

replace
Code: [Select]
(repeat 3
  (grid_2)
  (Point_center)
)
for
Code: [Select]
(repeat 8
  (grid_2)
  (Point_center)
)
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

GP

  • Newt
  • Posts: 82
  • Vercelli, Italy
Re: =={challenge}==Find the maximum inscribed circle
« Reply #13 on: July 24, 2012, 02:26:22 PM »
Thanks to all.  :-)
This was the request in my thread here:

I try to explain how it works:

(grid_1)
Calculation of the grid points within the getboundingbox of poly,
Subdivision = (step1 x step1)
Increase the value of step1 for greater certainty of outcome
I think step1 = 60 a good relationship time/accuracy

(Point_int)
Calculation of internal points on the polyline

(grid+)
Increase the density of the grid points (only internal).

(Point_center)
Calculation of the farthest point from the polyline
   
(grid_2)
Calculation of a new (dense) grid of points around the center provisionally calculated


The result is approximated.
Perhaps for the exact solution:
1.Construct the Voronoi Diagram of the edges in P. This can be done with, for example, Fortunes algorithm;
2.For Voronoi nodes (points equidistant to three or more edges) inside P;
3.Find the node with the maximum distance to edges in P. This node is the centre of the maximum inscribed circle.


http://stackoverflow.com/questions/4279478/maximum-circle-inside-a-non-convex-polygon
Voronoi Diagram
Fortunes algorithm

Ciao

« Last Edit: July 24, 2012, 02:29:23 PM by GP »

chlh_jd

  • Guest
Re: =={challenge}==Find the maximum inscribed circle
« Reply #14 on: July 25, 2012, 02:12:35 AM »
replace
Code: [Select]
(repeat 3
  (grid_2)
  (Point_center)
)
for
Code: [Select]
(repeat 8
  (grid_2)
  (Point_center)
)
Thanks ElpanovEvgeniy.
I've test 'repeat 8 ... , it take the same result .