Получите все точки в пределах треугольника

см. ответ z3nth10n для лучшей проверки ввода

Введение:

Общая идея заключалась в том, чтобы получить края треугольника (y-мудрый) для каждого x в его диапазоне, а затем у вас есть все y, которые существуют в треугольнике для каждого отдельного x, которые с помощью простого преобразования превращаются во все точки внутри треугольника.

Вы можете смотреть на это так, как если бы вы разрезали треугольник на полосы, каждая шириной 1. Итак, для X = 0 на линии между A и B Y равно 6, а на линии между A и C - Y равно -2, поэтому вы можете видеть, что полоса X = 0 находится между -2 и 6. Следовательно, вы можете сказать, что (0, -2) (0, -1) (0, 0) ... (0 , 5) (0, 6) все находятся в треугольнике. Проделав это для X между самым маленьким и самым большим в треугольнике, вы получите все точки в треугольнике!

Скорость:

Для треугольника (0, 0) (1, 8) (4, 6) найдено 16 точек.

Выполнено 1 000 000 раз за 3,68 секунды.

Реализация:

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;
}

@SimpleVar ответ хорош, но ему не хватает хорошей проверки правильности треугольников. (Это может вызвать проблему с переполнением).

Итак, я делаю свою реализацию для 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://stackoverflow.com/questions/524755/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 интерфейс может быть хорошей идеей для собственных Point реализаций (для таких библиотек, как Clipper, TessDotNet or Poly2Tri). Вы можете изменить его в любой момент (два UnityEngine.Vector2 или System.Drawing.Point).

Надеюсь это поможет!

РЕДАКТИРОВАТЬ: Я решил все ошибки здесь:

Также я ответил на свой вопрос: https://stackoverflow.com/a/53734816/3286975

Прежде всего, получите ограничительную рамку треугольника:

// This is in psuedocode since I don't know c#
bbox[x1] = min(triangles[1][x], triangles[2][x], triangles[3][x])
bbox[x2] = max(triangles[1][x], triangles[2][x], triangles[3][x])
bbox[y1] = min(triangles[1][y], triangles[2][y], triangles[3][y])
bbox[y2] = max(triangles[1][y], triangles[2][y], triangles[3][y])

Теперь для любой заданной точки (x, y):

if x < bbox[x1] or y < bbox[y1] or x > bbox[x2] or y > bbox[y2]
then it can't possibly be in the triangle

Для всех остальных точек вы можете использовать алгоритм точки в треугольнике, аналогичный представленным здесь.

Если вам нужны все точки, которые находятся в треугольнике, вы можете перебрать все точки в ограничивающей рамке и посмотреть, какие из них входят, а какие нет.