Circle Covering Points

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

 

Search

Search WWW

Search DelphiForFun.org

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.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa® 365 Puzzlers  Calendar 2017

Mensa® 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

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

Algorithm extracted from: http://www.eng.clemson.edu/~pmdrn/Dearing/location/minimax.pdf {no author information available}

  1. Choose any two points, Pi and Pj

  2. 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. 

  3. 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.

  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 TRealPointTLine, and TCircle:

bullet

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

bullet

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

bullet

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

bullet

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.

bullet

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. 

bullet

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.

bullet

function GetAngle(p1,p2,p3:TRealPoint):extendedReturn absolute value of smaller angle between lines defined by three input points, p1, p2, p3 forming two line segments, p1:p2, and p2:p3.  

bullet

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.

bullet

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 

bullet

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 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 

bulletDownload source
bulletDownload  executable

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:  May 15, 2018

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2018, Gary Darby    All rights reserved.