Determine the circumcircle of a set of points

This function returns the (smallest) circumcircle of a set of n points

Usage

circumcircle(x, y = NULL, num.touch=2, plot = FALSE, debug = FALSE)

Arguments

x

vector containing x coordinates of the data. If y is missing x should contain two elements $x and $y.

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 num.touch accordingly if you dont want the default behaviour!

plot

Logical, produce a simple plot of the result.

default: FALSE

debug

Logical, more plots, only needed for debugging.

default: FALSE

Details

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.

Value

x: 'x' coordinate of circumcircle center
y: 'y' coordinate of circumcircle center
radius: radius of circumcircle

Author

Albrecht Gebhardt

Examples

 data(circtest)
 # smallest circle:
 circumcircle(circtest,num.touch=2,plot=TRUE)

#> $x
#> [1] -0.3085279
#> 
#> $y
#> [1] -0.3116673
#> 
#> $radius
#> [1] 3.043886
#> 

 # smallest circle with maximum touching points (3):
 circumcircle(circtest,num.touch=3,plot=TRUE)

#> $x
#> [1] 0.3667301
#> 
#> $y
#> [1] -1.845474
#> 
#> $radius
#> [1] 3.474734
#> 

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

#> $x
#> [1] 0.05383896
#> 
#> $y
#> [1] 0.03794901
#> 
#> $radius
#> [1] 1.049089
#>