[source lang = "c#"]
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;
}
}
}
[C++ Code Update] 2D Intersection Algorithms
Author
I implemented most of these and got help with them on a site. If anyone with some math experience and optimization experience could look over them. They are at the core of my game and are used a lot, so any small changes or optimizations are welcome.
(you'll notice I only use Vector2 for the x and y structure and length and such, this is because the code is ported between my server and client which don't have access to the same stuff).
Code is found here
if the paste bin is remove you can scroll through this:
Also any refactoring and such would be nice also. I've tried to compress and optimize the code as much as I know how already, but I'm sure I'm missing simple things.
I just want these as optimized before I start porting and such since maintaining changes between my server and client can be tedious.
[Edited by - Sirisian on January 27, 2009 5:01:10 PM]
Could you shorten some of the longer lines? Not having to scroll back and forth would make it easier to read (for me at least).
Author
Quote:Original post by jyk
Could you shorten some of the longer lines? Not having to scroll back and forth would make it easier to read (for me at least).
I changed the formatting for the parameters. Now it's logically separated.
Author
It's been a while. I noticed this has been asked before, so I converted and optimized my code to a C++ version.
Inside you'll find circle, line, line-segment, and ray intersection algorithms.
Just in case anyone is curious what this means. An intersection finds the points that both shapes/lines/rays share in common.
Here's the code:
C++ Intersections
I formatted the tabbing to align in gamedev.net's tab rules so you can view it:
It's as easy as:
IntersectionObject io = LineSegmentToLineSegmentIntersection(Vector2(-5,0), Vector2(5, 0), Vector2(0, -5), Vector2(0, 5));
if(io.NumberOfSolutions() == 1)
{
// io.points[0] contains Vector2(0, 0)
}
Or:
IntersectionObject io = LineToCircleIntersection(Vector2(0, 0), Vector2(1, 0), Vector2(5, 0), 2);
for(std::vector<Vector2>::iterator sItr = io.points.begin(); sItr != io.points.end(); ++sItr)
{
// *sItr will be Vector2(3, 0) and then Vector2(7, 0)
}
Inside you'll find circle, line, line-segment, and ray intersection algorithms.
Just in case anyone is curious what this means. An intersection finds the points that both shapes/lines/rays share in common.
Here's the code:
C++ Intersections
I formatted the tabbing to align in gamedev.net's tab rules so you can view it:
#pragma once#include <vector>#include <cmath>#include "Vector2.hpp"namespace IntersectionFunctions{ struct IntersectionObject { std::vector<Vector2> points; void InsertSolution(float x, float y) { points.push_back(Vector2(x, y)); } void InsertSolution(Vector2 v) { points.push_back(v); } int NumberOfSolutions() { return points.size(); } }; // Circle to Circle IntersectionObject CircleToCircleIntersection(Vector2 circlePosition1, float radius1, Vector2 circlePosition2, float radius2) { IntersectionObject result; float a, distSq, dist, h; Vector2 d, r, v2; // d is the vertical and horizontal distances between the circle centers d = circlePosition1 - circlePosition2; //distance squared between the circles distSq = d.LengthSq(); // Check for equality and infinite intersections exist if (distSq == 0 && radius1 == radius2) { return result; } //Check for solvability if (distSq > (radius1 + radius2) * (radius1 + radius2)) { // no solution. circles do not intersect return result; } if (distSq < abs(radius1 - radius2) * abs(radius1 - radius2)) { // no solution. one circle is contained in the other return result; } if (distSq == (radius1 + radius2) * (radius1 + radius2)) { //one solution result.InsertSolution((circlePosition1 - circlePosition2) / (radius1 + radius2) * radius1 + circlePosition1); return result; } dist = sqrt(distSq); // '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 = ((radius1 * radius1) - (radius2 * radius2) + distSq) / (2.0f * dist); // Determine the coordinates of point 2 v2 = circlePosition1 + d * (a / dist); // Determine the distance from point 2 to either of the intersection points h = sqrt((radius1 * radius1) - (a * a)); // Now determine the offsets of the intersection points from point 2 r = d * (h / dist); r = r.Normal(); // Determine the absolute intersection points result.InsertSolution(v2 + r); result.InsertSolution(v2 - r); return result; } // Used only within this namespace int PrivateLineToCircleIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 circlePosition, float radius, Vector2 & solution1, Vector2 & solution2) { // Vector from point 1 to point 2 Vector2 vertex1to2 = vertex2 - vertex1; // Vector from point 1 to the circle's center Vector2 circleToVertex1 = circlePosition - vertex1; float dot = vertex1to2.Dot(circleToVertex1); Vector2 proj1 = vertex1to2 * (dot / vertex1to2.LengthSq()); Vector2 midpt = vertex1 + proj1; Vector2 circleToMidpt = midpt - circlePosition; float distSqToCenter = circleToMidpt.LengthSq(); if (distSqToCenter > radius * radius) return 0; if (distSqToCenter == radius * radius) { solution1 = midpt; return 1; } float distToIntersection; if (distSqToCenter == 0) { distToIntersection = radius; } else { distToIntersection = sqrt(radius * radius - distSqToCenter); } vertex1to2 = vertex1to2.Normalize(); vertex1to2 *= distToIntersection; solution1 = midpt + vertex1to2; solution2 = midpt - vertex1to2; return 2; } //Line to Circle IntersectionObject LineToCircleIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 circlePosition, float radius) { IntersectionObject result; Vector2 solution1, solution2; switch(PrivateLineToCircleIntersection(vertex1, vertex2, circlePosition, radius, solution1, solution2)) { case 2: result.InsertSolution(solution2); case 1: result.InsertSolution(solution1); break; } return result; } // Circle to Line IntersectionObject CircleToLineIntersection(Vector2 circlePosition, float radius, Vector2 vertex1, Vector2 vertex2) { return LineToCircleIntersection(vertex1, vertex2, circlePosition, radius); } // LineSegment to Circle IntersectionObject LineSegmentToCircleIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 circlePosition, float radius) { IntersectionObject result; Vector2 solution1, solution2; Vector2 vertex1to2 = vertex2 - vertex1; Vector2 vertex1ToSolution1, vertex2ToSolution1, vertex1ToSolution2, vertex2ToSolution2; switch(PrivateLineToCircleIntersection(vertex1, vertex2, circlePosition, radius, solution1, solution2)) { case 2: vertex1ToSolution2 = solution2 - vertex1; vertex2ToSolution2 = solution2 - vertex2; if (vertex1ToSolution2.Dot(vertex1to2) > 0 && vertex2ToSolution2.Dot(vertex1to2) < 0) { result.InsertSolution(solution2); } case 1: vertex1ToSolution1 = solution1 - vertex1; vertex2ToSolution1 = solution1 - vertex2; if (vertex1ToSolution1.Dot(vertex1to2) > 0 && vertex2ToSolution1.Dot(vertex1to2) < 0) { result.InsertSolution(solution1); } break; } return result; } // Circle to LineSegment IntersectionObject CircleToLineSegmentIntersection(Vector2 circlePosition, float radius, Vector2 vertex1, Vector2 vertex2) { return LineSegmentToCircleIntersection(vertex1, vertex2, circlePosition, radius); } // Ray to Circle IntersectionObject RayToCircleIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 circlePosition, float radius) { IntersectionObject result; Vector2 solution1, solution2; Vector2 vertex1to2 = vertex2 - vertex1; Vector2 vertex1ToSolution1, vertex1ToSolution2; switch(PrivateLineToCircleIntersection(vertex1, vertex2, circlePosition, radius, solution1, solution2)) { case 2: vertex1ToSolution2 = solution2 - vertex1; if (vertex1ToSolution2.Dot(vertex1to2) > 0) { result.InsertSolution(solution2); } case 1: vertex1ToSolution1 = solution1 - vertex1; if (vertex1ToSolution1.Dot(vertex1to2) > 0) { result.InsertSolution(solution1); } break; } return result; } // Circle to Ray IntersectionObject CircleToRayIntersection(Vector2 circlePosition, float radius, Vector2 vertex1, Vector2 vertex2) { return RayToCircleIntersection(vertex1, vertex2, circlePosition, radius); } // Used only within this namespace bool PrivateLineToLineIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 vertex3, Vector2 vertex4, float & r, float & s) { float d; //Make sure the lines aren't parallel Vector2 vertex1to2 = vertex2 - vertex1; Vector2 vertex3to4 = vertex4 - vertex3; //if (vertex1to2.x * -vertex3to4.y + vertex1to2.y * vertex3to4.x != 0) //{ if(vertex1to2.y / vertex1to2.x != vertex3to4.y / vertex3to4.x) { d = vertex1to2.x * vertex3to4.y - vertex1to2.y * vertex3to4.x; if (d != 0) { Vector2 vertex3to1 = vertex1 - vertex3; r = (vertex3to1.y * vertex3to4.x - vertex3to1.x * vertex3to4.y) / d; s = (vertex3to1.y * vertex1to2.x - vertex3to1.x * vertex1to2.y) / d; return true; } } return false; } // Line to Line IntersectionObject LineToLineIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 vertex3, Vector2 vertex4) { IntersectionObject result; float r, s; if(PrivateLineToLineIntersection(vertex1, vertex2, vertex3, vertex4, r, s)) { result.InsertSolution(vertex1 + (vertex2 - vertex1) * r); } return result; } // LineSegment to LineSegment IntersectionObject LineSegmentToLineSegmentIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 vertex3, Vector2 vertex4) { IntersectionObject result; float r, s; if(PrivateLineToLineIntersection(vertex1, vertex2, vertex3, vertex4, r, s)) { if (r >= 0 && r <= 1) { if (s >= 0 && s <= 1) { result.InsertSolution(vertex1 + (vertex2 - vertex1) * r); } } } return result; } // LineSegment to Line IntersectionObject LineSegmentToLineIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 vertex3, Vector2 vertex4) { IntersectionObject result; float r, s; if(PrivateLineToLineIntersection(vertex1, vertex2, vertex3, vertex4, r, s)) { if (r >= 0 && r <= 1) { result.InsertSolution(vertex1 + (vertex2 - vertex1) * r); } } return result; } // Line to LineSement IntersectionObject LineToLineSegmentIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 vertex3, Vector2 vertex4) { return LineSegmentToLineIntersection(vertex3, vertex4, vertex1, vertex2); } // Ray to LineSegment IntersectionObject RayToLineSegmentIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 vertex3, Vector2 vertex4) { IntersectionObject result; float r, s; if(PrivateLineToLineIntersection(vertex1, vertex2, vertex3, vertex4, r, s)) { if (r >= 0) { if (s >= 0 && s <= 1) { result.InsertSolution(vertex1 + (vertex2 - vertex1) * r); } } } return result; } // LineSegment to Ray IntersectionObject LineSegmentToRayIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 vertex3, Vector2 vertex4) { return RayToLineSegmentIntersection(vertex3, vertex4, vertex1, vertex2); } // Ray to Line IntersectionObject RayToLineIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 vertex3, Vector2 vertex4) { IntersectionObject result; float r, s; if(PrivateLineToLineIntersection(vertex1, vertex2, vertex3, vertex4, r, s)) { if (r >= 0) { result.InsertSolution(vertex1 + (vertex2 - vertex1) * r); } } return result; } // Line to Ray IntersectionObject LineToRayIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 vertex3, Vector2 vertex4) { return RayToLineIntersection(vertex3, vertex4, vertex1, vertex2); } // Ray to Ray IntersectionObject RayToRayIntersection(Vector2 vertex1, Vector2 vertex2, Vector2 vertex3, Vector2 vertex4) { IntersectionObject result; float r, s; if(PrivateLineToLineIntersection(vertex1, vertex2, vertex3, vertex4, r, s)) { if (r >= 0) { if (s >= 0) { result.InsertSolution(vertex1 + (vertex2 - vertex1) * r); } } } return result; }}It's as easy as:
IntersectionObject io = LineSegmentToLineSegmentIntersection(Vector2(-5,0), Vector2(5, 0), Vector2(0, -5), Vector2(0, 5));
if(io.NumberOfSolutions() == 1)
{
// io.points[0] contains Vector2(0, 0)
}
Or:
IntersectionObject io = LineToCircleIntersection(Vector2(0, 0), Vector2(1, 0), Vector2(5, 0), 2);
for(std::vector<Vector2>::iterator sItr = io.points.begin(); sItr != io.points.end(); ++sItr)
{
// *sItr will be Vector2(3, 0) and then Vector2(7, 0)
}
Sirisian,
Without even getting into the math, you can start by applying some good coding practices to increase the efficiency.
For example, I notice that you have made a user-defined constructor for your vector, which makes it a non-POD type. This can be a very significant loss of performance when doing lots of copying of that class, which is necessarily going to happen when you have things like "std::vector<Vector2>," or when you pass a Vector2 argument by value, as you're doing here. However, there's no reason to pass your Vector2 by value -- you should change that to a const-reference immediately.
Second, I recommend changing your Vector2 class to be POD. I understand this may be an annoyance to you if you really want to do things like,
Vector2 v(1,2);
However with a POD class, you can still use these similar alternatives:
Vector2 v = {{1,2}};
Vector2 v = make_vector2(1,2);
Next, you may want to rethink your "overly-object-centric-oriented-design" philosophy, and just stop using so many "objects" altogether, if you can help it.
I notice that you are returning some objects by value from functions. Luckily for you, the current version of MSVC has NRVO built into it which converts that into a return-by-reference-argument automatically. However, there's still some loss of performance for doing it that way.
It also is encouraging you to "over-calculate" things. For example, an expression like:
"if(io.NumberOfSolutions() == 1)"
Indicates that you may have just calculated several solutions, when in fact your code only wanted to deal with 1 of them.
Hope it helps
Without even getting into the math, you can start by applying some good coding practices to increase the efficiency.
For example, I notice that you have made a user-defined constructor for your vector, which makes it a non-POD type. This can be a very significant loss of performance when doing lots of copying of that class, which is necessarily going to happen when you have things like "std::vector<Vector2>," or when you pass a Vector2 argument by value, as you're doing here. However, there's no reason to pass your Vector2 by value -- you should change that to a const-reference immediately.
Second, I recommend changing your Vector2 class to be POD. I understand this may be an annoyance to you if you really want to do things like,
Vector2 v(1,2);
However with a POD class, you can still use these similar alternatives:
Vector2 v = {{1,2}};
Vector2 v = make_vector2(1,2);
Next, you may want to rethink your "overly-object-centric-oriented-design" philosophy, and just stop using so many "objects" altogether, if you can help it.
I notice that you are returning some objects by value from functions. Luckily for you, the current version of MSVC has NRVO built into it which converts that into a return-by-reference-argument automatically. However, there's still some loss of performance for doing it that way.
It also is encouraging you to "over-calculate" things. For example, an expression like:
"if(io.NumberOfSolutions() == 1)"
Indicates that you may have just calculated several solutions, when in fact your code only wanted to deal with 1 of them.
Hope it helps
Author
I should have changed the title all together when I bumped this topic. The top section is over a year old. I think "2D Intersection Algorithm optimization needed" is a little misleading since that was for the old post.
Impossible. A line-segment to line-segment intersection results in 0, 1 (or infinite solutions, which I don't handle).
Quote:Original post by yahastu
"if(io.NumberOfSolutions() == 1)"
Indicates that you may have just calculated several solutions, when in fact your code only wanted to deal with 1 of them.
Impossible. A line-segment to line-segment intersection results in 0, 1 (or infinite solutions, which I don't handle).
Quote:Original post by SirisianQuote:
Indicates that you may have just calculated several solutions, when in fact your code only wanted to deal with 1 of them.
Impossible. A line-segment to line-segment intersection results in 0, 1 (or infinite solutions, which I don't handle).
I was referring to the Line-Circle example you showed....
Quote:I think "2D Intersection Algorithm optimization needed" is a little misleading since that was for the old post.
If you are not looking to improve the efficiency, then what are you looking for?
Author
Quote:Original post by yahastuQuote:Original post by SirisianQuote:
Indicates that you may have just calculated several solutions, when in fact your code only wanted to deal with 1 of them.
Impossible. A line-segment to line-segment intersection results in 0, 1 (or infinite solutions, which I don't handle).
I was referring to the Line-Circle example you showed....
What did you mean when you quoted "if(io.NumberOfSolutions() == 1)" then? That was only for the LineSegmentToLineSegmentIntersection function. The Line-Circle uses iterators.
Quote:Original post by yahastuQuote:I think "2D Intersection Algorithm optimization needed" is a little misleading since that was for the old post.
If you are not looking to improve the efficiency, then what are you looking for?
Nothing :P Just a simple bump to code dump this for others that might use the search feature on this site or run past it on google. I'm starting to regret bumping my old post instead of making a new one. :) I put them in one namespace a while back because I kept needing them in my C#, AS3, and C++ projects.
Quote:Original post by Sirisian
What did you mean when you quoted "if(io.NumberOfSolutions() == 1)" then? That was only for the LineSegmentToLineSegmentIntersection function. The Line-Circle uses iterators.
I guess that would be the result of quickly skimming over your code. But anyway, I think my point is still valid -- because you do calculate both intersections and return them to the caller, whereas the caller never specified how many intersections were needed.
Thus, a user of your function who only needed 1 intersection, would have to calculate 2 intersections. It's just wasteful computation.
Author
Quote:Original post by yahastuCalculating one intersection is as cheap as calculating both. The algorithm first calculates a midpoint between the intersections then does an offset from it along the line. If you know a method that optimizes this and returns the closest or furthest point then I'd be glad to optimize that part.Quote:Original post by Sirisian
What did you mean when you quoted "if(io.NumberOfSolutions() == 1)" then? That was only for the LineSegmentToLineSegmentIntersection function. The Line-Circle uses iterators.
I guess that would be the result of quickly skimming over your code. But anyway, I think my point is still valid -- because you do calculate both intersections and return them to the caller, whereas the caller never specified how many intersections were needed.
Thus, a user of your function who only needed 1 intersection, would have to calculate 2 intersections. It's just wasteful computation.
[Edited by - Sirisian on January 28, 2009 8:22:10 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
