Jump to content
  • Advertisement
Sign in to follow this  
Pipo DeClown

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.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!