5

たとえば、次の 3 つのポイントがあります。

Start 194 171
Right 216 131
Left  216 203

その三角形内のすべての点を取得したい。どうすれば効率的にそれを行うことができますか？

4

2 に答える 2

5

より良い入力検証については、 z3nth10n の回答を参照してください

序章：

一般的なアイデアは、その範囲内のすべての x に対して三角形のエッジ (y 方向) を取得することでした。次に、すべての x に対して三角形内に存在するすべての y を取得し、単純な変換で三角形内のすべての点に変換します。

三角形を幅 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 個の点が見つかりました。

3.68秒で 1,000,000 回実行しました。

実装：

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;
}
于 2012-06-18T01:05:21.193 に答える
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://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）。いつでも変更できます (2 つUnityEngine.Vector2またはSystem.Drawing.Point)。

お役に立てれば！

編集:ここですべてのバグを解決しました:

また、私はこれを尋ねる自分の質問に答えました: https://stackoverflow.com/a/53734816/3286975

于 2018-12-11T19:00:49.673 に答える