如何在計算二維空間中兩點之間的對角線交點時確定+/-符號？

Question

這是another question的一個分支，並且與Keith Randall's answer有關。請快速查看下面的圖像，看看下面的功能正在嘗試做什麼。

簡而言之，如果是x2 != x1和y2 != y1，則2D網格上的任意兩點都將具有兩個對角線交點。我實現了以下功能，但無法弄清楚如何確定哪個單元從中減去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分區之內進行了分割，並且無法承受另一分割。

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

Answer 2

您不能簡單地使用hypoteneuse（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（爲Ÿ）和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 
      } 
     ); 

任何反饋將不勝感激。