Search
As of October, 2016, Embarcadero is offering a free release
of Delphi (Delphi
10.1 Berlin Starter Edition ). There
are a few restrictions, but it is a welcome step toward making
more programmers aware of the joys of Delphi. They do say
"Offer may be withdrawn at any time", so don't delay if you want
to check it out. Please use the
feedback
link to let me know if the link stops working.
Support DFF  Shop
If you shop at Amazon anyway, consider using
this link. We receive a few cents from each purchase.
Thanks.
Support DFF  Donate
If you benefit from the website, in terms of
knowledge, entertainment value, or something otherwise useful,
consider making a donation via PayPal to help defray the
costs. (No PayPal account necessary to donate via credit
card.) Transaction is secure.
Contact
Feedback:
Send an
email with your comments about this program (or anything else).

 
Problem Description
Here's a simple problem for you:
"Put some dots randomly on a piece of paper
and draw the smallest possible circle around them."
How hard can that be?
Background & Techniques
Fairly hard, as it turns out. The most quoted algorithm
for solving the problem is by professors Elzinga and Hearn who in 1972 published
a geometric algorithm for solving this problem and proved the correctness of the
algorithm. (D. Jack Elzinga, Donald W.
Hearn, "Geometrical Solutions for some minimax location problems,"
Transportation Science, 6, (1972), pp 379  394.)
ElzingaHearn Algorithm

Choose any two points, P_{i} and P_{j}

Construct the circle whose center is at the midpoint of
the line connecting P_{i} and P_{j}
and which passes through P_{i }and P_{j}.
If this circle contains all points, then the center of the circle is the
optimal X. Otherwise, choose a point P_{k} outside the circle.

If the triangle determined by P_{i},
P_{j} and P_{k} is a right triangle or an obtuse triangle, rename the two points
opposite the right angle or the obtuse angle as P_{i} and
P_{j}
and go to step 2. Otherwise, the three points determine an acute triangle.
Construct the circle passing through the three points. (The center is the
intersection of the perpendicular bisectors of two sides of the triangle.)
If the circle contains all the points, stop, else, go to 4.

Choose some point P_{l} not in the circle, and let Q be
the point among {P_{i}, P_{j}, P_{k}} that is greatest distance
from Pl. Extend the diameter (from the circle center) through the point Q into a line
that divides the plane into two half planes. Let the point R be the
point among {P_{i}, P_{j}, P_{k}} that is in the half plane
opposite P_{l}. With the points Q, R, and P_{l}, go to
step 3.
This procedure seemed a lot more complicated than
necessary, so I naively tried several other techniques  none of which worked very
well. I've left them all in the program and documented them there just to illustrate the problem
solving process. Actually my 5th technique does seem to
work ( I think I rediscovered the classical solution), it's just a lot slower than ElzingaHearn. My
# 5 assumes
that the smallest circle containing all points will go through 3 points.
So we just try all possible 3point subsets of our full set of points, find the
circle defined by each triplet, check to see if it encloses all of the
points and, if it does, save the one with the smallest
radius. We also (like ElzingaHearn) need to catch the exceptional case where the
diametrical circle defined though the two points furthest apart encloses
all the points. For example given a set of three points almost colinear,
the circle defined by those three points
will be much larger than necessary.
The program has a graphical interface  just click some random
points on the image area and view the results. Radio buttons let you choose
the algorithm to use and a Reset button clears the screen.
Some Geometric Routines
All of the testing here requires quite a bit of geometrical
processing so we include dozen or so geometric processing routines developed here or lifted from
other DFF programs. They may come in handy for future projects and
probably should be collected into a Geometry unit. Here's the list:
Three geometric types TRealPoint, TLine, and
TCircle:

procedure swap (var p1,p2:TRealPoint);
Swaps two points.

function
makerealpoint(x,y:extended):TRealpoint; Make a real point
from extended x and y. This is counterpart of Delphi's Point function.

function
Distance(p1,p2:TRealPoint):extended; Return the distance between
two points.

function
GetCenter(p1,p2,p3:TRealPoint; var center: TRealPoint):boolean; Calculate
the center of a circle given three points on its circumference.
Result is true is circle was found, result is false if circle could not be
calculated, either because points were colinear or duplicate points were
input.

function
GetRadius(p1,p2,p3:TRealPoint):single; Return the radius of
a circle given three points on its circumference. Not used here  if
you need the radius and the center, it's probably faster to call GetCenter,
then call Distance with the center and one of the points to get the
radius.

function
GetCircle(p1,p2,p3:TRealPoint; var circle: Tcircle):boolean;
Return a TCircle structure containing center and radius from three
input points. Calls GetCenter to get the center of the
circle. Result is true if a circle was found, result is false if
circle could not be calculated, either because points were colinear or
duplicate points were input.

function
GetAngle(p1,p2,p3:TRealPoint):extended; Return absolute
value of smaller angle between lines defined by three input points, p1, p2, p3
forming two line segments, p1:p2, and p2:p3.
function SameSide (L: TLine; p1,p2:TrealPoint):extended;
Determine where two points lie in relation to each other and a given
line segment extended, If on the same side, result>0. If
on opposite sides, result <0; If either or both points are on the line,
result=0.

function Intersect(L1,L2:
TLine):boolean; Return true if 2 line segments intersect,
i.e.
endpoints of each input line segment lie on opposite sides of the other line

function TForm1.IsAcute(p1,p2,p3:integer; Var q1,q2:integer):boolean;
Parameters p1, p2, p3, q1, and q2 in this case are index pointers
into an array of TRealPoint. In the generalized case the name
of the array would also be passed as a parameter. IsAcute
returns true if triangle defined by points p1,p2,p3 is acute (no angle greater than 90 degrees, pi/2 radians) and return 0 in q1 and q2. If it's not acute, the triangle is right or obtuse, return the
two acute angle points in q1 and q2.
Code Running Times
Finally, the timing code in the program uses QueryPerformanceCounter
and QueryPerformanceFrequency procedures to get microsecond timing resolution
for each algorithm.
500 lines of code put this program in the Intermediate category.
Addendum  January 30, 2004: A viewer with a real
application requested that the program accept a user input set of real valued
points and calculate the minimal covering circle for those
points. I posted that version today. I think the
changes are pretty straight forward, the most complex part was scaling the
points for plotting. The application, by the way, involves determining the
minimal hazardous area for simulations of military ordinance
"hits".
Addendum  April 13, 2006: A viewer wrote
with a question about how to apply the ElzingaHearn algorithm for a
set of three points which happen to be collinear. The answer is
to treat them as an extreme obtuse triangle with the angle = 180°
when returning to Step 2. In the process of checking it though,
I found a problem with the point scaling to draw the solution for this
case. So that's fixed along with what amounted to fairly major
rewrite to improve the way that files and inputting of data are
handled. All for the better I hope. Anyway,
Version 3.1 was posted today.
August 3, 2012: An actual application for the
program prompted a viewer to request greater accuracy when entering external
data points. Version 3.2 implements this easy change by
accepting and reporting "dot" locations to 3 decimal points. The
application measures the accuracy of a tool which "shoots" slug to puncture a
target object by determining the size of the circle which will just cover a
group of shots.
Running/Exploring the Program
Suggestions for Further Explorations
A Google search on "Elzinga Hearn" turns up
many hits
for further reading (for example  according to the Gainesville, Fla. Sun
newspaper, they both work at University of Southern Florida these days and got
9% raises the other day. They actually get paid for playing
with all this fun stuff. Way to go guys! )

There's
another version of the problem that requires covering by the minimum
number of circles of fixed size. Covering the dots with poker chips
or coins, for example. Might be interesting. 

How
about covering the dots with the minimum sized ellipse, square, rectangle,
etc? I guess size would be defined as minimum area in the
ellipse and rectangle cases. 

Then
of course, there's always the 3dimensional versions to consider.
The smallest sphere that would enclose our solar system (or our galaxy)
for example. 
Created: November 11, 2001 
Revised:
February 18, 2016 
