如何檢查兩條線在網格上相交/重疊？

Question

這是一個相當平凡的算法問題，但我的實現留下了速度和簡單性。我有兩個Line對象，每個對象都擁有{unsigned int x, unsigned int y}形式的兩個座標結構。這個第一個座標位置是該行的開始位置，第二個座標位置是它的結束位置。假設線條只能在網格上是垂直或水平的，我怎麼能檢查兩條線平行重疊或垂直相交。優選地，這是作爲行中的方法實現的：

- (BOOL)intersectsLine:(Line)otherLine; 

感謝！

Answer 1

由於我們只談論水平線或垂直線，因此第一步我會檢查線是否具有相同的方向。

​​

因此，考慮到兩個點的線條......

LineOrientation line1orientation; 
LineOrientation line2orientation;  

if (a.x1 == a.x2) { 
    line1orientation = HorizontalLine; 
} else { 
    line1orientation = VerticalLine; 
} 

if (b.x1 == b.x2) { 
    line2orientation = VerticalLine; 
} else { 
    line2orientation = Horizontal; 
} 

現在，我們需要檢查他們是否是兩個水平，無論垂直或每一個，然後測試特定值：

if (line1orientation == line2orientation) { 
    if (line1orientation == VerticalLine) { 
     if (a.x1 != b.x1) { 
      return false; 
     } else { 
      if (a.y1 < a.y2) { 
       return ((b.y1 > a.y1 && b.y1 < a.y2) || 
        (b.y2 > a.y1 && b.y2 < a.y2)); 
      } else { 
       return ((b.y1 > a.y2 && b.y1 < a.y1) || 
        (b.y2 > a.y2 && b.y2 < a.y1)); 
      } 
     } 
    } else { 
     if (a.y1 != b.y1) { 
      return false; 
     } else { 
      if (a.x1 < a.x2) { 
       return ((b.x1 > a.x1 && b.x1 < a.x2) || 
        (b.x2 > a.x1 && b.x2 < a.x2)); 
      } else { 
       return ((b.x1 > a.x2 && b.x1 < a.x1) || 
        (b.x2 > a.x2 && b.x2 < a.x1)); 
      } 
     } 
    } 
} else { 
    if (line1orientation == VerticalLine) { 
     if (a.y1 < a.y2) { 
      return (((b.y1 > a.y1) && (b.y1 < a.y2)) && ((b.x1 > a.x1 && b.x2 
       < a.x1) || (b.x2 > a.x1 && b.x1 < a.x1))); 
     } else { 
      return (((b.y1 > a.y2) && (b.y1 < a.y1)) && ((b.x1 > a.x1 && b.x2 
       < a.x1) || (b.x2 > a.x1 && b.x1 < a.x1))) 
     } 
    } else { 
     if (a.x1 < a.x2) { 
      return (((b.x1 > a.x1) && (b.x1 < a.x2)) && ((b.y1 > a.y1 && b.y2 
       < a.y2) || (b.y2 > a.y1 && b.y1 < a.y1))); 
     } else { 
      return (((b.x1 > a.x2) && (b.x1 < a.x1)) && ((b.y1 > a.y1 && b.y2 
       < a.y2) || (b.y2 > a.y1 && b.y1 < a.y1))); 
    } 
} 

如果您開始檢查以確保行不是同一行，這可能會更有效。