|
|
Available Now
Search
Contact
Feedback:
Send an e-mail with your
comments about this program (or anything else).
Help support DFF
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.
|
| |
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.)
Elzinga-Hearn Algorithm
-
Choose any two points, Pi and Pj
-
Construct the circle whose center is at the midpoint of
the line connecting Pi and Pj
and which passes through Pi and Pj.
If this circle contains all points, then the center of the circle is the
optimal X. Otherwise, choose a point Pk outside the circle.
-
If the triangle determined by Pi,
Pj and Pk is a right triangle or an obtuse triangle, rename the two points
opposite the right angle or the obtuse angle as Pi and
Pj
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 Pl not in the circle, and let Q be
the point among {Pi, Pj, Pk} 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 {Pi, Pj, Pk} that is in the half plane
opposite Pl. With the points Q, R, and Pl, 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 Elzinga-Hearn. My
# 5 assumes
that the smallest circle containing all points will go through 3 points.
So we just try all possible 3-point 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 Elzinga-Hearn) 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 co-linear,
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 co-linear 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 co-linear 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 Elzinga-Hearn algorithm for a
set of three points which happen to be collinear. The answer is
to treat them 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.
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 3-dimensional versions to consider.
The smallest sphere that would enclose our solar system (or our galaxy)
for example. |
| Created: November 11, 2001 |
Revised:
July 21, 2006 |
|
