Geometry Problem - Programmers Heaven

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# Geometry Problem

Posts: 1Member
Hi!..
I have a fixed rectangle with different radius circles in it, which do not intersect! The problem is about finding the largest area circle that can be put in the rectangle without intersecting the others circles.
If you know an algorithm to this problem, or you have any idea how to solve this mathematicaly, please send me a message.

• Posts: 1Member
sounds like a 'voronoi diagram' problem.

• Posts: 748Member
: Hi!..
: I have a fixed rectangle with different radius circles in it, which do not intersect! The problem is about finding the largest area circle that can be put in the rectangle without intersecting the others circles.
: If you know an algorithm to this problem, or you have any idea how to solve this mathematicaly, please send me a message.
:

One way you could do this is create a bitmap of the picture in an array using zero's and 1's and find the largest distance between the "virtual pixels" in both dimensions by doing a loop-within a loop for X and Y directions testing each dimension for boundaries.

If the rectangle is empty of course the result is the shorter dimension length.

I know an algorithim to plot a circle in BASIC so relate the dots this produces to X,Y pixels.

10 Pi=355/113
20 R=50
30 X=50
40 Y=50
60 Rem R is the radius - X and Y are the circle's centre
70 For A=0 to 2*Pi step 0.05
80 x1=R+sin(A)+x
90 y1=R*cos(A)+y
100 PLOT(x1,y1,c) : Rem where c is a colour value - in some BASICs PLOT is PSET

110 Next A

If your computer uses DEGREES instead of RADIANS change line 70 to>

70 For a=0 to 360 step 0.25

Reduce the step value to get the appearance of a complete circle or use the LINE to syntax to draw from the last point plotted.

Hope some of this helps. :-)