Get all points within a Triangle

Question

I have three points, for example:

Start 194 171
Right 216 131
Left  216 203

I want to get all the points within that triangle. How would I do that efficiently?

Organize

What have you tried? – Vibraphone

See if this suits you: #2772170 Interesting question that I'm facing myself. – Frugal

The key word you need for your Google search is "rasterization". A search for "triangle rasterization" yields some decent-looking results, for what it's worth. – Imagine

Answer 1

see z3nth10n's answer for better input validation

Introduction:

The general idea was to get the triangle's edges (y-Wise) for every x in it's range, and then you have all the y's that exist within the triangle for every single x, which with simple conversion turns into all points within the triangle.

You can look at it as if you cut the triangle into stripes, each being of width 1. So for X=0, on the line between A and B, the Y is 6, and on the line between A and C, the Y is -2, so you can see that the stripe of X=0 is between -2 and 6. Therefore, you can tell that (0, -2) (0, -1) (0, 0) ... (0, 5) (0, 6) are all in the triangle. Doing that for X's between the smallest and the largest within the triangle, and you have all the points in the triangle!

Speed:

For the triangle (0, 0) (1, 8) (4, 6) - found 16 points.

Done 1,000,000 times in 3.68 seconds.

Implementation:

public IEnumerable<Point> PointsInTriangle(Point pt1, Point pt2, Point pt3)
{
    if (pt1.Y == pt2.Y && pt1.Y == pt3.Y)
    {
        throw new ArgumentException("The given points must form a triangle.");
    }

    Point tmp;

    if (pt2.X < pt1.X)
    {
        tmp = pt1;
        pt1 = pt2;
        pt2 = tmp;
    }

    if (pt3.X < pt2.X)
    {
        tmp = pt2;
        pt2 = pt3;
        pt3 = tmp;

        if (pt2.X < pt1.X)
        {
            tmp = pt1;
            pt1 = pt2;
            pt2 = tmp;
        }
    }

    var baseFunc = CreateFunc(pt1, pt3);
    var line1Func = pt1.X == pt2.X ? (x => pt2.Y) : CreateFunc(pt1, pt2);

    for (var x = pt1.X; x < pt2.X; x++)
    {
        int maxY;
        int minY = GetRange(line1Func(x), baseFunc(x), out maxY);

        for (var y = minY; y <= maxY; y++)
        {
            yield return new Point(x, y);
        }
    }

    var line2Func = pt2.X == pt3.X ? (x => pt2.Y) : CreateFunc(pt2, pt3);

    for (var x = pt2.X; x <= pt3.X; x++)
    {
        int maxY;
        int minY = GetRange(line2Func(x), baseFunc(x), out maxY);

        for (var y = minY; y <= maxY; y++)
        {
            yield return new Point(x, y);
        }
    }
}

private int GetRange(double y1, double y2, out int maxY)
{
    if (y1 < y2)
    {
        maxY = (int)Math.Floor(y2);
        return (int)Math.Ceiling(y1);
    }

    maxY = (int)Math.Floor(y1);
    return (int)Math.Ceiling(y2);
}

private Func<int, double> CreateFunc(Point pt1, Point pt2)
{
    var y0 = pt1.Y;

    if (y0 == pt2.Y)
    {
        return x => y0;
    }

    var m = (double)(pt2.Y - y0) / (pt2.X - pt1.X);

    return x => m * (x - pt1.X) + y0;
}

Gym

Haha this made me laugh. Respect. – Improve

@KevinWang Oh, I see you've found my easter egg on the 12th pixel? Now, really, what? – Gym

Excellent stuff! This has helped me out tremendously. – Licit

Just a small correction: Since pt1.X (for example) is a double, the for loops should start like this: for (var x = Convert.ToInt32(pt1.X); x < pt2.X; x++) because line1Func(x) expects an int. – Licit

@SimpleVar - I don't see the Easter Egg. Sure, once it's pointed out ... It'll be obvious. – Tiberius

@Tiberius I don't see the easter egg either. I guess Kevin just found this amusing at the time – Gym

Answer 2

@SimpleVar answer is well, but it lacks a good check for valid triangles. (This can cause an overflow problem).

So I do my own implementation for Unity3D:

public static IEnumerable<T> PointsInTriangle<T>(T pt1, T pt2, T pt3)
   where T : IPoint
{
    /*
         // https://www.geeksforgeeks.org/check-whether-triangle-valid-not-sides-given/
         a + b > c
         a + c > b
         b + c > a
     */

    float a = Vector2.Distance(new Vector2(pt1.x, pt1.y), new Vector2(pt2.x, pt2.y)),
          b = Vector2.Distance(new Vector2(pt2.x, pt2.y), new Vector2(pt3.x, pt3.y)),
          c = Vector2.Distance(new Vector2(pt3.x, pt3.y), new Vector2(pt1.x, pt1.y));

    if (a + b <= c || a + c <= b || b + c <= a)
    {
        Debug.LogWarning($"The given points must form a triangle. {{{pt1}, {pt2}, {pt3}}}");
        yield break;
    }

    if (TriangleArea(pt1, pt2, pt3) <= 1)
    {
        Point center = GetTriangleCenter(pt1, pt2, pt3);
        yield return (T)Activator.CreateInstance(typeof(T), center.x, center.y);

        return;
    }

    T tmp;

    if (pt2.x < pt1.x)
    {
        tmp = pt1;
        pt1 = pt2;
        pt2 = tmp;
    }

    if (pt3.x < pt2.x)
    {
        tmp = pt2;
        pt2 = pt3;
        pt3 = tmp;

        if (pt2.x < pt1.x)
        {
            tmp = pt1;
            pt1 = pt2;
            pt2 = tmp;
        }
    }

    var baseFunc = CreateFunc(pt1, pt3);
    var line1Func = pt1.x == pt2.x ? (x => pt2.y) : CreateFunc(pt1, pt2);

    for (var x = pt1.x; x < pt2.x; ++x)
    {
        int maxY;
        int minY = GetRange(line1Func(x), baseFunc(x), out maxY);

        for (int y = minY; y <= maxY; ++y)
            yield return (T)Activator.CreateInstance(typeof(T), x, y);
    }

    var line2Func = pt2.x == pt3.x ? (x => pt2.y) : CreateFunc(pt2, pt3);

    for (var x = pt2.x; x <= pt3.x; ++x)
    {
        int maxY;
        int minY = GetRange(line2Func(x), baseFunc(x), out maxY);

        for (int y = minY; y <= maxY; ++y)
            yield return (T)Activator.CreateInstance(typeof(T), x, y);
    }
}

private static int GetRange(float y1, float y2, out int maxY)
{
    if (y1 < y2)
    {
        maxY = Mathf.FloorToInt(y2);
        return Mathf.CeilToInt(y1);
    }

    maxY = Mathf.FloorToInt(y1);
    return Mathf.CeilToInt(y2);
}

private static Func<int, float> CreateFunc<T>(T pt1, T pt2)
    where T : IPoint
{
    var y0 = pt1.y;

    if (y0 == pt2.y)
        return x => y0;

    float m = (float)(pt2.y - y0) / (pt2.x - pt1.x);

    return x => m * (x - pt1.x) + y0;
}

    public static float TriangleArea<T>(T p1, T p2, T p3)
        where T : IPoint
    {
        float a, b, c;

        if (!CheckIfValidTriangle(p1, p2, p3, out a, out b, out c))
            return 0;

        return TriangleArea(a, b, c);
    }

    public static float TriangleArea(float a, float b, float c)
    {
        // Thanks to: http://james-ramsden.com/area-of-a-triangle-in-3d-c-code/

        float s = (a + b + c) / 2.0f;
        return Mathf.Sqrt(s * (s - a) * (s - b) * (s - c));
    }

    public static Point GetTriangleCenter<T>(T p0, T p1, T p2)
        where T : IPoint
    {
        // Thanks to: https://mcmap.net/q/266471/-finding-center-of-2d-triangle

        return new Point(p0.x + p1.x + p2.x / 3, p0.y + p1.y + p2.y / 3);
    }

    public static bool CheckIfValidTriangle<T>(T v1, T v2, T v3, out float a, out float b, out float c)
        where T : IPoint
    {
        a = Vector2.Distance(new Vector2(v1.x, v1.y), new Vector2(v2.x, v2.y));
        b = Vector2.Distance(new Vector2(v2.x, v2.y), new Vector2(v3.x, v3.y));
        c = Vector2.Distance(new Vector2(v3.x, v3.y), new Vector2(v1.x, v1.y));

        if (a + b <= c || a + c <= b || b + c <= a)
            return false;

        return true;
    }

IPoint interface could be a good point for own Point implementations (for libs like Clipper, TessDotNet or Poly2Tri). You can change it at any time (two UnityEngine.Vector2 or System.Drawing.Point).

Hope this helps!

EDIT: I solved all bugs here:

Also I answered my own question asking this: https://mcmap.net/q/1774385/-get-all-points-within-a-triangle-is-causing-an-overflow

Tumble