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

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

Start 194 171
Right 216 131
Left  216 203

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

 MasterMastic18 июн. 2012 г., 01:16
Посмотрите, подходит ли вам это:stackoverflow.com/questions/2771670/… Интересный вопрос, с которым я сталкиваюсь.
 Stuart Golodetz18 июн. 2012 г., 01:27
Ключевое слово, которое вам нужно для поиска в Google, - "Растеризация". Поиск "растеризации треугольника" дает некоторые приличные результаты, чего бы это ни стоило.
 Oliver Charlesworth18 июн. 2012 г., 01:10
 Lukasz Madon18 июн. 2012 г., 01:10
Домашнее задание? ;) ...

Ответы на вопрос(3)

@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).

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

EDIT: Я решил все ошибки здесь:

Также я ответил на свой вопрос: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

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

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

Решение Вопроса

see Ответ Z3nth10n для лучшей проверки ввода

Introduction:

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

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;
}
 18 июн. 2012 г., 05:18
@KevinWang О, я вижу, вы нашли мое пасхальное яйцо на 12-м пикселе? Теперь действительно, что?
 28 июн. 2013 г., 18:15
Отличный материал! Это очень помогло мне.
 28 июн. 2013 г., 18:21
Небольшая поправка: Сpt1.X (например) являетсяdoubleЦиклы for должны начинаться так:for (var x = Convert.ToInt32(pt1.X); x < pt2.X; x++) так какline1Func(x) ожидаетint.
 18 июн. 2012 г., 05:06
Хаха, это заставило меня смеяться. Уважение.
 12 дек. 2018 г., 02:51
@SimpleVar - я не вижу пасхальное яйцо. Конечно, как только это будет указано ... Это будет очевидно.

Ваш ответ на вопрос