Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Does anyone know of a way I could add a radius to this code for p? Like basically saying "this is true if the triangle is < N dist from the point"

public boolean isPointInTriangle( Vector3f p, Vector3f a, Vector3f b, Vector3f c )
{
    return ( pointsAreOnSameSide(p, a, b, c) && pointsAreOnSameSide(p, b, a, c) && pointsAreOnSameSide(p, c, a, b) );
}

public boolean pointsAreOnSameSide( Vector3f p1, Vector3f p2, Vector3f a, Vector3f b )
{
    Vector3f diffba = new Vector3f(0,0,0);
    Vector3f.sub( b, a, diffba );
    Vector3f diffp1a = new Vector3f(0,0,0);
    Vector3f.sub( p1, a, diffp1a );
    Vector3f diffp2a = new Vector3f(0,0,0);
    Vector3f.sub( p2, a, diffp2a );

    Vector3f cross1 = Vector3f.cross(diffba, diffp1a);
    Vector3f cross2 = Vector3f.cross(diffba, diffp2a);

    return ( Vector3f.dot( cross1, cross2 ) >= 0 );
}
share|improve this question
    
All 3 points of the triangle are to be inside the radius? –  Byte56 Jun 28 '12 at 4:20
    
Hmm, I think I'd need something like any point, or edge. Oh man, what about if it's in the middle of a huge triangle? How would I even go about figuring that out? –  CyanPrime Jun 28 '12 at 4:23
    
For any point you can simply check the distance for each point. Otherwise you can check the center of the triangle. For seeing if an edge crosses within the radius, I don't know. –  Byte56 Jun 28 '12 at 4:25
    
This is nice for calculating collisions only on objects near you :-) –  danijar Jun 28 '12 at 9:22
add comment

2 Answers

up vote 2 down vote accepted

First, calculate the centroid of your triangle:

// the centroid is the average of the three points and is always the
// point in which the triangle is balanced
Vector3f centroid = (a + b + c) / 3;

Then, put it in the formula:

public boolean checkDistanceToTriangle(Vector3f a_Centroid, Vector3f a_Point, float a_Distance)
{
    // i'm just guessing that the length function exists
    // .length returns the magnitude between a_Centroid and a_Point
    return (Vector3f.length(a_Centroid - a_Point) < a_Distance);
}
share|improve this answer
    
Is .length the magnitude? or just a add/sub call? –  CyanPrime Jun 28 '12 at 4:29
    
a_Distance is a vector3? how would I calculate if a_distance is < a vector, or a vector's length? with a length call of a_Distance's own? –  CyanPrime Jun 28 '12 at 4:31
    
Woops, made a mistake there. a_Distance should be a float. Yes, .length is the magnitude of the distance between the point and the centroid. –  knight666 Jun 28 '12 at 4:41
1  
What about a triangle where either the points or the controid but an edge crosses the distance zone? –  danijar Jun 28 '12 at 9:20
add comment

For completeness, there are plenty of situations that knight666's answer misses. For example testing just the center of the triangle would miss this case:

enter image description here

And this case:

enter image description here

And this case:

enter image description here

To test all the cases, you need to check:

  • If the circle center is contained in the triangle
  • Test each edge of the triangle to see if it passes through the circle
  • Test each vertex of the triangle to see if it's contained within the circle

Those can all be short circuited, so you can return true as soon as one case is detected. So you can sort them by complexity.

You can find an excellent article about triangle circle intersection here.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.