0

/我需要确定由多个线段定义的一对线是否相交，例如由 定义的线(0,0), (1,2), (3,1)和由定义的线(0,2), (2,-1), (4,1)。

我不需要确定交点在哪里，但我需要一种有效的方法，因为我可以有大量的边。我正在使用下面的代码来确定两个线段是否相交，但这对于长度较大的线来说效率很低。此外，线是图中的边，它们被限制在已知的最大长度内。

static bool IsOnSegment(float xi, float yi, float xj, float yj,
                    float xk, float yk) {
  return (xi <= xk || xj <= xk) && (xk <= xi || xk <= xj) &&
     (yi <= yk || yj <= yk) && (yk <= yi || yk <= yj);
}

static char ComputeDirection(float xi, float yi, float xj, float yj,
                         float xk, float yk) {
  float a = (xk - xi) * (yj - yi);
  float b = (xj - xi) * (yk - yi);
  return a < b ? -1 : a > b ? 1 : 0;
}

// Do line segments (x1, y1)--(x2, y2) and (x3, y3)--(x4, y4) intersect? /
bool DoLineSegmentsIntersect(float x1, float y1, float x2, float y2,
                         float x3, float y3, float x4, float y4) {
char d1 = ComputeDirection(x3, y3, x4, y4, x1, y1);
char d2 = ComputeDirection(x3, y3, x4, y4, x2, y2);
char d3 = ComputeDirection(x1, y1, x2, y2, x3, y3);
char d4 = ComputeDirection(x1, y1, x2, y2, x4, y4);
return (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
      ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) ||
     (d1 == 0 && IsOnSegment(x3, y3, x4, y4, x1, y1)) ||
     (d2 == 0 && IsOnSegment(x3, y3, x4, y4, x2, y2)) ||
     (d3 == 0 && IsOnSegment(x1, y1, x2, y2, x3, y3)) ||
     (d4 == 0 && IsOnSegment(x1, y1, x2, y2, x4, y4));
}
4

1 回答 1

0

您将稍微更改Bentley-Ottmann 算法，该算法计算时间和空间上的所有k交叉点。O((n+k)logn)O(n+k)

提议的修改 - Bentley-Ottmann 算法获取一组段并报告所有交叉点。您可以将分段线拆分为一组段，并将该组作为算法的输入。当找到某个交点时，只需检查相交线段是否属于同一分段线。如果不是，则意味着您刚刚找到分段线的交点。

请注意，在最坏的情况下，复杂性将是O(n^2)交叉点数量非常多时。对你来说最糟糕的情况是两条看起来像缠绕在一起的蛇的分段线。请记住，至少存在O(N)伪交叉点 - 每条分段线都会产生O(length)伪交叉点，并且长度 1+长度 2 = N，其中 N 是线段的总数，存在 O(N) 个伪交叉点。伪交叉点是由 Bentley-Ottmann 算法检测到的交叉点，但不应考虑在内。

实施提示 - 基于扫描线算法的 Bentley-Ottmann 算法，该算法基于排序点 - (X,Y) 对。现在您应该只对三元组 (X,Y,segmentsLineID) 进行排序。在您的情况下，所有三元组都是 (X,Y,1) 或 (X,Y,2)

于 2013-07-18T04:57:18.243 回答