Determine the circumcircle of a set of points
This function returns the (smallest) circumcircle of a set of n points
circumcircle(x, y = NULL, num.touch=2, plot = FALSE, debug = FALSE)
x |
vector containing x coordinates of the data. If |
y |
vector containing y coordinates of the data. |
num.touch |
How often should the resulting circle touch the convex hull of the given points? default: 2 possible values: 2 or 3 Note: The circumcircle of a triangle is usually defined to touch
at 3 points, this function searches by default the minimum circle,
which may be only touching at 2 points. Set parameter
|
plot |
Logical, produce a simple plot of the result. default: |
debug |
Logical, more plots, only needed for debugging. default: |
This is a (naive implemented) algorithm which determines the smallest circumcircle of n points:
First step: Take the convex hull.
Second step: Determine two points on the convex hull with maximum distance for the diameter of the set.
Third step: Check if the circumcircle of these two points already contains all other points (of the convex hull and hence all other points).
If not or if 3 or more touching points are desired
(num.touch=3),
search a point with minimum enclosing circumcircle among the
remaining points of the convex hull.
If such a point cannot be found (e.g. for data(circtest2)),
search the remaining triangle combinations of points from the convex
hull until an enclosing circle with minimum radius is found.
The last search uses an upper and lower bound for the desired miniumum radius:
Any enclosing rectangle and its circumcircle gives an upper bound (the axis-parallel rectangle is used).
Half the diameter of the set from step 1 is a lower bound.
x |
'x' coordinate of circumcircle center |
y |
'y' coordinate of circumcircle center |
radius |
radius of circumcircle |
Albrecht Gebhardt
data(circtest) # smallest circle: circumcircle(circtest,num.touch=2,plot=TRUE) # smallest circle with maximum touching points (3): circumcircle(circtest,num.touch=3,plot=TRUE) # some stress test for this function, data(circtest2) # circtest2 was generated by: # 100 random points almost one a circle: # alpha <- runif(100,0,2*pi) # x <- cos(alpha) # y <- sin(alpha) # circtest2<-list(x=cos(alpha)+runif(100,0,0.1), # y=sin(alpha)+runif(100,0,0.1)) # circumcircle(circtest2,plot=TRUE)
Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.