[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionHere'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 & TechniquesFairly 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. Elzinga-Hearn Algorithm
|
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. | |
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. |
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 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.
Download source | |
Download executable |
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: May 15, 2018 |
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |