Circle in Triangle intersection
Author
Hey everyone, a little quick question here. How do I test if a circle (2D) is intersecting with a triangle (2D)?
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.
Author
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.
Author
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};Now I'm going to do the if-center-not-in-triangle-but-radius-is check.
.. 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:Original post by faxIf you're referring to Wasting Time's post, than yes it will work; it is exactly the correct solution.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
