如何检查两条线在网格上相交/重叠？

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

如果您开始检查以确保行不是同一行，这可能会更有效。