Получить все точки внутри треугольника вызывает переполнение - PullRequest
Новая
       122

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

0 голосов
/ 11 декабря 2018

Ну, мне не хватает GraphicsPath в Unity (чтобы заполнить многоугольник, нарисовать его, обрисовать в общих чертах и ​​утилиты с фигурами в целом), поэтому я делаю свою собственную реализацию.Ну, мы могли бы также обсудить, какой вариант является лучшим, но на самом деле я предпочитаю это, потому что я многому учусь.

Идея состоит в следующем, учитывая, что для многоугольника мы делаем смещенный многоугольник (внутрь инаружу) с помощью ClipperLib, а позже с LibTessDotNet мы триангулируем его, выводя это:

...

Зеленые, синие и желтые пиксели являются сторонами каждого треугольника.Вывод LibTessDotNet в виде 501 треугольника для этой фигуры.

Итак, благодаря @ SimpleVar Я сделал this : 

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

    // (new[] { pt1, pt2, pt3 }).Distinct(new PointComparer()).Count() == 0
    if (a + b <= c || a + c <= b || b + c <= a)
    {
        Debug.LogWarning($"The given points must form a triangle. {{{pt1}, {pt2}, {pt3}}}");
        yield break;
    }

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

На самом деле это работает,но не слишком хорошоПотому что это вызывает переполнение (мне приходится убивать процесс Unity с помощью Process Explorer из-за большого объема ОЗУ, используемого этим кодом).

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

Я думаю, что проблема в for (var x = pt1.x; x < pt2.x; ++x) или for (int y = minY; y <= maxY; ++y) или в следующем блоке ... Но, как я уже сказал, я не могу отлаживать, как я привык к WinForms.Когда переполнение достигнуто, Visual Studio прекращает отладку и происходит сбой Unity, поэтому я немного застрял.

Я пытался сделать DotNetFiddle переполнением, но я ничего не могу понять здесь ... Итак ... Я не знаю, что я могу сделать, чтобы улучшить код.

Объясните мне все, что вы находите, неоптимизировано, а также подходы, которые я мог бы сделать, чтобы улучшить свою главную цель.

1 Ответ

0 голосов
/ 12 декабря 2018

Хорошо, я решил, что проблема была в том, что треугольники с площадью, равной или меньшей 1, делали переполнение.Проверяя это по формуле Герона, я решил: 

    public static float TriangleArea(Point p1, Point p2, Point p3)
    {
        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));
    }

А потом: 

        if (TriangleArea(pt1, pt2, pt3) <= 1)
            return;

Возможно (я не проверял), но это могло быть вызвано генериками.

В любом случае, я разместил на Gist Github этот замечательный TriangleUtils.Учитывая список треугольников, связанных с LibTessDotNet, мы можем растеризовать его: https://gist.github.com/z3nth10n/7d60f22c7e906f645d53c9622507c23b

Я загрузил следующее видео, показывающее, чего я достиг: https://youtu.be/7yY3MIyRtPw

...