Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Results 1 to 5 of 5

Thread: Point in triangle ??

  1. #1
    Intern Contributor
    Join Date
    May 2001
    Location
    Hamburg, Germany
    Posts
    63

    Point in triangle ??

    Hi!
    My problem is:
    I want to test, if a point/vector(x|y) is within a specified triangle with the points A,B,C. I need a precise solution for that, so not a bounding-sphere...
    Please help!!

  2. #2
    Guest

    Re: Point in triangle ??

    Ther are quite a feW slusions for this problem . i like the parametric approach. So what u goto
    do is think of this point as point on surface, So u will have two parametrs say U and V and three vertices plus the point (you don't know if it is inside or outside) . so u can solve for U and V if U and V are between o and 1 you can say the point isinside the triangle. I guess i have the code for that i can give it u if u need it. Tell me what do u think

    Originally posted by TheBlob:
    Hi!
    My problem is:
    I want to test, if a point/vector(x|y) is within a specified triangle with the points A,B,C. I need a precise solution for that, so not a bounding-sphere...
    Please help!!

  3. #3
    Intern Contributor
    Join Date
    May 2001
    Location
    Hamburg, Germany
    Posts
    63

    Re: Point in triangle ??

    Thanks, i would really appreciate, if you could post some code!!
    But what purpose have the parameters U and V?? Please explain...i think your solution sounds very good. Iīve seen something with trigo-functions, but i think itīs too slow!

  4. #4
    Guest

    Re: Point in triangle ??

    I guess u can use this code
    // Here u and v are alpha and beta

    void IMF_MESHPNT_find_u_v_triangle(ure_array original_location,ure_array *vertex, double*alpha,double*beta)
    {
    double numerator;
    double denominator;
    int alpha_beta_found=0; // This flag is set to 1 if the point happens to be on the node
    int ii,jj; // Counter for for

    float tol;

    // Loop over three vertices of triangle
    for(ii=0;ii<3;ii++){
    // IMPORTANT: The tolarance is 1e-03 (!!!!!)
    // This one to see of th epoint is on one of the vertices
    if(vertex[ii].almostEqual(original_location,1e-03)){

    switch ( ii ) {
    case 0:
    *alpha=0;
    *beta=0;
    break;

    case 1:
    *alpha=1;
    *beta=0;
    break;

    case 2:
    *alpha=1;
    *beta=1;
    break;

    default:
    break;
    }
    alpha_beta_found=1;
    }
    }



    if(!alpha_beta_found){
    numerator = ((vertex[2][1] - vertex[1][1])*(original_location[0]- vertex[0][0])) -
    ((original_location[1] - vertex[0][1]) * (vertex[2][0] - vertex[1][0]));
    denominator=((vertex[1][0] - vertex[0][0])*(vertex[2][1] - vertex[1][1])) -
    ((vertex[2][0] - vertex[1][0])*(vertex[1][1] - vertex[0][1]));
    *alpha = numerator/denominator;

    numerator = original_location[0] - vertex[0][0] -
    (vertex[1][0] - vertex[0][0])*(*alpha);
    denominator = (*alpha)*(vertex[2][0] - vertex[1][0]);
    *beta=numerator/denominator;
    }
    }

    Originally posted by TheBlob:
    Thanks, i would really appreciate, if you could post some code!!
    But what purpose have the parameters U and V?? Please explain...i think your solution sounds very good. Iīve seen something with trigo-functions, but i think itīs too slow!

  5. #5
    Junior Member Regular Contributor
    Join Date
    May 2001
    Location
    Germany, Hannover
    Posts
    160

    Re: Point in triangle ??

    dont know if it is correct, but it should be what i used:


    VECTOR vector1= b-a
    VECTOR vector2= c-a
    VECTOR point= p-a
    float u= vector1*point / (vector1.size*point.size)
    float v= vector2*point / (vector2.size*point.size)

    if(u*v <= 1) inside else outside

    p is your point, and have to be on the surface of the triangle, if you dont know how the get this point, ask, but in 2d it is always ...

    [This message has been edited by T2k (edited 11-24-2001).]

    [This message has been edited by T2k (edited 11-24-2001).]

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •