CODEWITHSUNDEEP
java
nerdy_me
nerdy_me

Reputation: 501

How will we find number of points inside a triangle?

I want to find total no. of points lying inside and on the boundaries of a triangle if we are given with the x and y co-ordinate of all the three vertices in the 2D cartesian plane. I am thinking of enclosing the triangle inside a rectangle and then , find straight line equations and will check the points one by one to satisfy inequality equations. Is there a better computational approach to solve this problem?

Please help me.

Upvotes: 0

Views: 197

Answers (2)

Ben Taitelbaum
Ben Taitelbaum

Reputation: 7403

Check out the PointInPolygon description at http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry3 for a good summary of the general case of testing if a point is in a polygon. Since you have a triangle, which is always convex, this simplifies to (pseudocode):

for point in test_points:
  //infinity can just be a point outside the bounding box of the triangle
  ray := line from point to infinity 
  intersection_points := 0

  for side in triangle_sides
    isect := intersection ray, side
    intersection_points++ if isect

  return intersection_points %2 == 1

Upvotes: 0

huseyin tugrul buyukisik
huseyin tugrul buyukisik

Reputation: 11910

You take cross-product of all combinations of 3-triange edge vectors. If the resulting vectors' direction is not same with an result of cross-product of the vector to point p and the vector to one of triangle points(A,B or C), then p is not in the triangle.(cross product will be resulting in 3D)

More detailed explanations: http://www.blackpawn.com/texts/pointinpoly/default.html

Upvotes: 1

Related Questions