Jump to content
  • Advertisement
Sign in to follow this  
Sirisian

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

If you intended to correct an error in the post then please contact us.

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



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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by yahastu
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.
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]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!