3

这是另一个问题的一个分支，与Keith Randall对该问题的回答有关。请快速查看那里的图像，看看下面的功能正在尝试做什么。

x2 != x1简而言之，如果和 ，则 2D 网格上的任何两点都会有两个对角线交点y2 != y1。我实现了以下功能，但无法弄清楚如何确定要从哪个单元格中减去 delta 以及要添加到哪个单元格。结果，对于某些坐标对，结果是准确的，而对于其他坐标，结果是相反的。

// This class is the same as [Point] except
// it uses BigInteger instead of Int32 types.
public class Cell
{
    System.Numerics.BigInteger X = 0;
    System.Numerics.BigInteger Y = 0;
}

public List<Cell> GetIntersections (Cell c1, Cell c2)
{
    List<Cell> cells = new List<Cell>();
    System.Numerics.BigInteger delta = 0;
    System.Numerics.BigInteger deltaHalf = 0;
    System.Numerics.BigInteger width = 0;
    System.Numerics.BigInteger height = 0;

    width = System.Numerics.BigInteger.Abs(c2.X - c1.X);
    height = System.Numerics.BigInteger.Abs(c2.Y - c1.Y);
    delta = System.Numerics.BigInteger.Abs(height - width);
    deltaHalf = System.Numerics.BigInteger.Divide(delta, 2);

    // INTRODUCE CONDITIONS HERE TO DETERMINE +/- COMBINATION.
    cells.Add(new Cell(c1.X - deltaHalf, c1.Y + deltaHalf));
    cells.Add(new Cell(c2.X + deltaHalf, c2.Y - deltaHalf));

    return (cells);
}

起初我认为这是一个简单的梯度/斜率问题，但我似乎无法找到slope和+/- deltaHalf组合之间的一致相关性。

重要提示：请注意，可接受的答案只能进行 x1、y1、x2、y2 比较。由于性能损失，实际上计算线的斜率不是一种选择。我们已经在进行除以 2 且无法再进行除法。

4

2 回答 2

0

您不能简单地使用斜边 ( delta)。你必须发现三角形的高度。而且，正如您将看到的，要获得高度，您必须计算腿（使用勾股定理）。

然而，要实现这个使用BigInteger需要一些额外的帮助，因为会有一个平方根。我使用了此处提供的解决方案（Newton Raphson 方法）。

让我们得到这些值：

    // leg = sqrt(hypoteneuse²)/2)
    triangleLeg = SqRtN(System.Numerics.BigInteger.Divide(System.Numerics.BigInteger.Pow(delta, 2), 2));
    // altitude = leg²/hypoteneuse
    triangleAltitude = System.Numerics.BigInteger.Divide(System.Numerics.BigInteger.Pow(triangleLeg, 2), delta);

现在，重点来说，我们将使用deltaHalf(for Y ) 和triangleAltitude(for X )。

我已经这样做了：

        // INTRODUCE CONDITIONS HERE TO DETERMINE +/- COMBINATION.
        cells.Add(
            new Cell()
            {
                X = c1.X < c2.X? c1.X - triangleAltitude : c1.X + triangleAltitude,
                Y = c1.Y < c2.Y ? c1.Y - deltaHalf : c1.Y + deltaHalf
            }
        );

        cells.Add(
            new Cell()
            {
                X = c2.X < c1.X ? c2.X - triangleAltitude : c2.X + triangleAltitude,
                Y = c2.Y < c1.Y ? c2.Y - deltaHalf : c2.Y + deltaHalf
            }
        );

任何反馈将不胜感激。

于 2012-08-07T19:50:29.000 回答
0

我知道答案是简单的比较，而不是计算斜边。

public List<Cell> GetCellIntersections (Cell cell1, Cell cell2)
{
    Cell c1 = null;
    Cell c2 = null;
    List<Cell> cells = null;
    System.Numerics.BigInteger delta = 0;
    System.Numerics.BigInteger deltaHalf = 0;
    System.Numerics.BigInteger width = 0;
    System.Numerics.BigInteger height = 0;

    cells = new List<Cell>();

    // Sorting on y reduces conditions from 8 to 4.
    if (cell1.Y < cell2.Y)
    {
        c1 = cell1;
        c2 = cell2;
    }
    else
    {
        c1 = cell2;
        c2 = cell1;
    }

    if ((c1.X != c2.X) && (c1.Y != c2.Y))
    {
        width = System.Numerics.BigInteger.Abs(c2.X - c1.X);
        height = System.Numerics.BigInteger.Abs(c2.Y - c1.Y);
        delta = System.Numerics.BigInteger.Abs(height - width);
        deltaHalf = System.Numerics.BigInteger.Divide(delta, 2);

        if ((c1.X < c2.X) && (c1.Y < c2.Y))
        {
            if (width < height)
            {
                cells.Add(new Cell(this, c1.X - deltaHalf, c1.Y + deltaHalf));
                cells.Add(new Cell(this, c2.X + deltaHalf, c2.Y - deltaHalf));
            }
            else
            {
                cells.Add(new Cell(this, c1.X + deltaHalf, c1.Y - deltaHalf));
                cells.Add(new Cell(this, c2.X - deltaHalf, c2.Y + deltaHalf));
            }
        }
        else
        {
            if (width < height)
            {
                cells.Add(new Cell(this, c1.X + deltaHalf, c1.Y + deltaHalf));
                cells.Add(new Cell(this, c2.X - deltaHalf, c2.Y - deltaHalf));
            }
            else
            {
                cells.Add(new Cell(this, c1.X - deltaHalf, c1.Y - deltaHalf));
                cells.Add(new Cell(this, c2.X + deltaHalf, c2.Y + deltaHalf));
            }
        }
    }

    return (cells);
}
于 2012-08-08T19:55:00.853 回答