# [C++ Code Update] 2D Intersection Algorithms

This topic is 3608 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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:
[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_)
{
}

public void InsertSolution(Vector2 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;
}
}
}


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]

##### Share on other sites
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).

##### Share on other sites
Quote:
 Original post by jykCould 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.

##### Share on other sites
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:
#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)
}

##### Share on other sites
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

##### Share on other sites
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.

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).

##### Share on other sites
Quote:
Original post by Sirisian
Quote:
 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?

##### Share on other sites
Quote:
Original post by yahastu
Quote:
Original post by Sirisian
Quote:
 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 yahastu
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?

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.

##### Share on other sites
Quote:
 Original post by SirisianWhat 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.

##### Share on other sites
Quote:
Original post by yahastu
Quote:
 Original post by SirisianWhat 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.
Calculating 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.

[Edited by - Sirisian on January 28, 2009 8:22:10 PM]

1. 1
2. 2
Rutin
17
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633735
• Total Posts
3013597
×