using System;
using System.Drawing;
namespace Geometry
{
/// <summary>
///
Geometric solutions for circles
/// </summary>
public
class CircleGeometry
{
private
CircleGeometry()
{
}
/// <summary>
/// Find circles tangent to three lines
/// </summary>
/// <param
name="pt11">First point on first
line</param>
/// <param
name="pt12">Second point on first
line</param>
/// <param
name="pt21">First point on second
line</param>
/// <param
name="pt22">Second point on
second line</param>
/// <param
name="pt31">First point on third
line</param>
/// <param
name="pt32">Second point on third
line</param>
/// <param
name="Centres">Array to receive list of centre points</param>
/// <param
name="Radii">Array to receive
list of radii</param>
/// <returns>Number of solutions</returns>
public
static int Circle3L(Point pt11, Point pt12, Point
pt21, Point pt22,
Point pt31, Point pt32, ref
Point[] Centres, ref int[]
Radii)
//*************************************************************************
// Find circles tangent
to 3 lines
{
double
a1, b1, c1, a2, b2, c2, a3, b3, c3;
double
t1, t2, t3, u, v, Div, fRadius, xc,
yc;
int nRadius;
Point ptCentre;
// Initialise
int nSolutions
= 0;
Centres = new Point[0];
Radii = new int[0];
// Ensure
second line is not vertical
if(pt21.X
== pt22.X)
{
if(pt11.X
== pt12.X)
{
Point ptTemp
= pt21;
pt21 = pt31;
pt31 = ptTemp;
ptTemp
= pt22;
pt22 = pt32;
pt32 = ptTemp;
}
else
{
Point ptTemp
= pt11;
pt11 = pt21;
pt21 = ptTemp;
ptTemp
= pt12;
pt12 = pt22;
pt22 = ptTemp;
}
}
// Get normalised line equations
a1 = 0.0; b1
= 0.0; c1 = 0.0;
if(!LineGeometry.Equation(pt11, pt12, ref
a1, ref b1, ref
c1)) return 0;
a2 = 0.0; b2
= 0.0; c2 = 0.0;
if(!LineGeometry.Equation(pt21, pt22, ref
a2, ref b2, ref
c2)) return 0;
a3 = 0.0; b3
= 0.0; c3 = 0.0;
if(!LineGeometry.Equation(pt31, pt32, ref
a3, ref b3, ref
c3)) return 0;
// Derive
constants from equations
u = (a2 * b1) - (a1 * b2);
v = (a3 * b2) - (a2 * b3);
// Take all combinations
of t(n) to get circles on other side of lines
for(int iCase=0;
iCase<8; ++iCase)
{
t1 = ((iCase &
1) == 0) ? 1 : -1;
t2 = ((iCase &
2) == 0) ? 1 : -1;
t3 = ((iCase &
4) == 0) ? 1 : -1;
// Calculate radius
Div = v * (b1*t2 - b2*t1) - u * (b2*t3 -
b3*t2);
if(Div
== 0.0) continue;
fRadius
= (u * (b3*c2 - b2*c3) - v * (b2*c1 - b1*c2)) / Div;
if((fRadius <= 0.0) || (fRadius
> (double)Int32.MaxValue)) continue;
nRadius
= (int)Math.Round(fRadius);
// Derive centre
if(u
!= 0.0) xc = (b2*c1 - b2*fRadius*t1
- b1*c2 + b1*fRadius*t2) / u;
else
if(v != 0.0) xc =
(b3*c2 + b3*fRadius*t2 - b2*c3 + b2*fRadius*t3) / v;
else
continue;
if(Math.Abs(xc) > (double)Int32.MaxValue) continue;
if(b1
!= 0.0) yc = (-a1*xc - c1 +
fRadius*t1) / b1;
else
if(b2 != 0.0) yc =
(-a2*xc - c2 + fRadius*t2)
/ b2;
else
yc = (-a3*xc - c3 + fRadius*t3) / b3;
if(Math.Abs(yc) > (double)Int32.MaxValue) continue;
ptCentre
= new Point((int)Math.Round(xc), (int)Math.Round(yc));
// Add to solutions list
nSolutions
= AddSolution(ptCentre, nRadius, ref Centres, ref Radii);
}
// Return the number of
solutions found
return
nSolutions;
}
private
static int AddSolution(Point
ptCentre, int
nRadius,
ref
Point[] Centres, ref int[] Radii)
//*****************************************************
// Add
a solution to a list if not already present
// In
this overload, all values are integral
{
Point[] CentreCopy = new Point[0];
int[] RadiiCopy = new int[0];
// Don't
accept zero or negative radius solutions
int nSolutions
= Centres.Length;
if(nRadius <= 0) return nSolutions;
// Check if present
bool bPresent
= false;
for(int iSolution=0;
iSolution<nSolutions; ++iSolution)
{
if((ptCentre == Centres[iSolution]) &&
(nRadius
== Radii[iSolution]))
{
bPresent
= true;
break;
}
}
// If found, keep current
solutions
if(bPresent) return nSolutions;
// Otherwise,
copy existing solutions to temporary arrays
if(nSolutions > 0)
{
CentreCopy = new Point[nSolutions];
RadiiCopy = new int[nSolutions];
Array.Copy(Centres, 0, CentreCopy,
0, nSolutions);
Array.Copy(Radii, 0, RadiiCopy, 0, nSolutions);
}
// Set up new solution
arrays and load
Centres = new Point[nSolutions + 1];
Radii = new int[nSolutions + 1];
if(nSolutions > 0)
{
Array.Copy(CentreCopy, 0, Centres, 0, nSolutions);
Array.Copy(RadiiCopy, 0, Radii, 0, nSolutions);
}
Centres[nSolutions] = ptCentre;
Radii[nSolutions]
= nRadius;
// Return updated number
of solutions
return
(nSolutions + 1);
}
}
}
using System;
using System.Drawing;
namespace Geometry
{
/// <summary>
///
Geometric solutions for straight lines
/// </summary>
public
class LineGeometry
{
private
LineGeometry()
{
}
/// <summary>
/// Get the normalised equation of a
line between two points in the form: Ax + By + C = 0
/// </summary>
/// <param
name="pt1">First point</param>
/// <param
name="pt2">Second point</param>
/// <param
name="A">X factor</param>
/// <param
name="B">Y factor</param>
/// <param
name="C">Constant</param>
/// <returns>true on success</returns>
public
static bool Equation(Point pt1, Point pt2, ref double A, ref double B, ref double C)
//****************************************************************************************
// Derive
the equation of the line between 2 points in the form Ax + By + C = 0
// If the points are coincident, return
false
// In
this overload, coordinates are integral values
{
// Validation
if((pt1
== pt2)) return false;
// Get constants
int xDiff =
pt2.X - pt1.X;
int yDiff =
pt2.Y - pt1.Y;
double
rSquare = ((double)xDiff * xDiff) + ((double)yDiff * yDiff);
double
rInv = 1.0 / rSquare;
// Derive
parameters
A = -yDiff * rInv;
B = xDiff * rInv;
C = ((double)pt1.X * pt2.Y - (double)pt2.X
* pt1.Y) * rInv;
// Normalize
the equation for convenience
double
sMult = 1.0 / Math.Sqrt( A
* A + B * B);
A *= sMult;
B *= sMult;
C *= sMult;
// Return success
return
true;
}
}
}