Segment – 2D convex polygon intersection

 

Introduction

 

this algorithm has many uses, but I’ll focus one collision detection of fast moving particles, such as bullets, and special effects point sprites.

 

first of, imagine you want to model a bullet fired from a gun. the logical way to do it would be

Text Box: class CBullet { Vector Position; Vector Velocity; void Update(float dt) { Position += Velocity * dt; } };
 

 

 

 

 

 

 

 

 


so the bullet will travel along a straight line at a constant velocity. The most basic way of checking is a bullet hit an object (box, polygon, triangle, …), is to check if the bullet is inside the object. For a box, it is straight forward.

 

Text Box: bool Intersect(const Vector &Position, const Vector& BoxMin, const Vector& BoxMax) { if (Position.x < BoxMin.x || Position.x > BoxMax.x) return false; if (Position.y < BoxMin.y || Position.y > BoxMax.y) return false; return true; }
 

 

 

 

 

 

 


I assumed the box is defined by two vectors, which are the two points at a diagonal of the box.

 

ok, so far so good. But for fast bullets, it’s very possible a collision will be miss, as the bullet will ‘leapfrog’ the box.

 

a solution is to consider the bullet as a segment or ray, defined by the bullet’s current position, and the bullet’s prediceted position, as if there were no collisions, and check if anything is intersected in between.

 

This also works for projectiles under the influence of gravity or external forces (such as heat seeking missiles for example). The path of a bullet in a frame is approximated to a segment. This still not 100% accurate (for that, you’d have to consider the curved trajectory of the bullet within the frame), but it’s a lot better than checking a single point, and not difficult to implement.

 

I will explain the general method of intersecting a segment with a polygon. The case of a box and a ray is kind of a special case, but also interesting.

 

The algorithm considered is the standard clipping algorithm, where a ray is ‘cut’ with the edges of the polygon. It has the advantage of giving us both the normal and the points of collision, which is always useful.

 

Segments

 

Segments are described by two points, A and B. A point P is on the infinite line passing through A and B if

 

P = A + (B – A).t,

 

where t is a scalr.

 

now, the point P is on segment A and B if it verifies a similar equation

 

P = A + (B – A).t, t = [0, 1] (t in range [0, 1]).

 

you can see that if t = 0, P = A, and if t = 1, P = B. In between , t = 0.5, then P will be at the middle of segment [AB], and so on….

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Polygons

 

Polygons are a list of connected points, that forms an enclosed area. They come in several forms, but for the principle of collision detection, the most interesting of the bunch are convex polygons.

 

Convex polygons are polygons where every angles between two consecutive edges is less than 180 degrees. When an angle ‘cave-in’, forming an angle > 180 degrees, the polygon is not convex. They are concave.

 

 

 

 

 

 

 

 


you can see the angle at the top-centre of the yellow polygon forming an angle > 180 degrees.

 

So, why do we need to classify concave polygons to convex polygons?

 

the convexity of the polygons brings some interesting properties. For example, imagine a ray crossing a convex polygon. you can see that you will only ever get two intersection point.

 

 

 

 

 

 


if the ray started inside the polygon, you can see that you will only ever get one intersection point.

 

 

 

 

 

 

 

 

 


however, with a concave polygon, the same principle does not quite hold.

 

 

 

 

 

 

 

 

 

 

 


but you can also see that the number of intersections is odd if the start of the ray is inside the polygon, odd if it is outside.

 

this, for example, is used in some algorithm to detect if a point is inside a polygon or not.

 

 

Half-space. what’s that?

 

Convexity has more useful features, and we can use a method called ‘clipping’ very efficiently, since we can reduce clipping against segments to clipping against the infinite line going through the segment.

 

the line going through the segment splits the space in two, called half-space. one called ‘positive’, and one ‘negative’.  therefore, the line is kind of ‘signed’, the direction in which the line is pointing is important.

 

 

 

 

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

In the first picture, the line is pointing down. the positive half space is the portion of the space on the left of the line, while the negative portion is on the right. When the line is pointing up, the spaces are swapped around.

 

the ‘normal’ of the line is a vector that is perpendicular to the line direction, and obeying the right-hand rule. point the thumb of your right hand towards the line direction, and the index will point towards the direction of the normal, towards the positive half space.

 

this rule is more a coordinate system convention, and it’s quite important to stick to it. for example, following the right-hand rule, all convex polygons should have their vertices listed anti-clckwise, so the space enclosed in the polygon is the intersection of all the negative half-space of the lines passing through the edges of the polygons.

 

take for example a triangle, with it’s vertices listed anti-clockwise.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

The inside of the triangle is the intersection of the negative half-space of the line passing through the line [V0, V1], and the negative half-space of the line passing through the line [V1, V2], and finally the negative half-space of the line passing through the line [V2, V0].

 

now, to detect is a point is in the red area, it’s simply a matter of detecting if the point is inside one of the blue areas instead. And if it is, then the point cannot be in the red area.

 

to detect on which side of the line the point lies, you check the sign of the normal of the line dot the segment starting from a point on the line, and going twards the point of interest.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


here, P0 is in the blue area, and if you dot product vector (P0 – V0) and the normal, the product will be positive.

 

P1 is in the negative area, since (P1 – V0) dot Normal will be negative.

 

so, as soon as you find the point in a blue area, you know it cannot be in the polygon area, which is the intersecion of all half-spaces for every edges.

 

 

 

What’s does it have to do with convex polygons?

 

you can see that the algorithm will brake is the polygons where concave.

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

the red areas shows parts of the polygon where the points will be wrongfully detected as not being in the polygon.

 

Point in convex polygon code

 

here is how the code would look like to detect if a point is inside a convex polygon with its vertices listed in a anti-clockwise order.

 

 

Text Box: bool PointInsidePolygon(Vector Point, Vector* Vertices, int VertNum) { for(int j = 2, I = 0; I < VertNum; j = I, I++) { Vector Dir = Vertices[I] – Vertices[j]; Vector Normal(-Dir.y, Dir.x); // normal of edge, obeying the right hand rule Vector D = Point – Vertices[j]; float sign = D.Dot(Normal); // dot product if (sign > 0.0f) // for counter-clockwise polygons. else, test if negative return false; } return true; }
 

 

 

 

 

 

 

 

 

 

 

 

 


How does it works for our segment – polygon intersection test?

 

For a segment cut by a convex polygon, you know you will get two intersection point, a near point and a far point. the near point being the point the closest to the segment origin, the far point the point the closest to the segment’s end.

 

if the segment starts outside, then the intersection point lies in one of the positive half space of the polygon. and the near point will be a point that is the intersection of the segment and a line where the origin lies on the positive half space.

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

Pnear0 and Pnear1 are two candidates for the near point. The right point is the point which is the furthest away from the start position of the ray.

 

for the far point, it is the same principle. the far point will be a point that is the intersection of the segment and a line where the start point lies on the negative half space.

 

 

 

 

 

 

 

 

 

 

 

 

 

 


pfar0 is the point you are looking for, which is this time the point the closest of all the far point candidates.

 

 

how to calculate the intersection of a segment and a line?

 

to calculate the intersection of a segment and a line, we refer to the equation of a segment. P = A + (B – A).t.

 

the point of intersection Q will be a point on that line, so Q = A + (B – A).t

 

and the point of intersection Q is such that (Q – V).N = 0, where V is a vertex of the edge we are trying to intersect, and N is the normal of that edge.

 

so, we have a system of two equations

 

(1)     Q = A + (B – A).t

(2)     (Q – V).N = 0

 

now, we can calculate t, the unkown, by substituting Q from equation 1 into equation (2). the result will be .

 

t = (V – A).N / (B-A).N

 

and you find Q, the point of intersection, by plugging t back into the first equation

 

Q = A + (B – A).t

Putting it all together

 

so, now, we have a method to calculate the points of intersection Pnear and Pfar, which are the intersection of the segment and two of the lines passing through edges of the polygon.

 

the points Pnear and Pfar, have two tnear and tfar scalar values, as calculated by the system of equations above.

 

Pnear = A + (B – A).tnear

Pfar = A + (B – A).tfar

 

to detect if the ray misses the polygon, it’s simply a matter of finding if pfar is smaller than pnear, as demonstrated below.

 

 

 

 

 

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 also, tfar has to be > 0, and tnear has to be < 1, as shown below

 

 

 

 

 

 

 

 

 

 

 

 

 


if one of those conditions fail, then there are no intersection possible.

 

 

Segment – Polygon intersection code

 

Text Box: // clip a ray to a polygon // A : vertices of the polygon // Anum : number of vertices // xStart : start point of the segment // xEnd : end point of the segment. // tnear : near intersection // tfar : far intersection // Nnear : normal at near intersection (if tnear > 0.0f) // tfar : normal at far intersection (it tfar < 1.0f). bool ClipSegment(const Vector* A, int Anum, const Vector& xStart, const Vector& xEnd, float& tnear, float& tfar, Vector& Nnear, Vector& Nfar) { if (!A) return false; Vector xDir = xEnd - xStart; // test separation axes of A for(int j = Anum-1, i = 0; i < Anum; j = i, i ++) { Vector E0 = A[j]; Vector E1 = A[i]; Vector E = E1 - E0; Vector En(E.y, -E.x); Vector D = E0 – xStart; float denom = D * En; float numer = xDir * En; // ray parallel to plane if (fabs(numer) < 1.0E-8f) { // origin outside the plane, no intersection if (denom < 0.0f) return false; } else { float tclip = denom / numer; // near intersection if (numer < 0.0f) { if (tclip > tfar) return false; if (tclip > tnear) { tnear = tclip; Nnear = En; Nnear.Normalise(); } } // far intersection else { if (tclip < tnear) return false; if (tclip < tfar) { tfar = tclip; Nfar = En; Nfar.Normalise(); } } } } return true; }
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


So there you have it

 

an algo that detects if a segment intersects a convex polygon. Note that the code above returns the normal of the intersection at both points. That is if the ray actually intersects at the near and far plane. the ray origin might laredy be in the polygon, in that case, tnear will be 0.0f, but the normal Nnear will be undefined. Similarly for tfar = 1.0f, that is if the end point is inside the polygon, the normal Nfar will be undefined.

 

also, before calling the algorithm, tnear and tfar have to be initialised to respectively 0.0f and 1.0f. This algorithm can be used therefore as a mean to find the very first point of intersection and the very last point of intersection, when testing a ray against multiple polygons.