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;

            }

 

      }

}