c# - 计算二维空间中两点之间的对角线交点时如何确定+/-号？

Question

这是 another question 的一个分支并且与 Keith Randall's answer 有关到问题。请快速查看那里的图像，看看下面的函数正在尝试做什么。

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

// 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 的除法，无法再进行除法。

Answer 1

您不能简单地使用斜线 (delta)。你必须发现 triangle altitude .而且，正如您将看到的，要获得高度，您必须计算腿(使用勾股定理)。

但是，要使用 BigInteger 实现此目的将需要一些额外的帮助，因为会有一个平方根。我使用了解决方案 provided here (牛顿拉夫森法)。

让我们获取这些值:

    // 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(对于 Y)和 triangleAltitude(对于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
            }
        );

我们将不胜感激任何反馈。