Circle in Triangle intersection

This topic is 4491 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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

Share on other sites
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 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 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 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 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 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 on other sites
Quote:
 Original post by faxThat 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 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 on other sites
Quote:
 fax wroteThat 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 wroteThe 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.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• Forum Statistics

• Total Topics
633295
• Total Posts
3011243
• Who's Online (See full list)

There are no registered users currently online

×