A very interesting q. Following is just a hunch :

1 Choose the largest 3 sides(lines ) which would

ensure the biggest possible triangle.

2. Open this triangle at each vertex successively and

close it with the largest side from the remaining lines .

3. Check for max area that meets 2.

4.Proceed till all lines are exhausted.

As a check, suppose we have N lines, the circle may lie between regular polygons (equal angles) formed by N equal largest side ,

and a similar polygon with N smallest side.

Cheers

You can start off with a small circle somewhere within the polygon (easy if it's convex, do you care about concave as well?). Then you can use some optimiser that plays around with the radius and the XY coordinates of the centre, and maximise the area while constraining the distance the circle is "sticking out" below or equal to 0. It's not difficult to check if a circle moves past any individual lines. This is obviously a numerical solution not a precise mathematical, with all the drawbacks, such as you can never guarantee the global optimum, you get the solution within the desired tolerance and such. I think this problem could be done in excel using the solver plugin.

And then when that works, as intended you can add additional variables to the optimiser, eg the angles between the sides, and see what happens.

Hi, thank you for your responses I have to clarify: I don’t have a polygon, I have a polygon chain, so is not only a problem of finding the biggest circle inside a polygon but also the distribution of angles that allow it to happen (that means the result will be convex but the shape is part of the question)

Ok, I've thought you already got some form of polygonal shape defined. Then you have 3 subtasks in my opinion:

1) Assemble any fixed polygon from the given edges

2) Find the largest circle in the fixed polygon

3) Optimize for angles while looking for the largest circle

I've written down how would I do 2 and 3, for nr 1 I don't have an immediate solution, maybe chain up the lines in a straight line, and let an optimiser change the angles. It might need some logic to determine if its possible to create a polygon at all, not sure...

hi

Please consider following :

1. Let us try with circumscribed circle of radius R

2. Let there be N lines L1 , L2...

3. Then we obtain R from

N*Pi = asin(L1/2R)+asin(L2/R) +..........asin(LN/R)

4 Check with N=4 and L1=L2=L3+L4 =L say

L/2R = sin(Pi/4) = .707

R = L/.707

5 For inscribed circle we may use atan

6. Not sure if solution always feasible but we can consider

adding Lk+Lj etc to reduce and try for some solution.

Cheers

Here is a paper I thought might be helpful for you problem.

Weller, Rene, and Gabriel Zachmann. "Inner sphere trees for proximity and penetration queries." Robotics: science and systems. Vol. 2. 2009.

The idea behind it is that generate "distance field" for every edges of the polygon one by one, and find the position where the maximum value of distance field locates. The position will be the center, the maximum value will be the radius of the inscribed circle.

Hope it could help your problem.

A possible procedure for maximum circumscribed circle (easily extended to inscribed circle) is as follow:

1. Add up L1+L2+...Ln = Lt say

2. Start with R= Rapprox = Lt/( 2*pi)

3. Find angle alp1 = asin(L1/2R )

4. Next alp2 = asin(L2/2R) and alp= alp1+alp2

5. Repeat 4 with new Li

6. Check alp = pu? as i is incremented

7. Suitably correct R based on 6 .till i=N

Cheers

Hi, thanks for all of your replies, I have been busy for the past few weeks but this weekend I’m going to apply your advices and study the documentation you gave

It seems there is another solution with circumcenter outside

the polygon by equating sum of angles of all side -largest side

with angle of this largest side.:

asin(L1/2R)= asin(L2/2R)+asin(L3/2R) +..........asin(LN/2R)

with L1 = largest side.

Cheers

Hi, I forgot to write here that I solved it: for the first part, I found the configurarion that made it a cyclic polygon (which means Its area was maximized), then with a defined shape (edges and angles), using Voronoi diagrams I found the center of the inner circle and with it I computed its diameter, sorry for writting after so much time, another project took all my atention for the last months