N circles with fixed position and radius inside the smalest possible circle

0
votes

The Problem:

Given n circles with radii r1 ... rn and positions p1 ... pn. The algorithm have to find radius and center of the circle with the smallest radius containing all n circles. Position and radius of circles are fixed, so they can't be moved.

Structure of circle can looks like this:

Circle{
   position: Vector2,
   radius: Float
}

Input values: [c1 ... cn] (c - circle)

Output value: c

Image examples:

enter image description here

enter image description here

enter image description here

enter image description here

My thoughts:

I can draw the smallest circle with contain n circles if I find distance of the farthest 2 points and put center on the half ot this line, but there is posibility that the distance beetwen other circles and the center of main circle is farther than half of distance between the farthest 2 points.

enter image description here

So, I use this knowledge to find the farthest distance beetwen the center of main circle and third circle. When the distance is further than radius of main circle I know I have to find a center of three circles.

The problem start there. How can I find it?

I was thinking about finding the largest triangle possible using this three circles and than center of this, but there is problem with finding points position of this triangle. I tied a lot of different methods, but I can't find the heart of the problem.

enter image description here

enter image description here

That's why I'm here for some tips or solution. Maybe my way of thinking is correct, but there is much better solution. I would like to find it with you :)

1
algorithmgeometry
There are tons of results if you search for "circle through three points", almost certainly including example implementations in your favourite programming language. The same goes for finding the outer tangent between two circles. – Mike 'Pomax' Kamermans
I know how to calculate circle throught three points. I am searching for the largest triangle through three circles. Screenshots shows solution for the problem. Just imagines that the bigest circle doesn't exist and you have to find it. To show the answer I use reversed method. I just draw big circle and inside it I put smaller circles, to show you what I'm looking for. Thanks to this I was able to show you the pink triangle. – Apsik
Right, so reduce your question: you just need one or two decent images. And just mention the bits that matter: what struct you're using is irrelevant if you want to know how to find the outer tangents that join up your circles, for example. – Mike 'Pomax' Kamermans
Look at Hbf's answer here – MBo

1 Answers

0
votes

it looks like you have to combine the smallest circle algorithm with the solution to the Apollonius' problem.