Path: utzoo!utgpu!watmath!att!ucbvax!hplabs!hpfcdc!hpldola!myers
From: myers@hpldola.HP.COM (Dan Myers)
Newsgroups: comp.graphics
Subject: Re: Circle algorithms
Message-ID: <11390021@hpldola.HP.COM>
Date: 4 Aug 89 17:04:12 GMT
References: <3417@wpi.wpi.edu>
Organization: HP Elec. Design Div. -ColoSpgs
Lines: 43

Jeffrey T LeBlanc writes:

>     Does anyone out there have an algorithm handy that, when given the
>coordinates of three XY points can return the circle that would fall on
>them?  Any help along those lines would be appreciated.


This is pretty off-the-cuff, but is based on the fact that the distance
from any point on the perpendicular bisector of a line segment is
equidistant from the original segments endpoints:

	Given:  3 points A, B, and C (in XY coords)
	Algorithm:
	        If any of A,B,or C are duplicates, return the circle
		centered on the midpoint of the segment joining the two 
		distinct endpoints with radius equal to 1/2 their distance.

		Determine the equations for the perpendicular 
		bisectors of any TWO pairs of points( say AB and BC ).
		Call them perpAB and perpBC.
		
		If slope(perpAB) equals slope( perpBC ), return an
		"infinite" circle (i.e., the line passing through all
		points since they are collinear)
		
		Find the intersection of perpAB and perpBC (guaranteed
		exist since we made it past the last step...).  Call it
		centerpoint.
		
		Return the circle with center centerpoint and radius
		equal to the distance from centerpoint to ANY of the 
		given points (e.g. distance(centerpoint, A) ).
		
		Details are left as an exercise to the reader :^)
		
		
	Hope this helps...
	
	
	Dan Myers
	hplabs.hp.com!hpldola!myers