在计算2D空间中两点之间的对角线交点时如何确定+/-符号？

这是另一个问题的分支，与Keith Randall对问题的回答有关。 请快速查看图像，看看下面的function是做什么的。

简而言之，如果x2 != x1和y2 != y1则2D网格上的任何两个点都将具有两个对角交点。 我实现了以下function，但无法弄清楚如何确定从哪个单元中减去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 GetIntersections (Cell c1, Cell c2) { List cells = new List(); 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

您不能简单地使用hypoteneuse（ 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 （对于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 } ); 

任何反馈将不胜感激。

Answer 2

我知道答案是在简单比较的某个地方而不是必须计算斜边。

 public List GetCellIntersections (Cell cell1, Cell cell2) { Cell c1 = null; Cell c2 = null; List 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(); // 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); }