获取三角形内的所有点数

Question

我有三点,例如:

Start 194 171
Right 216 131
Left  216 203

我想得到那个三角形内的所有点.我该如何有效地做到这一点？

Answer 1

请参阅z3nth10n的答案,以获得更好的输入验证

介绍:

一般的想法是为每个x的范围获得三角形的边(y-Wise),然后你得到每个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;
}