Sunday, October 21, 2007

HP-35s Euclid Implementation - XV : The inscribed and circumscribed circle of a triangle

The final program to fullfill the requirements! Problem 16 and 17: Finding the inscribed (incircle) and circumscribed (circumcircle) circles of a triangle.

Finding the inscribed circle is the same as solving the problem of finding the circle tangent to three lines (lines defined by the triangle edges) and finding the circumscribed circle is the same as solving the problem of finding the circle that passes through three points (triangle's vertexes).

The triangle in question has been entered using the T program.

v3
/ \
/ \
/ \
v1------v2
Refering to the above triangle I give the formulas used in the HP-35s program presented here:

Inscribed circle:

The barycentric coordinates for the incenter are:
(l1/p, l2/p, l3/p)
Where p is the perimeter of the triangle (sum of all edges lengths) and l1 is the length of the edge v3-v2, l2 is the length of the edge v1-v3 and l3 is the length of the edge v2-v1.

The radius of the inscribed circle is:
(2A)/p
Where A is the area of the triangle.

Circumscribed circle:

With the intermediate results
d1=-e2*e3
d2=-e3*e1
d3=-e1*e2

(e1=v3-v2, e2=v1-v3, e3=v2-v1, * is the dot product)

c1=d2d3
c2=d3d1
c3=d1d2

c=c1+c2+c3
the barycentric coordinates for the circumcenter are:
((c2+c3)/2c, (c3+c1)/2c, (c1+c2)/2c)
The radius of the circumscribed circle is:
sqrt((d1+d2)(d2+d3)(d3+d1)/c)/2
These formulas are taken from the excelent book 3D Math Primer for Graphics and Game Development that also provide background for much of the geometric problems in the Euclid Pack specification.

Stack Input/Output:
No input on stack-> XEQ O ->[[bc1, bc2, bc3], cr, [bi1, bi2, bi3], ir | L]
Where (bc1, bc2, bc3) are the barycentric coordinates for the circumscribed circle's center (circumcenter) , cr is its radius, (bi1, bi2, bi3) are the barycentric coordinates for the inscribed circle's center (incenter) and ir is its radius.

Variables:

Reads:
K : First vertex (3D vector). Populated by the T program.
L : Second vertex (3D vector). Populated by the T program.
M : Third vertex (3D vector). Populated by the T program.
Writes:
Z : Scratch data.
Program:
O001 LBL O
O002 5
O003 STO I
O004 STO(I)
O005 4
O006 STO I
O007 LASTX
O008 STO(I)
O009 eq M-L
0O10 eq M-K
O011 eq [ABS(REGY),ABS(REGX),ABS(L-K)]
O012 STO Z
O013 eq REGX/([1,0,0]xREGX+[0,1,0]xREGX+[0,0,1]xREGX)
O014 R^
O015 R^
O016 XEQ X001
O017 R^
O018 X<>Y
O019 ABS
O020 eq REGX/([1,0,0]xZ+[0,1,0]xZ+[0,0,1]xZ)
O021 X<>Y
O022 RDN
O023 X<>Y
O024 RCL(I)
O025 ABS
O026 RDN
O027 XEQ U001
O028 eq M-L
O029 eq K-M
O030 eq L-K
O031 eq [-REGYxREGX,-REGXxREGZ,-REGZxREGY]
O032 eq [([0,1,0]xREGX)x([0,1,0]xREGX),
([0,0,1]xREGX)x([1,0,0]xREGX),
([1,0,0]xREGX)x([0,1,0]xREGX)]
O033 eq [1,0,0]xREGX+[0,1,0]xREGX+[0,0,1]xREGX
O034 eq 0.5xSQRT((([1,0,0]xREGZ+[0,1,0]xREGZ)x
([0,1,0]xREGZ+[0,0,1]xREGZ)x
([0,0,1]xREGZ+[1,0,0]xREGZ))/REGX)
O035 eq [([0,1,0]xREGZ)+([0,0,1]xREGZ),
([0,0,1]xREGZ)+([1,0,0]xREGZ),
([1,0,0]xREGZ)+([0,1,0]xREGZ)]/(2xREGY)
O036 XEQ U079
O037 RTN
Comments:

Terms of use.

Mnemonics: O since letter is a circle (or more or less depeding on font, rather circular on the 35s).

Reason for not converting to cartesian coordinates is that since the barycentric coordinates are relative to the vertices it is much easier to 'see' where the center points are relative to the triangle. If one where to be presented the cartesian coordinates one must remember the nine vertex coordinates to know where (relative to triangle) the center points are. Particular one see at once if the circumscribed circle's center is inside or outside the triangle.

Cartesian coordinates are easily obtained using the A program by the following key sequence:
XEQ A
RDN
RDN
XEQ A
RDN
RDN
The last two RDN are only provided to get content of stack in same order as before except that barycentric positional vectors are now replaced with cartesian ones.

No comments: