## 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*e3d2=-e3*e1d3=-e1*e2(e1=v3-v2, e2=v1-v3, e3=v2-v1, * is the dot product)c1=d2d3c2=d3d1c3=d1d2c=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:

`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 OO002 5O003 STO IO004 STO(I)O005 4O006 STO IO007 LASTXO008 STO(I)O009 eq M-L0O10 eq M-KO011 eq [ABS(REGY),ABS(REGX),ABS(L-K)]O012 STO ZO013 eq REGX/([1,0,0]xREGX+[0,1,0]xREGX+[0,0,1]xREGX)O014 R^O015 R^O016 XEQ X001O017 R^O018 X<>YO019 ABSO020 eq REGX/([1,0,0]xZ+[0,1,0]xZ+[0,0,1]xZ)O021 X<>YO022 RDNO023 X<>YO024 RCL(I)O025 ABSO026 RDNO027 XEQ U001O028 eq M-LO029 eq K-MO030 eq L-KO031 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]xREGXO034 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 U079O037 RTN`

`XEQ ARDNRDNXEQ ARDNRDN`