Получить все точки в треугольнике

Question

У меня есть три пункта, например:

Start 194 171
Right 216 131
Left  216 203

Я хочу получить все точки в этом треугольнике. Как бы я сделал это эффективно?

Answer 1

Вступление:

Основная идея состояла в том, чтобы получить ребра треугольника (y-Wise) для каждого 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;
}

Answer 2

Ответ 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://stackru.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).

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

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

Также я ответил на свой вопрос, задав следующий вопрос: /questions/4193075/poluchit-vse-tochki-vnutri-treugolnika-vyizyivaet-perepolnenie/4193088#4193088

Answer 3

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

// 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

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

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