Original Post
Hey everyone, a little quick question here. How do I test if a circle (2D) is intersecting with a triangle (2D)?
🔒 Locked
Circle in Triangle intersection
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.
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.
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.
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?
I want to make sure this works first.
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.
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.
Okay, I found the flaw. It was not in the above code, but in the Crossproduct code.
Now I'm going to do the if-center-not-in-triangle-but-radius-is check.
.. Done.
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};.. Done.
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) ...
2. point to segment (edges of triangle)
then, using closest point p to segment AB (a,B) ...
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.
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.
Quote:If you're referring to Wasting Time's post, than yes it will work; it is exactly the correct solution.
Original post by fax
That actually wont work
It may be though that you just misunderstood his post, since your proposed solution is just a different expression of the same idea.
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
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.
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; }
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.
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.
I believe that the original post said:
but was fixed after I pointed out the mistake, sorry for the misunderstanding.
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).
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.
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.
Topic Locked
This topic has been locked by a moderator. New replies are not allowed.
Sign in to reply to this topic.
Advertisement