Code: Select all
using System;
using System.Collections.Generic;
using Microsoft.DirectX;
namespace LineToCircleIntersection
{
static class IntersectionMethods
{
public class IntersectionObject
{
public List<Vector2> points = new List<Vector2>();
public void InsertSolution(float x_, float y_)
{
points.Add(new Vector2(x_, y_));
}
public void InsertSolution(Vector2 v_)
{
points.Add(v_);
}
public int NumberOfSolutions()
{
return points.Count;
}
}
//Circle to Circle
static public IntersectionObject CircleToCircleIntersection(float x0_, float y0_, float r0_,
float x1_, float y1_, float r1_)
{
IntersectionObject result = new IntersectionObject();
float a, dist, h;
Vector2 d, r = new Vector2(), v2 = new Vector2();
//d is the vertical and horizontal distances between the circle centers
d = new Vector2(x1_ - x0_, y1_ - y0_);
//distance between the circles
dist = d.Length();
//Check for equality and infinite intersections exist
if (dist == 0 && r0_ == r1_)
{
return result;
}
//Check for solvability
if (dist > r0_ + r1_)
{
//no solution. circles do not intersect
return result;
}
if (dist < Math.Abs(r0_ - r1_))
{
//no solution. one circle is contained in the other
return result;
}
if (dist == r0_ + r1_)
{
//one solution
result.InsertSolution((x0_ - x1_) / (r0_ + r1_) * r0_ + x1_, (y0_ - y1_) / (r0_ + r1_) * r0_ + y1_);
return result;
}
/* 'point 2' is the point where the line through the circle
* intersection points crosses the line between the circle
* centers.
*/
//Determine the distance from point 0 to point 2
a = ((r0_ * r0_) - (r1_ * r1_) + (dist * dist)) / (2.0f * dist);
//Determine the coordinates of point 2
v2 = new Vector2(x0_ + (d.X * a / dist), y0_ + (d.Y * a / dist));
//Determine the distance from point 2 to either of the intersection points
h = (float)Math.Sqrt((r0_ * r0_) - (a * a));
//Now determine the offsets of the intersection points from point 2
r = new Vector2(-d.Y * (h / dist), d.X * (h / dist));
//Determine the absolute intersection points
result.InsertSolution(v2 + r);
result.InsertSolution(v2 - r);
return result;
}
//Circle to Line
static public IntersectionObject CircleToLineIntersection(float x1_, float y1_, float r1_,
float x2_, float y2_, float x3_, float y3_)
{
return LineToCircleIntersection(x2_, y2_, x3_, y3_, x1_, y1_, r1_);
}
//Line to Circle
static public IntersectionObject LineToCircleIntersection(float x1_, float y1_, float x2_, float y2_,
float x3_, float y3_, float r3_)
{
IntersectionObject result = new IntersectionObject();
Vector2 v1, v2;
//Vector from point 1 to point 2
v1 = new Vector2(x2_ - x1_, y2_ - y1_);
//Vector from point 1 to the circle's center
v2 = new Vector2(x3_ - x1_, y3_ - y1_);
float dot = v1.X * v2.X + v1.Y * v2.Y;
Vector2 proj1 = new Vector2(((dot / (v1.LengthSq())) * v1.X), ((dot / (v1.LengthSq())) * v1.Y));
Vector2 midpt = new Vector2(x1_ + proj1.X, y1_ + proj1.Y);
float distToCenter = (midpt.X - x3_) * (midpt.X - x3_) + (midpt.Y - y3_) * (midpt.Y - y3_);
if (distToCenter > r3_ * r3_) return result;
if (distToCenter == r3_ * r3_)
{
result.InsertSolution(midpt);
return result;
}
float distToIntersection;
if (distToCenter == 0)
{
distToIntersection = r3_;
}
else
{
distToCenter = (float)Math.Sqrt(distToCenter);
distToIntersection = (float)Math.Sqrt(r3_ * r3_ - distToCenter * distToCenter);
}
float lineSegmentLength = 1 / (float)v1.Length();
v1 *= lineSegmentLength;
v1 *= distToIntersection;
result.InsertSolution(midpt + v1);
result.InsertSolution(midpt - v1);
return result;
}
//Circle to LineSegment
static public IntersectionObject CircleToLineSegmentIntersection(float x1_, float y1_, float r1_,
float x2_, float y2_, float x3_, float y3_)
{
return LineSegmentToCircleIntersection(x2_, y2_, x3_, y3_, x1_, y1_, r1_);
}
//LineSegment to Circle
static public IntersectionObject LineSegmentToCircleIntersection(float x1_, float y1_, float x2_, float y2_,
float x3_, float y3_, float r3_)
{
IntersectionObject result = new IntersectionObject();
Vector2 v1, v2;
//Vector from point 1 to point 2
v1 = new Vector2(x2_ - x1_, y2_ - y1_);
//Vector from point 1 to the circle's center
v2 = new Vector2(x3_ - x1_, y3_ - y1_);
float dot = v1.X * v2.X + v1.Y * v2.Y;
Vector2 proj1 = new Vector2(((dot / (v1.LengthSq())) * v1.X), ((dot / (v1.LengthSq())) * v1.Y));
Vector2 midpt = new Vector2(x1_ + proj1.X, y1_ + proj1.Y);
float distToCenter = (midpt.X - x3_) * (midpt.X - x3_) + (midpt.Y - y3_) * (midpt.Y - y3_);
if (distToCenter > r3_ * r3_) return result;
if (distToCenter == r3_ * r3_)
{
result.InsertSolution(midpt);
return result;
}
float distToIntersection;
if (distToCenter == 0)
{
distToIntersection = r3_;
}
else
{
distToCenter = (float)Math.Sqrt(distToCenter);
distToIntersection = (float)Math.Sqrt(r3_ * r3_ - distToCenter * distToCenter);
}
float lineSegmentLength = 1 / (float)v1.Length();
v1 *= lineSegmentLength;
v1 *= distToIntersection;
Vector2 solution1 = midpt + v1;
if ((solution1.X - x1_) * v1.X + (solution1.Y - y1_) * v1.Y > 0 &&
(solution1.X - x2_) * v1.X + (solution1.Y - y2_) * v1.Y < 0)
{
result.InsertSolution(solution1);
}
Vector2 solution2 = midpt - v1;
if ((solution2.X - x1_) * v1.X + (solution2.Y - y1_) * v1.Y > 0 &&
(solution2.X - x2_) * v1.X + (solution2.Y - y2_) * v1.Y < 0)
{
result.InsertSolution(solution2);
}
return result;
}
//Circle to Ray
static public IntersectionObject CircleToRayIntersection(float x1_, float y1_, float r1_,
float x2_, float y2_, float x3_, float y3_)
{
return RayToCircleIntersection(x2_, y2_, x3_, y3_, x1_, y1_, r1_);
}
//Ray to Circle
static public IntersectionObject RayToCircleIntersection(float x1_, float y1_, float x2_, float y2_,
float x3_, float y3_, float r3_)
{
IntersectionObject result = new IntersectionObject();
Vector2 v1, v2;
//Vector from point 1 to point 2
v1 = new Vector2(x2_ - x1_, y2_ - y1_);
//Vector from point 1 to the circle's center
v2 = new Vector2(x3_ - x1_, y3_ - y1_);
float dot = v1.X * v2.X + v1.Y * v2.Y;
Vector2 proj1 = new Vector2(((dot / (v1.LengthSq())) * v1.X), ((dot / (v1.LengthSq())) * v1.Y));
Vector2 midpt = new Vector2(x1_ + proj1.X, y1_ + proj1.Y);
float distToCenter = (midpt.X - x3_) * (midpt.X - x3_) + (midpt.Y - y3_) * (midpt.Y - y3_);
if (distToCenter > r3_ * r3_) return result;
if (distToCenter == r3_ * r3_)
{
result.InsertSolution(midpt);
return result;
}
float distToIntersection;
if (distToCenter == 0)
{
distToIntersection = r3_;
}
else
{
distToCenter = (float)Math.Sqrt(distToCenter);
distToIntersection = (float)Math.Sqrt(r3_ * r3_ - distToCenter * distToCenter);
}
float lineSegmentLength = 1 / (float)v1.Length();
v1 *= lineSegmentLength;
v1 *= distToIntersection;
Vector2 solution1 = midpt + v1;
if ((solution1.X - x1_) * v1.X + (solution1.Y - y1_) * v1.Y > 0)
{
result.InsertSolution(solution1);
}
Vector2 solution2 = midpt - v1;
if ((solution2.X - x1_) * v1.X + (solution2.Y - y1_) * v1.Y > 0)
{
result.InsertSolution(solution2);
}
return result;
}
//Line to Line
static public IntersectionObject LineToLineIntersection(float x1_, float y1_, float x2_, float y2_,
float x3_, float y3_, float x4_, float y4_)
{
IntersectionObject result = new IntersectionObject();
float r, s, d;
//Make sure the lines aren't parallel
if ((y2_ - y1_) / (x2_ - x1_) != (y4_ - y3_) / (x4_ - x3_))
{
d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
if (d != 0)
{
r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;
result.InsertSolution(x1_ + r * (x2_ - x1_), y1_ + r * (y2_ - y1_));
}
}
return result;
}
//LineSegment to LineSegment
static public IntersectionObject LineSegmentToLineSegmentIntersection(float x1_, float y1_, float x2_, float y2_,
float x3_, float y3_, float x4_, float y4_)
{
IntersectionObject result = new IntersectionObject();
float r, s, d;
//Make sure the lines aren't parallel
if ((y2_ - y1_) / (x2_ - x1_) != (y4_ - y3_) / (x4_ - x3_))
{
d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
if (d != 0)
{
r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;
if (r >= 0 && r <= 1)
{
if (s >= 0 && s <= 1)
{
result.InsertSolution(x1_ + r * (x2_ - x1_), y1_ + r * (y2_ - y1_));
}
}
}
}
return result;
}
//Line to LineSement
static public IntersectionObject LineToLineSegmentIntersection(float x1_, float y1_, float x2_, float y2_,
float x3_, float y3_, float x4_, float y4_)
{
return LineSegmentToLineIntersection(x3_, y3_, x4_, y4_, x1_, y1_, x2_, y2_);
}
//LineSegment to Line
static public IntersectionObject LineSegmentToLineIntersection(float x1_, float y1_, float x2_, float y2_,
float x3_, float y3_, float x4_, float y4_)
{
IntersectionObject result = new IntersectionObject();
float r, s, d;
//Make sure the lines aren't parallel
if ((y2_ - y1_) / (x2_ - x1_) != (y4_ - y3_) / (x4_ - x3_))
{
d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
if (d != 0)
{
r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;
if (r >= 0 && r <= 1)
{
result.InsertSolution(x1_ + r * (x2_ - x1_), y1_ + r * (y2_ - y1_));
}
}
}
return result;
}
//LineSegment to Ray
static public IntersectionObject LineSegmentToRayIntersection(float x1_, float y1_, float x2_, float y2_,
float x3_, float y3_, float x4_, float y4_)
{
return RayToLineSegmentIntersection(x3_, y3_, x4_, y4_, x1_, y1_, x2_, y2_);
}
//Ray to LineSegment
static public IntersectionObject RayToLineSegmentIntersection(float x1_, float y1_, float x2_, float y2_,
float x3_, float y3_, float x4_, float y4_)
{
IntersectionObject result = new IntersectionObject();
float r, s, d;
//Make sure the lines aren't parallel
if ((y2_ - y1_) / (x2_ - x1_) != (y4_ - y3_) / (x4_ - x3_))
{
d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
if (d != 0)
{
r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;
if (r >= 0)
{
if (s >= 0 && s <= 1)
{
result.InsertSolution(x1_ + r * (x2_ - x1_), y1_ + r * (y2_ - y1_));
}
}
}
}
return result;
}
//Line to Ray
static public IntersectionObject LineToRayIntersection(float x1_, float y1_, float x2_, float y2_,
float x3_, float y3_, float x4_, float y4_)
{
return RayToLineIntersection(x3_, y3_, x4_, y4_, x1_, y1_, x2_, y2_);
}
//Ray to Line
static public IntersectionObject RayToLineIntersection(float x1_, float y1_, float x2_, float y2_,
float x3_, float y3_, float x4_, float y4_)
{
IntersectionObject result = new IntersectionObject();
float r, s, d;
//Make sure the lines aren't parallel
if ((y2_ - y1_) / (x2_ - x1_) != (y4_ - y3_) / (x4_ - x3_))
{
d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
if (d != 0)
{
r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;
if (r >= 0)
{
result.InsertSolution(x1_ + r * (x2_ - x1_), y1_ + r * (y2_ - y1_));
}
}
}
return result;
}
//Ray to Ray
static public IntersectionObject RayToRayIntersection(float x1_, float y1_, float x2_, float y2_,
float x3_, float y3_, float x4_, float y4_)
{
IntersectionObject result = new IntersectionObject();
float r, s, d;
//Make sure the lines aren't parallel
if ((y2_ - y1_) / (x2_ - x1_) != (y4_ - y3_) / (x4_ - x3_))
{
d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
if (d != 0)
{
r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;
if (r >= 0)
{
if (s >= 0)
{
result.InsertSolution(x1_ + r * (x2_ - x1_), y1_ + r * (y2_ - y1_));
}
}
}
}
return result;
}
}
}