View Full Version : Point in triangle ??

TheBlob

11-22-2001, 08:26 AM

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!!

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!!

TheBlob

11-22-2001, 09:37 AM

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!

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!

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).]

Powered by vBulletin® Version 4.2.2 Copyright © 2014 vBulletin Solutions, Inc. All rights reserved.