• Advertisement
Sign in to follow this  

Circle in Triangle intersection

This topic is 4229 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

Hey everyone, a little quick question here. How do I test if a circle (2D) is intersecting with a triangle (2D)?

Share this post


Link to post
Share on other sites
Advertisement
Compute the distance from the circle center to the triangle. If that distance is smaller than the circle radius, then the circle and triangle intersect.

Share this post


Link to post
Share on other sites
That actually wont work,

You need to check if the center of the circle is inside the triangle.
if its not then check if the distance from the center of the circle to each of the line segments that makes up the triangle is less than the radius of the circle.

Share this post


Link to post
Share on other sites
I used this piece of code to check wheter the center of te circle (cP) is on the inside of the triangle (tA, tB, tC). However, when I test some other triangles that definitely should be intersecting with the circle, they return positive! Is there a flaw in this code?

    COLLIB2D_VECTOR2D cP = {A->X,  A->Y}; // CircleCenter
COLLIB2D_VECTOR2D tA = {B->X1, B->Y1}; // Triangle Points
COLLIB2D_VECTOR2D tB = {B->X2, B->Y2};
COLLIB2D_VECTOR2D tC = {B->X3, B->Y3};

COLLIB2D_VECTOR2D cp1 = (tB-tA).Cross( cP-tA ); // First check: point on inside?
COLLIB2D_VECTOR2D cp2 = (tB-tA).Cross( tC-tA );
if(cp1.Dot(cp2) >= 0)
{
cp1 = (tC-tB).Cross( cP-tB ); // Second check: point on inside?
cp2 = (tC-tB).Cross( tA-tB );
if(cp1.Dot(cp2) >= 0)
{
cp1 = (tA-tC).Cross( cP-tC ); // Third check: point on inside?
cp2 = (tA-tC).Cross( tB-tC );
if(cp1.Dot(cp2) >= 0)
{
return COLLIB2D_TRUE;
}
}
}





I want to make sure this works first.

Share this post


Link to post
Share on other sites
Id write a test program that lets you graphically view what the return value of the function is by setting the color of the triangle for example, and lets you also move the circle, change its radius and position each vertex of the triangle.

Share this post


Link to post
Share on other sites
Okay, I found the flaw. It was not in the above code, but in the Crossproduct code.

COLLIB2D_VECTOR2D v = {x*b.y-y*b.x, b.x*x-b.y*y}; // wrong
COLLIB2D_VECTOR2D v = {x*b.y-y*b.x, b.x*y-b.y*x};


Now I'm going to do the if-center-not-in-triangle-but-radius-is check.

.. Done.

Share this post


Link to post
Share on other sites
There are 7 Voronoi regions you need to check ... the centre, the edges, and the points.

1. Centre of triangle (point in triangle)
From my favourite book, 'real-time collision detection'
point p, couterclockwise triangle ABC (a,b,c) ...


if(cross(p - a, b - a) < 0.0f) return false;
if(cross(p - b, c - b) < 0.0f) return false;
if(cross(p - c, a - c) < 0.0f) return false;
return true;



2. point to segment (edges of triangle)
then, using closest point p to segment AB (a,B) ...


Vector ab = b - a;
float t = dot(p - a, ab) / dot(ab, ab);
if(t < 0.0f) t = 0.0f;
if(t > 1.0f) t = 1.0f;
return t;



if you do that for all 3 edges and check the distance against the circle, you're almost there ...
just need to check the cases where t = 0 or 1 - ie, the closest point in an endpoint - then you need to do a point-point test.

Share this post


Link to post
Share on other sites
Quote:
Original post by fax
That actually wont work
If you're referring to Wasting Time's post, than yes it will work; it is exactly the correct solution.

It may be though that you just misunderstood his post, since your proposed solution is just a different expression of the same idea.

Share this post


Link to post
Share on other sites

The test may not be as trivial as it seems ie. distance of a point to a triangle. There are several things to be considered, distance to each of the edges and then distance to each of the corners.

You can draw a sketch on the paper and see that if you just use the distance to the edge, there are cases where the distance of the circle to the triangle is less than 0 (although the circle might be a mile away).

Cheers

Share this post


Link to post
Share on other sites
Quote:
fax wrote
That actually wont work,

You need to check if the center of the circle is inside the triangle.
if its not then check if the distance from the center of the circle to each of the line segments that makes up the triangle is less than the radius of the circle.


The standard implementation of point-to-triangle distance assumes the triangle is a "solid". You are treating the triangle as if it is a wireframe. In the standard implementation, if the point is inside (or on) the triangle, the distance is zero.

Quote:
Demus79 wrote
The test may not be as trivial as it seems ie. distance of a point to a triangle. There are several things to be considered, distance to each of the edges and then distance to each of the corners.

You can draw a sketch on the paper and see that if you just use the distance to the edge, there are cases where the distance of the circle to the triangle is less than 0 (although the circle might be a mile away).


You are making the same assumption that "fax" does--a wireframe triangle.

It is easy enough to search the web and find point-to-triangle distance code.

Share this post


Link to post
Share on other sites
Quote:
If you're referring to Wasting Time's post, than yes it will work; it is exactly the correct solution.

Wasting Time's solution will not work in some cases, firstly a triangle has hundreds of different centers but if you chose any fixed point inside the triangle then the circle can be positioned in such a way that it is intersecting the tringle but the algorithm will not return true, for example: if you had a long thin triangle (longer than the diameter of the circle) and the circle was close to the further away vertex.

Quote:
The standard implementation of point-to-triangle distance assumes the triangle is a "solid". You are treating the triangle as if it is a wireframe. In the standard implementation, if the point is inside (or on) the triangle, the distance is zero.

I dont actually suggest using the distance from the center of the circle to the triangle for the collision detection test.
What I was describing takes first a point/triangle test then a circle/wireframe triangle test which in combination handles every case.

Since some code would probably make more sense than my explanation heres my implementation of what I was describing from line 12 onwards:


int SphereIntersectsTriangle(CVector sphere_center, float radius, CVector A, CVector B, CVector C, CVector N, float d) {
float k = d-sphere_center.Dot(N);
CVector center_projected_onto_triangle = sphere_center+N*k;

float radius_at_projected_point_squared = radius*radius-(sphere_center-center_projected_onto_triangle).Norm();

// Check that the sphere intersects the triangles plane
if(radius_at_projected_point_squared < 0)
return 0;


////////////////// From here on its just circle a triangle intersection test:

// Check if the point is inside the triangle
if(BPPointInTriangle(center_projected_onto_triangle, A, B, C))
return 1;

// check if the projected point is close enough to any of the triangles edges
k = ClosestPointOnLineToPoint(A, B, center_projected_onto_triangle);
if(k < 0)
k = 0;
else if(k > 1)
k = 1;
if((A + (B-A)*k - center_projected_onto_triangle).Norm() < radius_at_projected_point_squared)
return 1;

k = ClosestPointOnLineToPoint(B, C, center_projected_onto_triangle);
if(k < 0)
k = 0;
else if(k > 1)
k = 1;
if((B + (C-B)*k - center_projected_onto_triangle).Norm() < radius_at_projected_point_squared)
return 1;

k = ClosestPointOnLineToPoint(C, A, center_projected_onto_triangle);
if(k < 0)
k = 0;
else if(k > 1)
k = 1;
if((C + (A-C)*k - center_projected_onto_triangle).Norm() < radius_at_projected_point_squared)
return 1;

return 0;
}


Share this post


Link to post
Share on other sites
fax, you still are not getting it.

Treating the triangles as a solid (= interior + edges), the distance from a point to the triangle will always give you enough information to determine if the circle and triangle overlap. A triangle might have "hundreds of different centers" but none of these have anything to do with computing the distance from a point to the triangle. When the point is inside the triangle, the distance algorithm returns zero, which is effectively a point-in-triangle test.

Your posted code involves 3D calculations. You did notice that "Pipo DeClown" asked about a 2D problem?

You wrote: "I dont actually suggest using the distance from the center of the circle to the triangle for the collision detection test.
What I was describing takes first a point/triangle test then a circle/wireframe triangle test which in combination handles every case."

Checking if a point is inside the triangle and, if it is not, computing the "circle/wireframe" test *IS* equivalent to computing the distance from the center of the circle to the triangle.

Share this post


Link to post
Share on other sites
I believe that the original post said:
Quote:
Original post by Wasting Time
Compute the distance from the circle to the center of the triangle. If that distance is smaller than the circle radius, then the circle and triangle intersect.

but was fixed after I pointed out the mistake, sorry for the misunderstanding.

Quote:
Original post by Wasting Time
Your posted code involves 3D calculations. You did notice that "Pipo DeClown" asked about a 2D problem?

I realise this which is why I said to read from line 12 onwards, I just left the rest in for context, but the 3D code is applicable to 2D (just set the z component of all the vectors to 0).

Quote:
Original post by Wasting Time
Checking if a point is inside the triangle and, if it is not, computing the "circle/wireframe" test *IS* equivalent to computing the distance from the center of the circle to the triangle.

Its only equivalent to doing that and checking the radius is greater than or equal to that distance, because distance is never calculated unless required in the method I suggested.

Share this post


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

  • Advertisement