Circles of given radius through two points: Difference between revisions
(Nimrod -> Nim) |
(Updated D entry) |
||
| Line 229: | Line 229: | ||
throw new ValueException("radius of zero"); |
throw new ValueException("radius of zero"); |
||
if (feqrel( |
if (feqrel(p1.x, p2.x) >= nBits && |
||
feqrel( |
feqrel(p1.y, p2.y) >= nBits) |
||
throw new ValueException("coincident points give" ~ |
throw new ValueException("coincident points give" ~ |
||
" infinite number of Circles"); |
" infinite number of Circles"); |
||
Revision as of 19:28, 27 February 2015
You are encouraged to solve this task according to the task description, using any language you may know.
Given two points on a plane and a radius, usually two circles of given radius can be drawn through the points.
- Exceptions
- r==0.0 should be treated as never describing circles (except in the case where the points are coincident).
- If the points are coincident then an infinite number of circles with the point on their circumference can be drawn, unless r==0.0 as well which then collapses the circles to a point.
- If the points form a diameter then return two identical circles or return a single circle, according to which is the most natural mechanism for the implementation language.
- If the points are too far apart then no circles can be drawn.
- Task detail
- Write a function/subroutine/method/... that takes two points and a radius and returns the two circles through those points, or some indication of special cases where two, possibly equal, circles cannot be returned.
- Show here the output for the following inputs:
p1 p2 r 0.1234, 0.9876 0.8765, 0.2345 2.0 0.0000, 2.0000 0.0000, 0.0000 1.0 0.1234, 0.9876 0.1234, 0.9876 2.0 0.1234, 0.9876 0.8765, 0.2345 0.5 0.1234, 0.9876 0.1234, 0.9876 0.0
- Ref
- Finding the Center of a Circle from 2 Points and Radius from Math forum @ Drexel
AutoHotkey
<lang AutoHotkey>CircleCenter(x1, y1, x2, y2, r){ d := sqrt((x2-x1)**2 + (y2-y1)**2) x3 := (x1+x2)/2 , y3 := (y1+y2)/2 cx1 := x3 + sqrt(r**2-(d/2)**2)*(y1-y2)/d , cy1:= y3 + sqrt(r**2-(d/2)**2)*(x2-x1)/d cx2 := x3 - sqrt(r**2-(d/2)**2)*(y1-y2)/d , cy2:= y3 - sqrt(r**2-(d/2)**2)*(x2-x1)/d if (d = 0) return "No circles can be drawn, points are identical" if (d = r*2) return "points are opposite ends of a diameter center = " cx1 "," cy1 if (d = r*2) return "points are too far" if (r <= 0) return "radius is not valid" if !(cx1 && cy1 && cx2 && cy2) return "no solution" return cx1 "," cy1 " & " cx2 "," cy2 }</lang> Examples:<lang AutoHotkey>data = ( 0.1234 0.9876 0.8765 0.2345 2.0 0.0000 2.0000 0.0000 0.0000 1.0 0.1234 0.9876 0.1234 0.9876 2.0 0.1234 0.9876 0.8765 0.2345 0.5 0.1234 0.9876 0.1234 0.9876 0.0 )
loop, parse, data, `n { obj := StrSplit(A_LoopField, " ") MsgBox, % CircleCenter(obj[1], obj[2], obj[3], obj[4], obj[5]) }</lang>
- Output:
0.1234 0.9876 0.8765 0.2345 2.0 > 1.863112,1.974212 & -0.863212,-0.752112 0.0000 2.0000 0.0000 0.0000 1.0 > points are opposite ends of a diameter center = 0.000000,1.000000 0.1234 0.9876 0.1234 0.9876 2.0 > No circles can be drawn, points are identical 0.1234 0.9876 0.8765 0.2345 0.5 > no solution 0.1234 0.9876 0.1234 0.9876 0.0 > No circles can be drawn, points are identical
BASIC
<lang freebasic>
Type Point
As Double x,y Declare Property length As Double
End Type
Property point.length As Double Return Sqr(x*x+y*y) End Property
Sub circles(p1 As Point,p2 As Point,radius As Double)
Print "Points ";"("&p1.x;","&p1.y;"),("&p2.x;","&p2.y;")";", Rad ";radius
Var ctr=Type<Point>((p1.x+p2.x)/2,(p1.y+p2.y)/2)
Var half=Type<Point>(p1.x-ctr.x,p1.y-ctr.y)
Var lenhalf=half.length
If radius<lenhalf Then Print "Can't solve":Print:Exit Sub
If lenhalf=0 Then Print "Points are the same":Print:Exit Sub
Var dist=Sqr(radius^2-lenhalf^2)/lenhalf
Var rot= Type<Point>(-dist*(p1.y-ctr.y) +ctr.x,dist*(p1.x-ctr.x) +ctr.y)
Print " -> Circle 1 ("&rot.x;","&rot.y;")"
rot= Type<Point>(-(rot.x-ctr.x) +ctr.x,-((rot.y-ctr.y)) +ctr.y)
Print" -> Circle 2 ("&rot.x;","&rot.y;")"
Print
End Sub
Dim As Point p1=(.1234,.9876),p2=(.8765,.2345)
circles(p1,p2,2)
p1=Type<Point>(0,2):p2=Type<Point>(0,0)
circles(p1,p2,1)
p1=Type<Point>(.1234,.9876):p2=p1
circles(p1,p2,2)
p1=Type<Point>(.1234,.9876):p2=Type<Point>(.8765,.2345)
circles(p1,p2,.5)
p1=Type<Point>(.1234,.9876):p2=p1
circles(p1,p2,0)
Sleep </lang>
- Output:
Points (0.1234,0.9876),(0.8765,0.2345), Rad 2 -> Circle 1 (-0.8632118016581893,-0.7521118016581889) -> Circle 2 (1.863111801658189,1.974211801658189) Points (0,2),(0,0), Rad 1 -> Circle 1 (0,1) -> Circle 2 (0,1) Points (0.1234,0.9876),(0.1234,0.9876), Rad 2 Points are the same Points (0.1234,0.9876),(0.8765,0.2345), Rad 0.5 Can't solve Points (0.1234,0.9876),(0.1234,0.9876), Rad 0 Points are the same
C
<lang C>
- include<stdio.h>
- include<math.h>
typedef struct{ double x,y; }point;
double distance(point p1,point p2) { return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); }
void findCircles(point p1,point p2,double radius) { double separation = distance(p1,p2),mirrorDistance;
if(separation == 0.0) { radius == 0.0 ? printf("\nNo circles can be drawn through (%.4f,%.4f)",p1.x,p1.y): printf("\nInfinitely many circles can be drawn through (%.4f,%.4f)",p1.x,p1.y); }
else if(separation == 2*radius) { printf("\nGiven points are opposite ends of a diameter of the circle with center (%.4f,%.4f) and radius %.4f",(p1.x+p2.x)/2,(p1.y+p2.y)/2,radius); }
else if(separation > 2*radius) { printf("\nGiven points are farther away from each other than a diameter of a circle with radius %.4f",radius); }
else { mirrorDistance =sqrt(pow(radius,2) - pow(separation/2,2));
printf("\nTwo circles are possible."); printf("\nCircle C1 with center (%.4f,%.4f), radius %.4f and Circle C2 with center (%.4f,%.4f), radius %.4f",(p1.x+p2.x)/2 + mirrorDistance*(p1.y-p2.y)/separation,(p1.y+p2.y)/2 + mirrorDistance*(p2.x-p1.x)/separation,radius,(p1.x+p2.x)/2 - mirrorDistance*(p1.y-p2.y)/separation,(p1.y+p2.y)/2 - mirrorDistance*(p2.x-p1.x)/separation,radius); } }
int main() { int i;
point cases[] = { {0.1234, 0.9876}, {0.8765, 0.2345}, {0.0000, 2.0000}, {0.0000, 0.0000}, {0.1234, 0.9876}, {0.1234, 0.9876}, {0.1234, 0.9876}, {0.8765, 0.2345}, {0.1234, 0.9876}, {0.1234, 0.9876} };
double radii[] = {2.0,1.0,2.0,0.5,0.0};
for(i=0;i<5;i++) { printf("\nCase %d)",i+1); findCircles(cases[2*i],cases[2*i+1],radii[i]); }
return 0; } </lang>
- test run:
Case 1) Two circles are possible. Circle C1 with center (1.8631,1.9742), radius 2.0000 and Circle C2 with center (-0.8632,-0.7521), radius 2.0000 Case 2) Given points are opposite ends of a diameter of the circle with center (0.0000,1.0000) and radius 1.0000 Case 3) Infinitely many circles can be drawn through (0.1234,0.9876) Case 4) Given points are farther away from each other than a diameter of a circle with radius 0.5000 Case 5) No circles can be drawn through (0.1234,0.9876)
D
<lang d>import std.stdio, std.typecons, std.math;
class ValueException : Exception {
this(string msg_) pure { super(msg_); }
}
struct V2 { double x, y; } struct Circle { double x, y, r; }
/**Following explanation at: http://mathforum.org/library/drmath/view/53027.html
- /
Tuple!(Circle, Circle) circlesFromTwoPointsAndRadius(in V2 p1, in V2 p2, in double r) pure in {
assert(r >= 0, "radius can't be negative");
} body {
enum nBits = 40;
if (r.abs < (1.0 / (2.0 ^^ nBits)))
throw new ValueException("radius of zero");
if (feqrel(p1.x, p2.x) >= nBits &&
feqrel(p1.y, p2.y) >= nBits)
throw new ValueException("coincident points give" ~
" infinite number of Circles");
// Delta between points. immutable d = V2(p2.x - p1.x, p2.y - p1.y);
// Distance between points.
immutable q = sqrt(d.x ^^ 2 + d.y ^^ 2);
if (q > 2.0 * r)
throw new ValueException("separation of points > diameter");
// Halfway point. immutable h = V2((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
// Distance along the mirror line. immutable dm = sqrt(r ^^ 2 - (q / 2) ^^ 2);
return typeof(return)(
Circle(h.x - dm * d.y / q, h.y + dm * d.x / q, r.abs),
Circle(h.x + dm * d.y / q, h.y - dm * d.x / q, r.abs));
}
void main() {
foreach (immutable t; [
tuple(V2(0.1234, 0.9876), V2(0.8765, 0.2345), 2.0),
tuple(V2(0.0000, 2.0000), V2(0.0000, 0.0000), 1.0),
tuple(V2(0.1234, 0.9876), V2(0.1234, 0.9876), 2.0),
tuple(V2(0.1234, 0.9876), V2(0.8765, 0.2345), 0.5),
tuple(V2(0.1234, 0.9876), V2(0.1234, 0.9876), 0.0)]) {
writefln("Through points:\n %s %s and radius %f\n" ~
"You can construct the following circles:", t[]);
try {
writefln(" %s\n %s\n",
circlesFromTwoPointsAndRadius(t[])[]);
} catch (ValueException v)
writefln(" ERROR: %s\n", v.msg);
}
}</lang>
- Output:
Through points: immutable(V2)(0.1234, 0.9876) immutable(V2)(0.8765, 0.2345) and radius 2.000000 You can construct the following circles: Circle(1.86311, 1.97421, 2) Circle(-0.863212, -0.752112, 2) Through points: immutable(V2)(0, 2) immutable(V2)(0, 0) and radius 1.000000 You can construct the following circles: Circle(0, 1, 1) Circle(0, 1, 1) Through points: immutable(V2)(0.1234, 0.9876) immutable(V2)(0.1234, 0.9876) and radius 2.000000 You can construct the following circles: ERROR: coincident points give infinite number of Circles Through points: immutable(V2)(0.1234, 0.9876) immutable(V2)(0.8765, 0.2345) and radius 0.500000 You can construct the following circles: ERROR: separation of points > diameter Through points: immutable(V2)(0.1234, 0.9876) immutable(V2)(0.1234, 0.9876) and radius 0.000000 You can construct the following circles: ERROR: radius of zero
ERRE
<lang> PROGRAM CIRCLES
! ! for rosettacode.org !
PROCEDURE CIRCLE_CENTER(X1,Y1,X2,Y2,R->MSG$)
LOCAL D,W,X3,Y3
D=SQR((X2-X1)^2+(Y2-Y1)^2)
IF D=0 THEN
MSG$="NO CIRCLES CAN BE DRAWN, POINTS ARE IDENTICAL"
EXIT PROCEDURE
END IF
X3=(X1+X2)/2 Y3=(Y1+Y2)/2
W=R^2-(D/2)^2
IF W<0 THEN
MSG$="NO SOLUTION"
EXIT PROCEDURE
END IF
CX1=X3+SQR(W)*(Y1-Y2)/D CY1=Y3+SQR(W)*(X2-X1)/D
CX2=X3-SQR(W)*(Y1-Y2)/D CY2=Y3-SQR(W)*(X2-X1)/D
IF D=R*2 THEN
MSG$="POINTS ARE OPPOSITE ENDS OF A DIAMETER CENTER = "+STR$(CX1)+","+STR$(CY1)
EXIT PROCEDURE
END IF
IF D>R*2 THEN
MSG$="POINTS ARE TOO FAR"
EXIT PROCEDURE
END IF
IF R<=0 THEN
MSG$="RADIUS IS NOT VALID"
EXIT PROCEDURE
END IF
MSG$=STR$(CX1)+","+STR$(CY1)+" & "+STR$(CX2)+","+STR$(CY2)
END PROCEDURE
BEGIN DATA(0.1234,0.9876,0.8765,0.2345,2.0) DATA(0.0000,2.0000,0.0000,0.0000,1.0) DATA(0.1234,0.9876,0.1234,0.9876,2.0) DATA(0.1234,0.9876,0.8765,0.2345,0.5) DATA(0.1234,0.9876,0.1234,0.9876,0.0)
FOR I%=1 TO 5 DO
READ(PX,PY,QX,QY,RADIUS) CIRCLE_CENTER(PX,PY,QX,QY,RADIUS->MSG$) PRINT(MSG$)
END FOR END PROGRAM </lang>
Fortran
<lang fortran> ! Implemented by Anant Dixit (Nov. 2014) program circles implicit none double precision :: P1(2), P2(2), R
P1 = (/0.1234d0, 0.9876d0/) P2 = (/0.8765d0,0.2345d0/) R = 2.0d0 call print_centers(P1,P2,R)
P1 = (/0.0d0, 2.0d0/) P2 = (/0.0d0,0.0d0/) R = 1.0d0 call print_centers(P1,P2,R)
P1 = (/0.1234d0, 0.9876d0/) P2 = (/0.1234d0, 0.9876d0/) R = 2.0d0 call print_centers(P1,P2,R)
P1 = (/0.1234d0, 0.9876d0/) P2 = (/0.8765d0, 0.2345d0/) R = 0.5d0 call print_centers(P1,P2,R)
P1 = (/0.1234d0, 0.9876d0/) P2 = (/0.1234d0, 0.9876d0/) R = 0.0d0 call print_centers(P1,P2,R) end program circles
subroutine print_centers(P1,P2,R) implicit none double precision :: P1(2), P2(2), R, Center(2,2) integer :: Res call test_inputs(P1,P2,R,Res) write(*,*) write(*,'(A10,F7.4,A1,F7.4)') 'Point1 : ', P1(1), ' ', P1(2) write(*,'(A10,F7.4,A1,F7.4)') 'Point2 : ', P2(1), ' ', P2(2) write(*,'(A10,F7.4)') 'Radius : ', R if(Res.eq.1) then
write(*,*) 'Same point because P1=P2 and r=0.'
elseif(Res.eq.2) then
write(*,*) 'No circles can be drawn because r=0.'
elseif(Res.eq.3) then
write(*,*) 'Infinite circles because P1=P2 for non-zero radius.'
elseif(Res.eq.4) then
write(*,*) 'No circles with given r can be drawn because points are far apart.'
elseif(Res.eq.0) then
call find_center(P1,P2,R,Center) if(Center(1,1).eq.Center(2,1) .and. Center(1,2).eq.Center(2,2)) then write(*,*) 'Points lie on the diameter. A single circle can be drawn.' write(*,'(A10,F7.4,A1,F7.4)') 'Center : ', Center(1,1), ' ', Center(1,2) else write(*,*) 'Two distinct circles found.' write(*,'(A10,F7.4,A1,F7.4)') 'Center1 : ', Center(1,1), ' ', Center(1,2) write(*,'(A10,F7.4,A1,F7.4)') 'Center2 : ', Center(2,1), ' ', Center(2,2) end if
elseif(Res.lt.0) then
write(*,*) 'Incorrect value for r.'
end if write(*,*) end subroutine print_centers
subroutine test_inputs(P1,P2,R,Res) implicit none double precision :: P1(2), P2(2), R, dist integer :: Res if(R.lt.0.0d0) then
Res = -1 return
elseif(R.eq.0.0d0 .and. P1(1).eq.P2(1) .and. P1(2).eq.P2(2)) then
Res = 1 return
elseif(R.eq.0.0d0) then
Res = 2 return
elseif(P1(1).eq.P2(1) .and. P1(2).eq.P2(2)) then
Res = 3 return
else
dist = sqrt( (P1(1)-P2(1))**2 + (P1(2)-P2(2))**2 ) if(dist.gt.2.0d0*R) then Res = 4 return else Res = 0 return end if
end if end subroutine test_inputs
subroutine find_center(P1,P2,R,Center) implicit none double precision :: P1(2), P2(2), MP(2), Center(2,2), R, dm MP = (P1+P2)/2.0d0 dm = sqrt( (P1(1)-P2(1))**2 + (P1(2)-P2(2))**2 )
Center(1,1) = MP(1) + sqrt(R**2 - (dm/2.0d0)**2)*(P2(2)-P1(2))/dm Center(1,2) = MP(2) + sqrt(R**2 - (dm/2.0d0)**2)*(P2(1)-P1(1))/dm
Center(2,1) = MP(1) - sqrt(R**2 - (dm/2.0d0)**2)*(P2(2)-P1(2))/dm Center(2,2) = MP(2) - sqrt(R**2 - (dm/2.0d0)**2)*(P2(1)-P1(1))/dm end subroutine find_center </lang>
- Output:
Point1 : 0.1234 0.9876 Point2 : 0.8765 0.2345 Radius : 2.0000 Two distinct circles found. Center1 : -0.8632 1.9742 Center2 : 1.8631 -0.7521 Point1 : 0.0000 2.0000 Point2 : 0.0000 0.0000 Radius : 1.0000 Points lie on the diameter. A single circle can be drawn. Center : 0.0000 1.0000 Point1 : 0.1234 0.9876 Point2 : 0.1234 0.9876 Radius : 2.0000 Infinite circles because P1=P2 for non-zero radius. Point1 : 0.1234 0.9876 Point2 : 0.8765 0.2345 Radius : 0.5000 No circles with given r can be drawn because points are far apart. Point1 : 0.1234 0.9876 Point2 : 0.1234 0.9876 Radius : 0.0000 Same point because P1=P2 and r=0.
Go
<lang go>package main
import (
"fmt" "math"
)
var (
Two = "Two circles." R0 = "R==0.0 does not describe circles." Co = "Coincident points describe an infinite number of circles." CoR0 = "Coincident points with r==0.0 describe a degenerate circle." Diam = "Points form a diameter and describe only a single circle." Far = "Points too far apart to form circles."
)
type point struct{ x, y float64 }
func circles(p1, p2 point, r float64) (c1, c2 point, Case string) {
if p1 == p2 {
if r == 0 {
return p1, p1, CoR0
}
Case = Co
return
}
if r == 0 {
return p1, p2, R0
}
dx := p2.x - p1.x
dy := p2.y - p1.y
q := math.Hypot(dx, dy)
if q > 2*r {
Case = Far
return
}
m := point{(p1.x + p2.x) / 2, (p1.y + p2.y) / 2}
if q == 2*r {
return m, m, Diam
}
d := math.Sqrt(r*r - q*q/4)
ox := d * dx / q
oy := d * dy / q
return point{m.x - oy, m.y + ox}, point{m.x + oy, m.y - ox}, Two
}
var td = []struct {
p1, p2 point r float64
}{
{point{0.1234, 0.9876}, point{0.8765, 0.2345}, 2.0},
{point{0.0000, 2.0000}, point{0.0000, 0.0000}, 1.0},
{point{0.1234, 0.9876}, point{0.1234, 0.9876}, 2.0},
{point{0.1234, 0.9876}, point{0.8765, 0.2345}, 0.5},
{point{0.1234, 0.9876}, point{0.1234, 0.9876}, 0.0},
}
func main() {
for _, tc := range td {
fmt.Println("p1: ", tc.p1)
fmt.Println("p2: ", tc.p2)
fmt.Println("r: ", tc.r)
c1, c2, Case := circles(tc.p1, tc.p2, tc.r)
fmt.Println(" ", Case)
switch Case {
case CoR0, Diam:
fmt.Println(" Center: ", c1)
case Two:
fmt.Println(" Center 1: ", c1)
fmt.Println(" Center 2: ", c2)
}
fmt.Println()
}
}</lang>
- Output:
p1: {0.1234 0.9876}
p2: {0.8765 0.2345}
r: 2
Two circles.
Center 1: {1.8631118016581891 1.974211801658189}
Center 2: {-0.8632118016581893 -0.752111801658189}
p1: {0 2}
p2: {0 0}
r: 1
Points form a diameter and describe only a single circle.
Center: {0 1}
p1: {0.1234 0.9876}
p2: {0.1234 0.9876}
r: 2
Coincident points describe an infinite number of circles.
p1: {0.1234 0.9876}
p2: {0.8765 0.2345}
r: 0.5
Points too far apart to form circles.
p1: {0.1234 0.9876}
p2: {0.1234 0.9876}
r: 0
Coincident points with r==0.0 describe a degenerate circle.
Center: {0.1234 0.9876}
Haskell
<lang Haskell>add (a, b) (x, y) = (a + x, b + y) sub (a, b) (x, y) = (a - x, b - y) magSqr (a, b) = (a ^^ 2) + (b ^^ 2) mag a = sqrt $ magSqr a mul (a, b) c = (a * c, b * c) div2 (a, b) c = (a / c, b / c) perp (a, b) = (negate b, a) norm a = a `div2` mag a
circlePoints :: (Ord a, Floating a) =>
(a, a) -> (a, a) -> a -> Maybe ((a, a), (a, a))
circlePoints p q radius
| radius == 0 = Nothing | p == q = Nothing | diameter < magPQ = Nothing | otherwise = Just (center1, center2) where diameter = radius * 2 pq = p `sub` q magPQ = mag pq midpoint = (p `add` q) `div2` 2 halfPQ = magPQ / 2 magMidC = sqrt . abs $ (radius ^^ 2) - (halfPQ ^^ 2) midC = (norm $ perp pq) `mul` magMidC center1 = midpoint `add` midC center2 = midpoint `sub` midC
uncurry3 f (a, b, c) = f a b c
main :: IO () main = mapM_ (print . uncurry3 circlePoints)
[((0.1234, 0.9876), (0.8765, 0.2345), 2), ((0 , 2 ), (0 , 0 ), 1), ((0.1234, 0.9876), (0.1234, 0.9876), 2), ((0.1234, 0.9876), (0.8765, 0.2345), 0.5), ((0.1234, 0.9876), (0.1234, 0.1234), 0)]</lang>
- Output:
Just ((-0.8632118016581896,-0.7521118016581892),(1.8631118016581893,1.974211801658189)) Just ((0.0,1.0),(0.0,1.0)) Nothing Nothing Nothing
Icon and Unicon
Works in both languages. <lang unicon>procedure main()
A := [ [0.1234, 0.9876, 0.8765, 0.2345, 2.0],
[0.0000, 2.0000, 0.0000, 0.0000, 1.0],
[0.1234, 0.9876, 0.1234, 0.9876, 2.0],
[0.1234, 0.9876, 0.9765, 0.2345, 0.5],
[0.1234, 0.9876, 0.1234, 0.9876, 0.0] ]
every write(cCenter!!A)
end
procedure cCenter(x1,y1, x2,y2, r)
if r <= 0 then return "Illegal radius"
r2 := r*2
d := ((x2-x1)^2 + (y2-y1)^2)^0.5
if d = 0 then return "Identical points, infinite number of circles"
if d > r2 then return "No circles possible"
z := (r^2-(d/2.0)^2)^0.5
x3 := (x1+x2)/2.0; y3 := (y1+y2)/2.0
cx1 := x3+z*(y1-y2)/d; cy1 := y3+z*(x2-x1)/d
cx2 := x3-z*(y1-y2)/d; cy2 := y3-z*(x2-x1)/d
if d = r2 then return "Single circle at ("||cx1||","||cy1||")"
return "("||cx1||","||cy1||") and ("||cx2||","||cy2||")"
end</lang>
- Output:
->cgr (1.863111801658189,1.974211801658189) and (-0.8632118016581896,-0.7521118016581892) Single circle at (0.0,1.0) Identical points, infinite number of circles No circles possible Illegal radius ->
J
2D computations are often easier using the complex plane. <lang J> [INPUT =: _5]\0.1234, 0.9876 0.8765, 0.2345 2.0 0.0000, 2.0000 0.0000, 0.0000 1.0 0.1234, 0.9876 0.1234, 0.9876 2.0 0.1234, 0.9876 0.8765, 0.2345 0.5 0.1234, 0.9876 0.1234, 0.9876 0.0
average =: +/ % #
circles =: verb define"1
'P0 P1 R' =. (j./"1)_2[\y NB. Use complex plane
C =. P0 average@:, P1
BAD =: ":@:+. C
SEPARATION =. P0 |@- P1
if. 0 = SEPARATION do.
if. 0 = R do. 'Degenerate point at ' , BAD
else. 'Any center at a distance ' , (":R) , ' from ' , BAD , ' works.'
end.
elseif. SEPARATION (> +:) R do. 'No solutions.'
elseif. SEPARATION (= +:) R do. 'Duplicate solutions with center at ' , BAD
elseif. 1 do.
ORTHOGONAL_DISTANCE =. R * 1 o. _2 o. R %~ | C - P0
UNIT =: P1 *@:- P0
OFFSETS =: ORTHOGONAL_DISTANCE * UNIT * j. _1 1
C +.@:+ OFFSETS
end.
)
('x0 y0 x1 y1 r' ; 'center'),(;circles)"1 INPUT
┌───────────────────────────────┬────────────────────────────────────────────────────┐ │x0 y0 x1 y1 r │center │ ├───────────────────────────────┼────────────────────────────────────────────────────┤ │0.1234 0.9876 0.8765 0.2345 2 │_0.863212 _0.752112 │ │ │ 1.86311 1.97421 │ ├───────────────────────────────┼────────────────────────────────────────────────────┤ │0 2 0 0 1 │Duplicate solutions with center at 0 1 │ ├───────────────────────────────┼────────────────────────────────────────────────────┤ │0.1234 0.9876 0.1234 0.9876 2 │Any center at a distance 2 from 0.1234 0.9876 works.│ ├───────────────────────────────┼────────────────────────────────────────────────────┤ │0.1234 0.9876 0.8765 0.2345 0.5│No solutions. │ ├───────────────────────────────┼────────────────────────────────────────────────────┤ │0.1234 0.9876 0.1234 0.9876 0 │Degenerate point at 0.1234 0.9876 │ └───────────────────────────────┴────────────────────────────────────────────────────┘ </lang>
Maxima
<lang Maxima>/* define helper function */ vabs(a):= sqrt(a.a); realp(e):=freeof(%i, e);
/* get a general solution */ sol: block(
[p1: [x1, y1], p2: [x2, y2], c: [x0, y0], eq], local(r), eq: [vabs(p1-c) = r, vabs(p2-c) = r], load(to_poly_solve), assume(r>0), args(to_poly_solve(eq, c, use_grobner = true)))$
/* use general solution for concrete case */ getsol(sol, x1, y1, x2, y2, r):=block([n, lsol],
if [x1, y1]=[x2, y2] then (
print("infinity many solutions"),
return('infmany)),
lsol: sublist(sol, 'realp),
n: length(lsol),
if n=0 then (
print("no solutions"),
[])
else if n=1 then (
print("single solution"),
lsol[1])
else if [assoc('x0, lsol[1]), assoc('y0, lsol[1])]=[assoc('x0, lsol[2]), assoc('y0, lsol[2])] then (
print("single solution"),
lsol[1])
else (
print("two solutions"),
lsol))$
/* [x1, y1, x2, y2, r] */ d[1]: [0.1234, 0.9876, 0.8765, 0.2345, 2]; d[2]: [0.0000, 2.0000, 0.0000, 0.0000, 1]; d[3]: [0, 0, 0, 1, 0.4]; d[4]: [0, 0, 0, 0, 0.4];
apply('getsol, cons(sol, d[1])); apply('getsol, cons(sol, d[2])); apply('getsol, cons(sol, d[3])); apply('getsol, cons(sol, d[4]));</lang>
- Output:
<lang>apply('getsol, cons(sol, d[1])); two solutions (%o9) [[x0 = 1.86311180165819, y0 = 1.974211801658189],
[x0 = - 0.86321180165819, y0 = - 0.75211180165819]]
(%i10) apply('getsol, cons(sol, d[2])); single solution (%o10) [x0 = 0.0, y0 = 1.0] (%i11) apply('getsol, cons(sol, d[3])); no solutions (%o11) [] (%i12) apply('getsol, cons(sol, d[4])); infinity many solutions (%o12) infmany</lang>
МК-61/52
<lang>П0 С/П П1 С/П П2 С/П П3 С/П П4 ИП2 ИП0 - x^2 ИП3 ИП1 - x^2 + КвКор П5 ИП0 ИП2 + 2 / П6 ИП1 ИП3 + 2 / П7 ИП4 x^2 ИП5 2 / x^2 - КвКор ИП5 / П8 ИП6 ИП1 ИП3 - ИП8 * П9 + ПA ИП6 ИП9 - ПC ИП7 ИП2 ИП0 - ИП8 * П9 + ПB ИП7 ИП9 - ПD ИП5 x#0 97 8 4 ИНВ С/П ИП4 2 * ИП5 - ПE x#0 97 ИПB ИПA 8 5 ИНВ С/П ИПE x>=0 97 8 3 ИНВ С/П ИПD ИПC ИПB ИПA С/П</lang>
- Input:
В/О x1 С/П y1 С/П x2 С/П y2 С/П radius С/П
- Output:
"8.L" if the points are coincident; "8.-" if the points are opposite ends of a diameter of the circle, РY and РZ are coordinates of the center; "8.Г" if the points are farther away from each other than a diameter of a circle; else РX, РY and РZ, РT are coordinates of the circles centers.
Nim
<lang nim>import math
type
Point = tuple[x, y: float] Circle = tuple[x, y, r: float]
proc circles(p1, p2: Point, r: float): tuple[c1, c2: Circle] =
if r == 0: raise newException(EInvalidValue, "radius of zero") if p1 == p2: raise newException(EInvalidValue, "coincident points gives infinite number of Circles")
# delta x, delta y between points let (dx, dy) = (p2.x - p1.x, p2.y - p1.y) # dist between points let q = sqrt(dx*dx + dy*dy) if q > 2.0*r: raise newException(EInvalidValue, "separation of points > diameter")
# halfway point let p3: Point = ((p1.x+p2.x)/2, (p1.y+p2.y)/2) # distance along the mirror line let d = sqrt(r*r - (q/2)*(q/2)) # One answer result.c1 = (p3.x - d*dy/q, p3.y + d*dx/q, abs(r)) # The other answer result.c2 = (p3.x + d*dy/q, p3.y - d*dx/q, abs(r))
const tries: seq[tuple[p1, p2: Point, r: float]] =
@[((0.1234, 0.9876), (0.8765, 0.2345), 2.0), ((0.0000, 2.0000), (0.0000, 0.0000), 1.0), ((0.1234, 0.9876), (0.1234, 0.9876), 2.0), ((0.1234, 0.9876), (0.8765, 0.2345), 0.5), ((0.1234, 0.9876), (0.1234, 0.9876), 0.0)]
for p1, p2, r in tries.items:
echo "Through points:" echo " ", p1 echo " ", p2 echo " and radius ", r echo "You can construct the following circles:" try: let (c1, c2) = circles(p1, p2, r) echo " ", c1 echo " ", c2 except EInvalidValue: echo " ERROR: ", getCurrentExceptionMsg() echo ""</lang>
- Output:
Through points: (x: 0.1234, y: 0.9876) (x: 0.8764999999999999, y: 0.2345) and radius 2.0 You can construct the following circles: (x: 1.863111801658189, y: 1.974211801658189, r: 2.0) (x: -0.8632118016581896, y: -0.7521118016581892, r: 2.0) Through points: (x: 0.0, y: 2.0) (x: 0.0, y: 0.0) and radius 1.0 You can construct the following circles: (x: 0.0, y: 1.0, r: 1.0) (x: 0.0, y: 1.0, r: 1.0) Through points: (x: 0.1234, y: 0.9876) (x: 0.1234, y: 0.9876) and radius 2.0 You can construct the following circles: ERROR: coincident points gives infinite number of Circles Through points: (x: 0.1234, y: 0.9876) (x: 0.8764999999999999, y: 0.2345) and radius 0.5 You can construct the following circles: ERROR: separation of points > diameter Through points: (x: 0.1234, y: 0.9876) (x: 0.1234, y: 0.9876) and radius 0.0 You can construct the following circles: ERROR: radius of zero
ooRexx
<lang oorexx>/*REXX pgm finds 2 circles with a specific radius given two (X,Y) points*/
a.= a.1=0.1234 0.9876 0.8765 0.2345 2 a.2=0.0000 2.0000 0.0000 0.0000 1 a.3=0.1234 0.9876 0.1234 0.9876 2 a.4=0.1234 0.9876 0.8765 0.2345 0.5 a.5=0.1234 0.9876 0.1234 0.9876 0
Say ' x1 y1 x2 y2 radius cir1x cir1y cir2x cir2y'
Say ' ------ ------ ------ ------ ------ ------ ------ ------ ------'
Do j=1 By 1 While a.j<>
Do k=1 For 4
w.k=f(word(a.j,k))
End
Say w.1 w.2 w.3 w.4 format(word(a.j,5),5,1) twocircles(a.j)
End
Exit
twocircles: Procedure
Parse Arg px py qx qy r . If r=0 Then Return ' radius of zero gives no circles.' x=(qx-px)/2 y=(qy-py)/2 bx=px+x by=py+y pb=rxCalcsqrt(x**2+y**2) If pb=0 Then Return ' coincident points give infinite circles' If pb>r Then Return ' points are too far apart for the given radius' cb=rxCalcsqrt(r**2-pb**2) x1=y*cb/pb y1=x*cb/pb Return f(bx-x1) f(by+y1) f(bx+x1) f(by-y1)
f: Return format(arg(1),2,4) /* format a number with 4 dec dig.*/
- requires 'rxMath' library</lang>
- Output:
x1 y1 x2 y2 radius cir1x cir1y cir2x cir2y ------ ------ ------ ------ ------ ------ ------ ------ ------ 0.1234 0.9876 0.8765 0.2345 2.0 1.8631 1.9742 -0.8632 -0.7521 0.0000 2.0000 0.0000 0.0000 1.0 0.0000 1.0000 0.0000 1.0000 0.1234 0.9876 0.1234 0.9876 2.0 coincident points give infinite circles 0.1234 0.9876 0.8765 0.2345 0.5 points are too far apart for the given radius 0.1234 0.9876 0.1234 0.9876 0.0 radius of zero gives no circles.
PARI/GP
<lang parigp>circ(a, b, r)={
if(a==b, return("impossible"));
my(h=(b-a)/2,t=sqrt(r^2-abs(h)^2)/abs(h)*h);
[a+h+t*I,a+h-t*I]
}; circ(0.1234 + 0.9876*I, 0.8765 + 0.2345*I, 2) circ(0.0000 + 2.0000*I, 0.0000 + 0.0000*I, 1) circ(0.1234 + 0.9876*I, 0.1234 + 0.9876*I, 2) circ(0.1234 + 0.9876*I, 0.8765 + 0.2345*I, .5) circ(0.1234 + 0.9876*I, 0.1234 + 0.9876*I, 0)</lang>
- Output:
%1 = [1.86311180 + 1.97421180*I, -0.863211802 - 0.752111802*I] %2 = [0.E-9 + 1.00000000*I, 0.E-9 + 1.00000000*I] %3 = "impossible" %4 = [0.370374144 + 0.740625856*I, 0.629525856 + 0.481474144*I] %5 = "impossible"
Perl 6
<lang Perl6>sub circles(@A, @B where (not [and] @A Z== @B), $radius where * > 0) {
my @middle = .5 X* (@A Z+ @B); my @diff = @A Z- @B; my @orth = -@diff[1], @diff[0] X/ 2 * tan asin 2*$radius R/ sqrt [+] @diff X**2;
return (@middle Z+ @orth).item, (@middle Z- @orth).item;
}
my @input = \([0.1234, 0.9876], [0.8765, 0.2345], 2.0), \([0.0000, 2.0000], [0.0000, 0.0000], 1.0), \([0.1234, 0.9876], [0.1234, 0.9876], 2.0), \([0.1234, 0.9876], [0.8765, 0.2345], 0.5), \([0.1234, 0.9876], [0.1234, 0.9876], 0.0),
for @input -> $input {
say $input.perl, ": ",
try { say join " and ", circles(|$input) }
}</lang>
- Output:
-0.863211801658189 -0.752111801658189 and 1.86311180165819 1.97421180165819 -6.12323399573677e-17 1 and 6.12323399573677e-17 1 NaN NaN and NaN NaN
Another possibility is to use the Complex plane, for it often makes calculations easier with plane geometry:
<lang perl6>sub circles($a, $b where $b != $a, $r) {
my $h = ($b - $a)/2;
my $l = sqrt($r**2 - $h.abs**2);
return map { $a + $h + $l * $_ * $h/$h.abs },
i, -i;
}
my @input = \(0.1234 + 0.9876i, 0.8765 + 0.2345i, 2.0), \(0.0000 + 2.0000i, 0.0000 + 0.0000i, 1.0), \(0.1234 + 0.9876i, 0.1234 + 0.9876i, 2.0), \(0.1234 + 0.9876i, 0.8765 + 0.2345i, 0.5), \(0.1234 + 0.9876i, 0.1234 + 0.9876i, 0.0),
- </lang>
PL/I
<lang PL/I>twoci: Proc Options(main);
Dcl 1 *(5),
2 m1x Dec Float Init(0.1234, 0,0.1234,0.1234,0.1234),
2 m1y Dec Float Init(0.9876, 2,0.9876,0.9876,0.9876),
2 m2x Dec Float Init(0.8765, 0,0.1234,0.8765,0.1234),
2 m2y Dec Float Init(0.2345, 0,0.9876,0.2345,0.9876),
2 r Dec Float Init( 2, 1, 2,0.5 , 0);
Dcl i Bin Fixed(31);
Put Edit(' x1 y1 x2 y2 r '||
' cir1x cir1y cir2x cir2y')(Skip,a);
Put Edit(' ====== ====== ====== ====== = '||
' ====== ====== ====== ======')(Skip,a);
Do i=1 To 5;
Put Edit(m1x(i),m1y(i),m2x(i),m2y(i),r(i))
(Skip,4(f(7,4)),f(3));
Put Edit(twocircles(m1x(i),m1y(i),m2x(i),m2y(i),r(i)))(a);
End;
twoCircles: proc(m1x,m1y,m2x,m2y,r) Returns(Char(50) Var);
Dcl (m1x,m1y,m2x,m2y,r) Dec Float;
Dcl (cx,cy,bx,by,pb,x,y,x1,y1) Dec Float;
Dcl res Char(50) Var;
If r=0 then return(' radius of zero gives no circles.');
x=(m2x-m1x)/2;
y=(m2y-m1y)/2;
bx=m1x+x;
by=m1y+y;
pb=sqrt(x**2+y**2);
cx=(m2x-m1x)/2;
cy=(m2y-m1y)/2;
bx=m1x+x;
by=m1y+y;
pb=sqrt(x**2+y**2)
if pb=0 then return(' coincident points give infinite circles');
if pb>r then return(' points are too far apart for the given radius');
cb=sqrt(r**2-pb**2);
x1=y*cb/pb;
y1=x*cb/pb
Put String(res) Edit((bx-x1),(by+y1),(bx+x1),(by-y1))(4(f(8,4)));
Return(res);
End;
End;</lang>
- Output:
x1 y1 x2 y2 r cir1x cir1y cir2x cir2y ====== ====== ====== ====== = ====== ====== ====== ====== 0.1234 0.9876 0.8765 0.2345 2 1.8631 1.9742 -0.8632 -0.7521 0.0000 2.0000 0.0000 0.0000 1 0.0000 1.0000 0.0000 1.0000 0.1234 0.9876 0.1234 0.9876 2 coincident points give infinite circles 0.1234 0.9876 0.8765 0.2345 1 points are too far apart for the given radius 0.1234 0.9876 0.1234 0.9876 0 radius of zero gives no circles.
Python
The function raises the ValueError exception for the special cases and uses try - except to catch these and extract the exception detail.
<lang python>from collections import namedtuple from math import sqrt
Pt = namedtuple('Pt', 'x, y') Circle = Cir = namedtuple('Circle', 'x, y, r')
def circles_from_p1p2r(p1, p2, r):
'Following explanation at http://mathforum.org/library/drmath/view/53027.html' if r == 0.0: raise ValueError('radius of zero') (x1, y1), (x2, y2) = p1, p2 if p1 == p2: raise ValueError('coincident points gives infinite number of Circles') # delta x, delta y between points dx, dy = x2 - x1, y2 - y1 # dist between points q = sqrt(dx**2 + dy**2) if q > 2.0*r: raise ValueError('separation of points > diameter') # halfway point x3, y3 = (x1+x2)/2, (y1+y2)/2 # distance along the mirror line d = sqrt(r**2-(q/2)**2) # One answer c1 = Cir(x = x3 - d*dy/q, y = y3 + d*dx/q, r = abs(r)) # The other answer c2 = Cir(x = x3 + d*dy/q, y = y3 - d*dx/q, r = abs(r)) return c1, c2
if __name__ == '__main__':
for p1, p2, r in [(Pt(0.1234, 0.9876), Pt(0.8765, 0.2345), 2.0),
(Pt(0.0000, 2.0000), Pt(0.0000, 0.0000), 1.0),
(Pt(0.1234, 0.9876), Pt(0.1234, 0.9876), 2.0),
(Pt(0.1234, 0.9876), Pt(0.8765, 0.2345), 0.5),
(Pt(0.1234, 0.9876), Pt(0.1234, 0.9876), 0.0)]:
print('Through points:\n %r,\n %r\n and radius %f\nYou can construct the following circles:'
% (p1, p2, r))
try:
print(' %r\n %r\n' % circles_from_p1p2r(p1, p2, r))
except ValueError as v:
print(' ERROR: %s\n' % (v.args[0],))</lang>
- Output:
Through points: Pt(x=0.1234, y=0.9876), Pt(x=0.8765, y=0.2345) and radius 2.000000 You can construct the following circles: Circle(x=1.8631118016581893, y=1.974211801658189, r=2.0) Circle(x=-0.8632118016581896, y=-0.7521118016581892, r=2.0) Through points: Pt(x=0.0, y=2.0), Pt(x=0.0, y=0.0) and radius 1.000000 You can construct the following circles: Circle(x=0.0, y=1.0, r=1.0) Circle(x=0.0, y=1.0, r=1.0) Through points: Pt(x=0.1234, y=0.9876), Pt(x=0.1234, y=0.9876) and radius 2.000000 You can construct the following circles: ERROR: coincident points gives infinite number of Circles Through points: Pt(x=0.1234, y=0.9876), Pt(x=0.8765, y=0.2345) and radius 0.500000 You can construct the following circles: ERROR: separation of points > diameter Through points: Pt(x=0.1234, y=0.9876), Pt(x=0.1234, y=0.9876) and radius 0.000000 You can construct the following circles: ERROR: radius of zero
Racket
Using library `plot/utils` for simple vector operations.
<lang racket>
- lang racket
(require plot/utils)
(define (circle-centers p1 p2 r)
(when (zero? r) (err "zero radius.")) (when (equal? p1 p2) (err "the points coinside.")) ; the midle point (define m (v/ (v+ p1 p2) 2)) ; the vector connecting given points (define d (v/ (v- p1 p2) 2)) ; the distance between the center of the circle and the middle point (define ξ (- (sqr r) (vmag^2 d))) (when (negative? ξ) (err "given radius is less then the distance between points.")) ; the unit vector orthogonal to the delta (define n (vnormalize (orth d))) ; the shift along the direction orthogonal to the delta (define x (v* n (sqrt ξ))) (values (v+ m x) (v- m x)))
- error message
(define (err m) (error "Impossible to build a circle:" m))
- returns a vector which is orthogonal to the geven one
(define orth (match-lambda [(vector x y) (vector y (- x))])) </lang>
- Testing:
> (circle-centers #(0.1234 0.9876) #(0.8765 0.2345) 2.0) '#(1.8631118016581893 1.974211801658189) '#(-0.8632118016581896 -0.7521118016581892) > (circle-centers #(0.0000 2.0000) #(0.0000 0.0000) 1.0) '#(0.0 1.0) '#(0.0 1.0) > (circle-centers #(0.1234 0.9876) #(0.1234 0.9876) 2.0) . . Impossible to find a circle: "the points coinside." > (circle-centers #(0.1234 0.9876) #(0.8765 0.2345) 0.5) . . Impossible to find a circle: "given radius is less then the distance between points." > (circle-centers #(0.1234 0.9876) #(0.1234 0.9876) 0.0) . . Impossible to find a circle: "zero radius."
Drawing circles:
<lang racket> (require 2htdp/image)
(define/match (point v)
[{(vector x y)} (λ (s) (place-image (circle 2 "solid" "black") x y s))])
(define/match (circ v r)
[{(vector x y) r} (λ (s) (place-image (circle r "outline" "red") x y s))])
(define p1 #(40 50)) (define p2 #(60 30)) (define r 20) (define-values (x1 x2) (circle-centers p1 p2 r))
((compose (point p1) (point p2) (circ x1 r) (circ x2 r))
(empty-scene 100 100))
</lang>
REXX
<lang rexx>/*REXX pgm finds 2 circles with a specific radius given two (X,Y) points*/ @. = @.1 = 0.1234 0.9876 0.8765 0.2345 2 @.2 = 0 2 0 0 1 @.3 = 0.1234 0.9876 0.1234 0.9876 2 @.4 = 0.1234 0.9876 0.8765 0.2345 0.5 @.5 = 0.1234 0.9876 0.1234 0.9876 0 say ' x1 y1 x2 y2 radius circle1x circle1y circle2x circle2y' say ' ──────── ──────── ──────── ──────── ────── ──────── ──────── ──────── ────────'
do j=1 while @.j\== /*process all given points&radius*/
do k=1 for 4; w.k=f(word(@.j,k)) /*format # with 4 dec digs*/
end /*k*/
say w.1 w.2 w.3 w.4 center(word(@.j,5)/1,9) "───► " twoCircles(@.j)
end /*j*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────F subroutine────────────────────────*/ f: return right(format(arg(1),,4),9) /*format a # with 4 decimal digs.*/ /*──────────────────────────────────SQRT subroutine─────────────────────*/ sqrt: procedure; parse arg x; if x=0 then return 0; d=digits(); numeric digits 11 numeric form; m.=11; p=d+d%4+2; parse value format(x,2,1,,0) 'E0' with g 'E' _ . g=g*.5'E'_%2; do j=0 while p>9; m.j=p; p=p%2+1; end
do k=j+5 to 0 by -1; if m.k>11 then numeric digits m.k; g=.5*(g+x/g); end
numeric digits d; return g/1 /*──────────────────────────────────TWOCIRCLES subroutine───────────────*/ twoCircles: procedure; parse arg px py qx qy r . x=(qx-px)/2; y=(qy-py)/2; bx=px+x; by=py+y; pb=sqrt(x**2+y**2) if r=0 then return 'radius of zero gives no circles' if pb=0 then return 'coincident points give infinite circles' if pb>r then return 'points are too far apart for the given radius' cb=sqrt(r**2-pb**2); x1=y*cb/pb; y1=x*cb/pb return f(bx-x1) f(by+y1) f(bx+x1) f(by-y1)</lang>
- Output:
when using the default inputs
x1 y1 x2 y2 radius circle1x circle1y circle2x circle2y ──────── ──────── ──────── ──────── ────── ──────── ──────── ──────── ──────── 0.1234 0.9876 0.8765 0.2345 2 ───► 1.8631 1.9742 -0.8632 -0.7521 0.0000 2.0000 0.0000 0.0000 1 ───► 0.0000 1.0000 0.0000 1.0000 0.1234 0.9876 0.1234 0.9876 2 ───► coincident points give infinite circles 0.1234 0.9876 0.8765 0.2345 0.5 ───► points are too far apart for the given radius 0.1234 0.9876 0.1234 0.9876 0 ───► radius of zero gives no circles
Ruby
<lang ruby>Pt = Struct.new(:x, :y) Circle = Struct.new(:x, :y, :r)
def circles_from(pt1, pt2, r)
raise ArgumentError, "Infinite number of circles, points coincide." if pt1 == pt2 && r > 0 # handle single point and r == 0 return [Circle.new(pt1.x, pt1.y, r)] if pt1 == pt2 && r == 0 dx, dy = pt2.x - pt1.x, pt2.y - pt1.y # distance between points q = Math.hypot(dx, dy) # Also catches pt1 != pt2 && r == 0 raise ArgumentError, "Distance of points > diameter." if q > 2.0*r # halfway point x3, y3 = (pt1.x + pt2.x)/2.0, (pt1.y + pt2.y)/2.0 d = (r**2 - (q/2)**2)**0.5 [Circle.new(x3 - d*dy/q, y3 + d*dx/q, r), Circle.new(x3 + d*dy/q, y3 - d*dx/q, r)].uniq
end
- Demo:
ar = [[Pt.new(0.1234, 0.9876), Pt.new(0.8765, 0.2345), 2.0],
[Pt.new(0.0000, 2.0000), Pt.new(0.0000, 0.0000), 1.0],
[Pt.new(0.1234, 0.9876), Pt.new(0.1234, 0.9876), 2.0],
[Pt.new(0.1234, 0.9876), Pt.new(0.8765, 0.2345), 0.5],
[Pt.new(0.1234, 0.9876), Pt.new(0.1234, 0.9876), 0.0]]
ar.each do |p1, p2, r|
print "Given points:\n #{p1.values},\n #{p2.values}\n and radius #{r}\n"
begin
circles = circles_from(p1, p2, r)
puts "You can construct the following circles:"
circles.each{|c| puts " #{c}"}
rescue ArgumentError => e
puts e
end
puts
end</lang>
- Output:
Given points: [0.1234, 0.9876], [0.8765, 0.2345] and radius 2.0 You can construct the following circles: #<struct Circle x=1.8631118016581891, y=1.974211801658189, r=2.0> #<struct Circle x=-0.8632118016581893, y=-0.752111801658189, r=2.0> Given points: [0.0, 2.0], [0.0, 0.0] and radius 1.0 You can construct the following circles: #<struct Circle x=0.0, y=1.0, r=1.0> Given points: [0.1234, 0.9876], [0.1234, 0.9876] and radius 2.0 Infinite number of circles, points coincide. Given points: [0.1234, 0.9876], [0.8765, 0.2345] and radius 0.5 Distance of points > diameter. Given points: [0.1234, 0.9876], [0.1234, 0.9876] and radius 0.0 You can construct the following circles: #<struct Circle x=0.1234, y=0.9876, r=0.0>
Rust
<lang rust>use std::fmt;
struct Point {
x: f64, y: f64
}
impl Point { fn new(x : f64, y : f64) -> Point{ Point{x : x, y : y} } fn distance (&self, p : Point) -> f64{ ( (self.x - p.x).powi(2) + (self.y - p.y).powi(2) ).sqrt() } }
impl fmt::Show for Point { // a Point become printable in console
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "({:.4f}, {:.4f})", self.x, self.y)
}
}
fn is_circle(p1 : Point, p2 : Point, radius : f64){ let separation = p1.distance(p2);
if separation == 0.0 { if radius == 0.0 { println!("No circles can be drawn through {}", p1); } else { println!("Infinitely many circles can be drawn through {}", p1); } } else if separation == 2.0 * radius { println!("Given points are opposite ends of a diameter of the circle with center ({:.4f},{:.4f}) and radius {:.4f}",(p1.x+p2.x) / 2.0, (p1.y+p2.y) / 2.0, radius); } else if separation > 2.0 * radius { println!("Given points are farther away from each other than a diameter of a circle with radius {:.4f}", radius); } else { let mirror_distance = (radius.powi(2) - (separation / 2.0).powi(2)).sqrt();
println!("Two circles are possible."); println!("Circle C1 with center ({:.4f}, {:.4f}), radius {:.4f} and Circle C2 with center ({:.4f}, {:.4f}), radius {:.4f}", ((p1.x + p2.x) / 2.0) + mirror_distance * (p1.y-p2.y)/separation, (p1.y+p2.y) / 2.0 + mirror_distance*(p2.x-p1.x)/separation, radius, (p1.x+p2.x) / 2.0 - mirror_distance*(p1.y-p2.y)/separation, (p1.y+p2.y) / 2.0 - mirror_distance*(p2.x-p1.x)/separation, radius); } }
fn main() { let points : Vec<(Point, Point)> = vec!( (Point::new(0.1234, 0.9876), Point::new(0.8765, 0.2345)), (Point::new(0.0000, 2.0000), Point::new(0.0000, 0.0000)), (Point::new(0.1234, 0.9876), Point::new(0.1234, 0.9876)), (Point::new(0.1234, 0.9876), Point::new(0.8765, 0.2345)), (Point::new(0.1234, 0.9876), Point::new(0.1234, 0.9876)) ); let radii : Vec<f64> = vec!(2.0, 1.0, 2.0, 0.5, 0.0);
for (p, &r) in points.iter().zip(radii.iter()) { println!("\nPoints : {} \t Radius : {:.4f}", p, r); is_circle(p.val0(), p.val1(), r); } }</lang>
- Output:
Points : ((0.1234, 0.9876), (0.8765, 0.2345)) Radius : 2.0000 Two circles are possible. Circle C1 with center (1.8631, 1.9742), radius 2.0000 and Circle C2 with center (-0.8632, -0.7521), radius 2.0000 Points : ((0.0000, 2.0000), (0.0000, 0.0000)) Radius : 1.0000 Given points are opposite ends of a diameter of the circle with center (0.0000,1.0000) and radius 1.0000 Points : ((0.1234, 0.9876), (0.1234, 0.9876)) Radius : 2.0000 Infinitely many circles can be drawn through (0.1234, 0.9876) Points : ((0.1234, 0.9876), (0.8765, 0.2345)) Radius : 0.5000 Given points are farther away from each other than a diameter of a circle with radius 0.5000 Points : ((0.1234, 0.9876), (0.1234, 0.9876)) Radius : 0.0000 No circles can be drawn through (0.1234, 0.9876)
Seed7
<lang seed7>$ include "seed7_05.s7i";
include "float.s7i"; include "math.s7i";
const type: point is new struct
var float: x is 0.0; var float: y is 0.0; end struct;
const func point: point (in float: x, in float: y) is func
result var point: aPoint is point.value; begin aPoint.x := x; aPoint.y := y; end func;
const func float: distance (in point: p1, in point: p2) is
return sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2);
const proc: findCircles (in point: p1, in point: p2, in float: radius) is func
local
var float: separation is 0.0;
var float: mirrorDistance is 0.0;
begin
separation := distance(p1, p2);
if separation = 0.0 then
if radius = 0.0 then
write("Radius of zero. No circles can be drawn through (");
else
write("Infinitely many circles can be drawn through (");
end if;
writeln(p1.x digits 4 <& ", " <& p1.y digits 4 <& ")");
elsif separation = 2.0 * radius then
writeln("Given points are opposite ends of a diameter of the circle with center (" <&
(p1.x + p2.x) / 2.0 digits 4 <& ", " <& (p1.y + p2.y) / 2.0 digits 4 <& ") and radius " <&
radius digits 4);
elsif separation > 2.0 * radius then
writeln("Given points are farther away from each other than a diameter of a circle with radius " <&
radius digits 4);
else
mirrorDistance := sqrt(radius ** 2 - (separation / 2.0) ** 2);
writeln("Two circles are possible.");
writeln("Circle C1 with center (" <&
(p1.x + p2.x) / 2.0 + mirrorDistance*(p1.y - p2.y) / separation digits 4 <& ", " <&
(p1.y + p2.y) / 2.0 + mirrorDistance*(p2.x - p1.x) / separation digits 4 <& "), radius " <&
radius digits 4);
writeln("Circle C2 with center (" <&
(p1.x + p2.x) / 2.0 - mirrorDistance*(p1.y - p2.y) / separation digits 4 <& ", " <&
(p1.y + p2.y) / 2.0 - mirrorDistance*(p2.x - p1.x) / separation digits 4 <& "), radius " <&
radius digits 4);
end if;
end func;
const proc: main is func
local
const array array float: cases is [] (
[] (0.1234, 0.9876, 0.8765, 0.2345, 2.0),
[] (0.0000, 2.0000, 0.0000, 0.0000, 1.0),
[] (0.1234, 0.9876, 0.1234, 0.9876, 2.0),
[] (0.1234, 0.9876, 0.8765, 0.2345, 0.5),
[] (0.1234, 0.9876, 0.1234, 0.9876, 0.0));
var integer: index is 0;
begin
for index range 1 to 5 do
writeln("Case " <& index <& ":");
findCircles(point(cases[index][1], cases[index][2]),
point(cases[index][3], cases[index][4]), cases[index][5]);
end for;
end func;</lang>
- Output:
Case 1: Two circles are possible. Circle C1 with center (1.8631, 1.9742), radius 2.0000 Circle C2 with center (-0.8632, -0.7521), radius 2.0000 Case 2: Given points are opposite ends of a diameter of the circle with center (0.0000, 1.0000) and radius 1.0000 Case 3: Infinitely many circles can be drawn through (0.1234, 0.9876) Case 4: Given points are farther away from each other than a diameter of a circle with radius 0.5000 Case 5: Radius of zero. No circles can be drawn through (0.1234, 0.9876)
Tcl
<lang tcl>proc findCircles {p1 p2 r} {
lassign $p1 x1 y1
lassign $p2 x2 y2
# Special case: coincident & zero size
if {$x1 == $x2 && $y1 == $y2 && $r == 0.0} {
return [list [list $x1 $y1 0.0]]
}
if {$r <= 0.0} {
error "radius must be positive for sane results"
}
if {$x1 == $x2 && $y1 == $y2} {
error "no sane solution: points are coincident"
}
# Calculate distance apart and separation vector
set dx [expr {$x2 - $x1}]
set dy [expr {$y2 - $y1}]
set q [expr {hypot($dx, $dy)}]
if {$q > 2*$r} {
error "no solution: points are further apart than required diameter"
}
# Calculate midpoint
set x3 [expr {($x1+$x2)/2.0}]
set y3 [expr {($y1+$y2)/2.0}]
# Fractional distance along the mirror line
set f [expr {($r**2 - ($q/2.0)**2)**0.5 / $q}]
# The two answers
set c1 [list [expr {$x3 - $f*$dy}] [expr {$y3 + $f*$dx}] $r]
set c2 [list [expr {$x3 + $f*$dy}] [expr {$y3 - $f*$dx}] $r]
return [list $c1 $c2]
}</lang>
- Demo:
<lang tcl>foreach {p1 p2 r} {
{0.1234 0.9876} {0.8765 0.2345} 2.0
{0.0000 2.0000} {0.0000 0.0000} 1.0
{0.1234 0.9876} {0.1234 0.9876} 2.0
{0.1234 0.9876} {0.8765 0.2345} 0.5
{0.1234 0.9876} {0.1234 0.9876} 0.0
} {
puts "p1:([join $p1 {, }]) p2:([join $p2 {, }]) r:$r =>"
if {[catch {
foreach c [findCircles $p1 $p2 $r] { puts "\tCircle:([join $c {, }])" }
} msg]} {
puts "\tERROR: $msg"
}
}</lang>
- Output:
p1:(0.1234, 0.9876) p2:(0.8765, 0.2345) r:2.0 => Circle:(1.863111801658189, 1.974211801658189, 2.0) Circle:(-0.8632118016581891, -0.752111801658189, 2.0) p1:(0.0000, 2.0000) p2:(0.0000, 0.0000) r:1.0 => Circle:(0.0, 1.0, 1.0) Circle:(0.0, 1.0, 1.0) p1:(0.1234, 0.9876) p2:(0.1234, 0.9876) r:2.0 => ERROR: no sane solution: points are coincident p1:(0.1234, 0.9876) p2:(0.8765, 0.2345) r:0.5 => ERROR: no solution: points are further apart than required diameter p1:(0.1234, 0.9876) p2:(0.1234, 0.9876) r:0.0 => Circle:(0.1234, 0.9876, 0.0)
XPL0
An easy way to solve this: translate the coordinates so that one point is at the origin. Then rotate the coordinate frame so that the second point is on the X-axis. The circles' X coordinate is then half the distance to the second point. The circles' Y coordinates are easily seen as +/-sqrt(radius^2 - circleX^2). Now undo the rotation and translation. The method used here is a streamlining of these steps.
<lang XPL0>include c:\cxpl\codes;
proc Circles; real Data; \Show centers of circles, given points P & Q and radius real Px, Py, Qx, Qy, R, X, Y, X1, Y1, Bx, By, PB, CB; [Px:= Data(0); Py:= Data(1); Qx:= Data(2); Qy:= Data(3); R:= Data(4); if R = 0.0 then [Text(0, "Radius = zero gives no circles^M^J"); return]; X:= (Qx-Px)/2.0; Y:= (Qy-Py)/2.0; Bx:= Px+X; By:= Py+Y; PB:= sqrt(X*X + Y*Y); if PB = 0.0 then [Text(0, "Coincident points give infinite circles^M^J"); return]; if PB > R then [Text(0, "Points are too far apart for radius^M^J"); return]; CB:= sqrt(R*R - PB*PB); X1:= Y*CB/PB; Y1:= X*CB/PB; RlOut(0, Bx-X1); ChOut(0, ^,); RlOut(0, By+Y1); ChOut(0, 9\tab\); RlOut(0, Bx+X1); ChOut(0, ^,); RlOut(0, By-Y1); CrLf(0); ];
real Tbl; int I; [Tbl:=[[0.1234, 0.9876, 0.8765, 0.2345, 2.0],
[0.0000, 2.0000, 0.0000, 0.0000, 1.0],
[0.1234, 0.9876, 0.1234, 0.9876, 2.0],
[0.1234, 0.9876, 0.8765, 0.2345, 0.5],
[0.1234, 0.9876, 0.1234, 0.9876, 0.0]];
for I:= 0 to 4 do Circles(Tbl(I)); ]</lang>
- Output:
1.86311, 1.97421 -0.86321, -0.75211
0.00000, 1.00000 0.00000, 1.00000
Coincident points give infinite circles
Points are too far apart for radius
Radius = zero gives no circles
zkl
<lang zkl>fcn findCircles(a,b, c,d, r){ //-->T(T(x,y,r) [,T(x,y,r)]))
delta:=(a-c).hypot(b-d);
switch(delta){ // could just catch MathError
case(0.0){"singularity"} // should use epsilon test
case(r*2){T(T((a+c)/2,(b+d)/2,r))}
else{
if(delta > 2*r) "Point delta > diameter"; else{ md:=(r.pow(2) - (delta/2).pow(2)).sqrt(); T(T((a+c)/2 + md*(b-d)/delta,(b+d)/2 + md*(c-b)/delta,r), T((a+c)/2 - md*(b-d)/delta,(b+d)/2 - md*(c-b)/delta,r)); }
} }
}
data:=T(
T(0.1234, 0.9876, 0.8765, 0.2345, 2.0), T(0.0000, 2.0000, 0.0000, 0.0000, 1.0), T(0.1234, 0.9876, 0.1234, 0.9876, 2.0), T(0.1234, 0.9876, 0.8765, 0.2345, 0.5), T(0.1234, 0.9876, 0.1234, 0.9876, 0.0),
);
ppFmt:="(%2.4f,%2.4f)"; pprFmt:=ppFmt+" r=%2.1f"; foreach a,b, c,d, r in (data){
println("Points: ",ppFmt.fmt(a,b),", ",pprFmt.fmt(c,d,r));
print(" Circles: ");
cs:=findCircles(a,b,c,d,r);
if(List.isType(cs))
print(cs.pump(List,'wrap(c){pprFmt.fmt(c.xplode())}).concat(", "));
else print(cs);
println();
}</lang>
- Output:
Points: (0.1234,0.9876), (0.8765,0.2345) r=2.0 Circles: (1.8631,1.9742) r=2.0, (-0.8632,-0.7521) r=2.0 Points: (0.0000,2.0000), (0.0000,0.0000) r=1.0 Circles: (0.0000,1.0000) r=1.0 Points: (0.1234,0.9876), (0.1234,0.9876) r=2.0 Circles: singularity Points: (0.1234,0.9876), (0.8765,0.2345) r=0.5 Circles: Point delta > diameter Points: (0.1234,0.9876), (0.1234,0.9876) r=0.0 Circles: singularity