Re: [algogeeks] Re: plz give some efficient method to find out if a point lies inside or outside the triangle?
Join the given point with all the vertices of the triangle and calculate the
area of each of the three sub-triangles thus formed
now compare the area of original triangle with the sum of the area of those
3 triangles
if that comes out to be equal, then the point lies inside
otherwise not.
On Fri, Jul 29, 2011 at 1:34 AM, Don dondod...@gmail.com wrote:
// True if point (x,y) is above line defined by two points
// If line is vertical, above is defined as to the right
bool above(double lx1, double ly1, double lx2, double ly2, double x,
double y)
{
return (lx1 != lx2) ? (y (ly1+(x-lx1)*(ly2-ly1)/(lx2-lx1))) : (x
lx1);
}
// True if point 1 and point 2 are on the same side of the line
defined by l1 and l2
bool sameSide(double lx1, double ly1, double lx2, double ly2, double
px1, double py1, double px2, double py2)
{
return above(lx1, ly1, lx2, ly2, px1, py1) == above(lx1, ly1, lx2,
ly2, px2, py2);
}
// True if point (x,y) is inside triangle
bool pointInTriangle(double x1, double y1, double x2, double y2,
double x3, double y3, double x, double y)
{
return sameSide(x1,y1,x2,y2,x,y,x3,y3)
sameSide(x1,y1,x3,y3,x,y,x2,y2)
sameSide(x2,y2,x3,y3,x,y,x1,y1);
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: plz give some efficient method to find out if a point lies inside or outside the triangle?
That should work, but I'd bet that my method is faster.
Don
On Jul 29, 6:02 am, Udit Gupta uditgupta...@gmail.com wrote:
Join the given point with all the vertices of the triangle and calculate the
area of each of the three sub-triangles thus formed
now compare the area of original triangle with the sum of the area of those
3 triangles
if that comes out to be equal, then the point lies inside
otherwise not.
On Fri, Jul 29, 2011 at 1:34 AM, Don dondod...@gmail.com wrote:
// True if point (x,y) is above line defined by two points
// If line is vertical, above is defined as to the right
bool above(double lx1, double ly1, double lx2, double ly2, double x,
double y)
{
return (lx1 != lx2) ? (y (ly1+(x-lx1)*(ly2-ly1)/(lx2-lx1))) : (x
lx1);
}
// True if point 1 and point 2 are on the same side of the line
defined by l1 and l2
bool sameSide(double lx1, double ly1, double lx2, double ly2, double
px1, double py1, double px2, double py2)
{
return above(lx1, ly1, lx2, ly2, px1, py1) == above(lx1, ly1, lx2,
ly2, px2, py2);
}
// True if point (x,y) is inside triangle
bool pointInTriangle(double x1, double y1, double x2, double y2,
double x3, double y3, double x, double y)
{
return sameSide(x1,y1,x2,y2,x,y,x3,y3)
sameSide(x1,y1,x3,y3,x,y,x2,y2)
sameSide(x2,y2,x3,y3,x,y,x1,y1);
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: plz give some efficient method to find out if a point lies inside or outside the triangle?
area of 3 triangles being formed by joining the point to 3 vertices can be
float n when we add the 3 areas, the sum wud also be float. and this is to b
compared with original area
don't u think the problem wud arise in comparing the floats?
wud that give right ans??
On Fri, Jul 29, 2011 at 9:06 PM, Don dondod...@gmail.com wrote:
That should work, but I'd bet that my method is faster.
Don
On Jul 29, 6:02 am, Udit Gupta uditgupta...@gmail.com wrote:
Join the given point with all the vertices of the triangle and calculate
the
area of each of the three sub-triangles thus formed
now compare the area of original triangle with the sum of the area of
those
3 triangles
if that comes out to be equal, then the point lies inside
otherwise not.
On Fri, Jul 29, 2011 at 1:34 AM, Don dondod...@gmail.com wrote:
// True if point (x,y) is above line defined by two points
// If line is vertical, above is defined as to the right
bool above(double lx1, double ly1, double lx2, double ly2, double x,
double y)
{
return (lx1 != lx2) ? (y (ly1+(x-lx1)*(ly2-ly1)/(lx2-lx1))) : (x
lx1);
}
// True if point 1 and point 2 are on the same side of the line
defined by l1 and l2
bool sameSide(double lx1, double ly1, double lx2, double ly2, double
px1, double py1, double px2, double py2)
{
return above(lx1, ly1, lx2, ly2, px1, py1) == above(lx1, ly1, lx2,
ly2, px2, py2);
}
// True if point (x,y) is inside triangle
bool pointInTriangle(double x1, double y1, double x2, double y2,
double x3, double y3, double x, double y)
{
return sameSide(x1,y1,x2,y2,x,y,x3,y3)
sameSide(x1,y1,x3,y3,x,y,x2,y2)
sameSide(x2,y2,x3,y3,x,y,x1,y1);
}
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: plz give some efficient method to find out if a point lies inside or outside the triangle?
Yeah, the comparison of two floats will be a problem as the behaviour is
undefined and depends on the machine architecture and compiler.
Thanks Regards,
Prashant Bhutani
Senior Undergraduate
Computer Science Engineering (B.Tech)
Institute of Technology - BHU (IT-BHU)
Varanasi-221005
On Fri, Jul 29, 2011 at 11:43 PM, tech rascal techrascal...@gmail.comwrote:
area of 3 triangles being formed by joining the point to 3 vertices can be
float n when we add the 3 areas, the sum wud also be float. and this is to b
compared with original area
don't u think the problem wud arise in comparing the floats?
wud that give right ans??
On Fri, Jul 29, 2011 at 9:06 PM, Don dondod...@gmail.com wrote:
That should work, but I'd bet that my method is faster.
Don
On Jul 29, 6:02 am, Udit Gupta uditgupta...@gmail.com wrote:
Join the given point with all the vertices of the triangle and calculate
the
area of each of the three sub-triangles thus formed
now compare the area of original triangle with the sum of the area of
those
3 triangles
if that comes out to be equal, then the point lies inside
otherwise not.
On Fri, Jul 29, 2011 at 1:34 AM, Don dondod...@gmail.com wrote:
// True if point (x,y) is above line defined by two points
// If line is vertical, above is defined as to the right
bool above(double lx1, double ly1, double lx2, double ly2, double x,
double y)
{
return (lx1 != lx2) ? (y (ly1+(x-lx1)*(ly2-ly1)/(lx2-lx1))) : (x
lx1);
}
// True if point 1 and point 2 are on the same side of the line
defined by l1 and l2
bool sameSide(double lx1, double ly1, double lx2, double ly2, double
px1, double py1, double px2, double py2)
{
return above(lx1, ly1, lx2, ly2, px1, py1) == above(lx1, ly1, lx2,
ly2, px2, py2);
}
// True if point (x,y) is inside triangle
bool pointInTriangle(double x1, double y1, double x2, double y2,
double x3, double y3, double x, double y)
{
return sameSide(x1,y1,x2,y2,x,y,x3,y3)
sameSide(x1,y1,x3,y3,x,y,x2,y2)
sameSide(x2,y2,x3,y3,x,y,x1,y1);
}
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: plz give some efficient method to find out if a point lies inside or outside the triangle?
You just need some comparison which determines if they are very close
to equal. You can't expect them to be exactly equal in all 64 bits.
Something like this should be fine:
bool isClose(double a, double b)
{
const double epsilon = 1.001;
return (a b*epsilon) (b a*epsilon);
}
(Note that this assumes positive values.)
Don
On Jul 29, 1:21 pm, prashant bhutani prashantbhutani2...@gmail.com
wrote:
Yeah, the comparison of two floats will be a problem as the behaviour is
undefined and depends on the machine architecture and compiler.
Thanks Regards,
Prashant Bhutani
Senior Undergraduate
Computer Science Engineering (B.Tech)
Institute of Technology - BHU (IT-BHU)
Varanasi-221005
On Fri, Jul 29, 2011 at 11:43 PM, tech rascal techrascal...@gmail.comwrote:
area of 3 triangles being formed by joining the point to 3 vertices can be
float n when we add the 3 areas, the sum wud also be float. and this is to b
compared with original area
don't u think the problem wud arise in comparing the floats?
wud that give right ans??
On Fri, Jul 29, 2011 at 9:06 PM, Don dondod...@gmail.com wrote:
That should work, but I'd bet that my method is faster.
Don
On Jul 29, 6:02 am, Udit Gupta uditgupta...@gmail.com wrote:
Join the given point with all the vertices of the triangle and calculate
the
area of each of the three sub-triangles thus formed
now compare the area of original triangle with the sum of the area of
those
3 triangles
if that comes out to be equal, then the point lies inside
otherwise not.
On Fri, Jul 29, 2011 at 1:34 AM, Don dondod...@gmail.com wrote:
// True if point (x,y) is above line defined by two points
// If line is vertical, above is defined as to the right
bool above(double lx1, double ly1, double lx2, double ly2, double x,
double y)
{
return (lx1 != lx2) ? (y (ly1+(x-lx1)*(ly2-ly1)/(lx2-lx1))) : (x
lx1);
}
// True if point 1 and point 2 are on the same side of the line
defined by l1 and l2
bool sameSide(double lx1, double ly1, double lx2, double ly2, double
px1, double py1, double px2, double py2)
{
return above(lx1, ly1, lx2, ly2, px1, py1) == above(lx1, ly1, lx2,
ly2, px2, py2);
}
// True if point (x,y) is inside triangle
bool pointInTriangle(double x1, double y1, double x2, double y2,
double x3, double y3, double x, double y)
{
return sameSide(x1,y1,x2,y2,x,y,x3,y3)
sameSide(x1,y1,x3,y3,x,y,x2,y2)
sameSide(x2,y2,x3,y3,x,y,x1,y1);
}
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: plz give some efficient method to find out if a point lies inside or outside the triangle?
@don: is what I have mentioned above almost the same as the method u r
saying?
On Fri, Jul 29, 2011 at 9:16 PM, Don dondod...@gmail.com wrote:
You just need some comparison which determines if they are very close
to equal. You can't expect them to be exactly equal in all 64 bits.
Something like this should be fine:
bool isClose(double a, double b)
{
const double epsilon = 1.001;
return (a b*epsilon) (b a*epsilon);
}
(Note that this assumes positive values.)
Don
On Jul 29, 1:21 pm, prashant bhutani prashantbhutani2...@gmail.com
wrote:
Yeah, the comparison of two floats will be a problem as the behaviour is
undefined and depends on the machine architecture and compiler.
Thanks Regards,
Prashant Bhutani
Senior Undergraduate
Computer Science Engineering (B.Tech)
Institute of Technology - BHU (IT-BHU)
Varanasi-221005
On Fri, Jul 29, 2011 at 11:43 PM, tech rascal techrascal...@gmail.com
wrote:
area of 3 triangles being formed by joining the point to 3 vertices can
be
float n when we add the 3 areas, the sum wud also be float. and this is
to b
compared with original area
don't u think the problem wud arise in comparing the floats?
wud that give right ans??
On Fri, Jul 29, 2011 at 9:06 PM, Don dondod...@gmail.com wrote:
That should work, but I'd bet that my method is faster.
Don
On Jul 29, 6:02 am, Udit Gupta uditgupta...@gmail.com wrote:
Join the given point with all the vertices of the triangle and
calculate
the
area of each of the three sub-triangles thus formed
now compare the area of original triangle with the sum of the area
of
those
3 triangles
if that comes out to be equal, then the point lies inside
otherwise not.
On Fri, Jul 29, 2011 at 1:34 AM, Don dondod...@gmail.com wrote:
// True if point (x,y) is above line defined by two points
// If line is vertical, above is defined as to the right
bool above(double lx1, double ly1, double lx2, double ly2, double
x,
double y)
{
return (lx1 != lx2) ? (y (ly1+(x-lx1)*(ly2-ly1)/(lx2-lx1))) :
(x
lx1);
}
// True if point 1 and point 2 are on the same side of the line
defined by l1 and l2
bool sameSide(double lx1, double ly1, double lx2, double ly2,
double
px1, double py1, double px2, double py2)
{
return above(lx1, ly1, lx2, ly2, px1, py1) == above(lx1, ly1,
lx2,
ly2, px2, py2);
}
// True if point (x,y) is inside triangle
bool pointInTriangle(double x1, double y1, double x2, double y2,
double x3, double y3, double x, double y)
{
return sameSide(x1,y1,x2,y2,x,y,x3,y3)
sameSide(x1,y1,x3,y3,x,y,x2,y2)
sameSide(x2,y2,x3,y3,x,y,x1,y1);
}
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Arun Vish
Graduate Student
Department of Computer Science
University of Southern California
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: plz give some efficient method to find out if a point lies inside or outside the triangle?
A point is inside a triangle iff: for each pair of vertices of the triangle, the point is on the same side of the line defined by those points as the third vertex of the triangle. Don On Jul 28, 1:47 pm, tech rascal techrascal...@gmail.com wrote: -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: plz give some efficient method to find out if a point lies inside or outside the triangle?
// True if point (x,y) is above line defined by two points
// If line is vertical, above is defined as to the right
bool above(double lx1, double ly1, double lx2, double ly2, double x,
double y)
{
return (lx1 != lx2) ? (y (ly1+(x-lx1)*(ly2-ly1)/(lx2-lx1))) : (x
lx1);
}
// True if point 1 and point 2 are on the same side of the line
defined by l1 and l2
bool sameSide(double lx1, double ly1, double lx2, double ly2, double
px1, double py1, double px2, double py2)
{
return above(lx1, ly1, lx2, ly2, px1, py1) == above(lx1, ly1, lx2,
ly2, px2, py2);
}
// True if point (x,y) is inside triangle
bool pointInTriangle(double x1, double y1, double x2, double y2,
double x3, double y3, double x, double y)
{
return sameSide(x1,y1,x2,y2,x,y,x3,y3)
sameSide(x1,y1,x3,y3,x,y,x2,y2)
sameSide(x2,y2,x3,y3,x,y,x1,y1);
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
