如何在二维空间中计算两点对角线交点时确定正负符号？

Question

如何在二维空间中计算两点对角线交点时确定正负符号？

3

这是另一个问题的分支，与Keith Randall的答案有关。请快速查看那里的图像，以了解下面的函数试图做什么。

简而言之，在2D网格上的任何两个点如果x2！= x1且y2！= y1，则会有两个对角线交点。我实现了以下函数，但无法确定从哪个单元格减去delta，哪个单元格添加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了，不能再承担另一个。

- Raheel Khan

1

除以2就是一个位移操作，这不是非常廉价吗？你是如何对此进行性能分析的？ - djechlin

嗨，Raheel，你能给我一些反馈吗？谢谢！ - Andre Calil

@AndreCalil：我已经回复了，并且添加了我最终使用的只需要一次除以2的代码。 - Raheel Khan

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Raheel Khan · Answer 1

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

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

- Andre Calil · Answer 2

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

然而，如果要使用BigInteger来实现这一点，需要一些额外的帮助，因为会有一个平方根。我使用了这里提供的解决方案（牛顿-拉弗森方法）。

让我们获取这些值：

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

任何反馈将不胜感激。