Finding smallest circle that encloses n points.

Follow up to Rosetta Code task-Total circles area.

Given a selection of points as Cartesian x,y coordinates, find the smallest circle that can contain them all.

One point is enclosed of course by a circle of radius zero!

Two points will be at opposite ends of a diameter.

Three points define a unique circle.

Four or more points MAY be three on the rim and the rest inside, but in theory an infinite number of points could lie exactly on one circle!

I store the coordinates in a string array, with x and y values and a comma separator. Search for max and min values, which means a maximum circle radius can be determined.

A guaranteed method is to take the points three at a time in all possible combinations ( 1 and 2-point cases are trivial) and see if the resulting circles include all the others. Boring but straightforward.

Attempted Monte-Carlo approximation.

Mouse clicks are now used to enter your chosen points. I originally generated the points with random coordinates. By using randomize command I could repeatedly test a particular data set. However mouse-clicking allows easy entry of interestingly-spaced situations. A superposed grid allows more accurate positioning of data points. And the bounding box is displayed once calculated.

I draw the successive attempts, changing colour when the first point is reached, or very close. At the end of a suitable time, I redraw, showing just the points and the grid.

I start with a circle suitably 'centred' and of radius big enough to include all the points within itself. I then progressively shrink it until it touches one of the further-out points. I then dither the centre to see if better approximations can be made, stopping on encountering a second. The intention is to continue this to all possible points.

Examples of the present form of data entry, calculation and results.

LB Code

Code, as a zip file, will be linked soon. I still want to significantly improve it!