Find points on triangle

Question

I have 3 vertices of a triangle and I'm trying to find all the integer points that lie on the inside and ON THE SIDES of the triangle. I've tried numerous methods and they all succeed in finding the inside points, but fail in finding the points on the sides of the triangle. Currently I'm using barycentric coordinates:

      private static boolean pointInTriangle(int[] p, int[] c1, int[] c2, int[] c3){

      float alpha = ((c2[1] - c3[1])*(p[0] - c3[0]) + (c3[0] - c2[0])*(p[1] - c3[1])) /
                ((c2[1] - c3[1])*(c1[0] - c3[0]) + (c3[0] - c2[0])*(c1[1] - c3[1]));
      float beta = ((c3[1] - c1[1])*(p[0] - c3[0]) + (c1[0] - c3[0])*(p[1] - c3[1])) /
               ((c2[1] - c3[1])*(c1[0] - c3[0]) + (c3[0] - c2[0])*(c1[1] - c3[1]));
      float gamma = 1.0f - alpha - beta;

      return ( (alpha>=0.0f) && (beta>=0.0f) && (gamma>=0.0f) );

For example, for vertices (0,0),(0,10),(10,10) this does find (10,8) but it also finds (11,8) which is not correct.

Can somebody help me?

Thanks in advance!

http://gamedev.stackexchange.com/questions/23743/whats-the-most-efficient-way-to-find-barycentric-coordinates — Naman, Feb 27 '17 at 15:43
Duplicate: http://stackoverflow.com/questions/14669614/finding-whether-a-point-is-within-a-triangle — MrApnea, Feb 27 '17 at 15:54
Another one: http://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle — MrApnea, Feb 27 '17 at 15:55
Possible duplicate of [Finding whether a point is within a triangle](http://stackoverflow.com/questions/14669614/finding-whether-a-point-is-within-a-triangle) — MrApnea, Feb 27 '17 at 15:58
Possible duplicate of [How to determine if a point is in a 2D triangle?](http://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle) — Naman, Feb 27 '17 at 15:58
It's not a duplicate lol read the question first, all those methods work for points inside the triangle. I also want to find the points on the triangle — Ayk96, Feb 27 '17 at 18:07
Sorry @Ayk96, will write an answer. Duplicate suggestion was a bit quick. — MrApnea, Feb 28 '17 at 06:33

score 1 · Accepted Answer · answered Feb 28 '17 at 06:37

Use the code you alreay have to find if a position is inside the triangle. Then for the other part, if a point is on the line or not..

I would do it like this..

Check by calculating the distance between 2 vertices at a time. Lets say we have vertices a, b and c. And the point p.

Check if p is on the line between a and b.

This can be done by measuring the distance between a -> p and p -> b.

If those two distances equals the distance of a -> b then it is on the line. If p should be off the line the distance will be longer.

Here is a method to caluclate distance (pythagoran teorem):

private static double GetDistance(double x1, double y1, double x2, double y2) 
{
    double a = Math.abs(x1-x2);
    double b = Math.abs(y1-y2);

    return Math.sqrt(a * a + b * b);
}

Find points on triangle

1 Answers1