Maximum circle inscribed in a closed polyline

Hi all,

i need to find, even approximately, the maximum circle inscribed in a closed polyline.

Does anyone know if it is possible in lisp?

Thanks.

This would be interesting. I attempted, but could only get the biggest possible circle within the polyline from the polyline's centroid.

Thanks for your interest, is an extremely difficult problem.

Any other ideas?

I think it can be done, are these closed polygon defined by n vertices?

I enclose a sample image.

A quote from someone who's askign the same question:

Irregular polygons are not thought of as having an incircle or even a center.

If you were to draw a polygon at random, it is unlikely that there is a circle that has every side as a tangent.

An exception is a 3-sided polygon (triangle). All triangles always have an incircle.

It can happen in reverse however.You can start with a circle and draw an irregular polygon around it as in the figure on the right.

This would be called a circumscribed polygon.

 

Some mathematicians consider the incircle to be the largest circle that will fit inside a polygon,

without the requirement that it touches all the sides. Clearly,

under this definition, it is always possible to draw such a circle.

 

Not very re-assuring isint it?

Is this the same case as yours?

EDIT: I didnt see you post, let me ponder on that.....

It's the same case..

"...consider the incircle to be the largest circle that will fit inside a polygon,

without the requirement that it touches all the sides. Clearly,

under this definition, it is always possible to draw such a circle. "

A) For each vertex:

... 1) Draw circles between the current vertex and every two other vertices.

....... (making 2-element groups out of all other vertices required.)

... 2) Filter out circles intersecting other elements.

... 3) Save one circle with biggest radius.

... 4) Draw circles between the current vertex and "tan" to other two elements.

... 5) Repeat step 2.

... 6) Repeat step 3.

B) For each element:

... 7) Draw circles with "tan, tan, tan" method between current element and two other elements.

... Repeat step 2.

... 9) Repeat step 3.

Now find the largest circle between gotten objects out of above steps.

P.S. means 8 )

This reminds me of this problem...

fun fun fun

This reminds me of this problem...

 

fun fun fun

Lee, in that condition there are two useful restrictions:

1) It is obvious that circle is outside of the boundary.

2) Circle is inside the bounding box of the selected object(s).

... while here, try and error ways are more than your nice program's.

Lee, in that condition there are two useful restrictions:

 

1) It is obvious that circle is outside of the boundary.

2) Circle is inside the bounding box of the selected object(s).

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.

Thanks for the suggestions.

Lee, I try to take a look, but I think it will be difficult (for me) ...

As I expected it is very difficult for me to modify the Lee's code.

I followed another road, maybe not perfect but it solves my problem.

notes:

- Increase the value of step1 for greater certainty of outcome

- I think step1 = 60 a good relationship time/accuracy

- Function LM:LWPoly->List of lisp MinimumEnclosingCircle (Lee Mac) instead of my Vert_poly also describes the curves of the polylines, if inserted in lisp you can also check with curves polyline.

Finally, sorry for my English.

(defun C:TEST (/ Dx Dy Lp List_vert_poly list_p_int P_center dist)

   (prompt "\nSelect Polyline: ")
   (setq POLY_vl (vlax-ename->vla-object (ssname (ssget ":S" '((0 . "POLYLINE,LWPOLYLINE"))) 0)))
   (Vert_poly) 
   (grid_1)   
   (Point_int)  
   (Point_center)
   (repeat 3
       (grid_2) 
       (Point_center)
   )

   (entmake
       (list
           (cons 0 "CIRCLE")
           (cons 8 (getvar "clayer"))
           (cons 10 P_center)
           (cons 40 dist)
       )
   )
   (princ)
)


; Returns a list of polyline vertices
(defun Vert_poly (/ n_par pt)
   (setq list_vert_poly nil)
   (setq n_par (fix (vlax-curve-getendparam POLY_vl)))
   (repeat n_par
       (setq pt (vlax-curve-getpointatparam POLY_vl (setq n_par (1- n_par))))
       (setq list_vert_poly (cons pt list_vert_poly))
       (if (/= (last pt) 0.0)
           (progn
           (alert (strcat "Invalid Object Selected"
                              "\nz-coordinate vertices not = 0.0"))
           (exit)
           )
       )
   )
)


; Returns a grid of points within the BoundingBox of the selected poly
(defun grid_1 (/ P1_ P2_ n P> step1)
   (setq step1 60)
   (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))
           )
       )
   )
)


; Returns a grid of dots around the center point (provisional)
(defun grid_2 (/ P1_ step2 P> n)
   (setq step2 30)
   (setq list_p_int nil)
   (setq P1_ (list (- (car P_center) Dx) (- (cadr P_center) Dy)))
   (setq Dx (/ (* 2 Dx) step2))
   (setq Dy (/ (* 2 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))
           )
       )
   )
)


; Returns the list of points inside the polyline
(defun Point_int (/ P_distant n Pr cont attr p# Pa Pa_ Pb )
   (setq P_distant (polar (car Lp) 0 10000000))
   (setq list_p_int nil)
   (repeat (setq n (length Lp))
       (setq Pr (nth (setq n (1- n)) 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)))     
   )
)


; Returns the farthest point from the polyline
(defun Point_center (/ Pa n Pvic)
   (setq Dist 0.0000001)
   (setq P_center nil)
   (repeat (setq n (length list_p_int))
       (setq Pa (nth (setq n (1- n)) 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))
           )
       )
   )
)

(vl-load-com)
(princ)

Nice GP_

Thanks pBe