CODEWITHSUNDEEP
c++mathgeometryline-intersection
Colin Hines
Colin Hines

Reputation: 1

Determining intersections of segmented lines

/I need to determine if a pair of lines defined by multiple line segments intersects, for example a line defined by (0,0), (1,2), (3,1) and another by (0,2), (2,-1), (4,1).

I do not need to determine where the intersection is, but I need an efficient method because I can have a very large number of edges. I am using the below code to determine if two segments intersect, but that is inefficient for a line of larger lengths. Furthermore, the lines are edges in a graph and they are constrained to a known maximum length.

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

Upvotes: 0

Views: 980

Answers (1)

user2104560
user2104560

Reputation:

You would slightly change Bentley-Ottmann Algorithm which computes all k intersections in O((n+k)logn) time and O(n+k) space.

Proposed modification - Bentley-Ottmann Algorithm gets set of segments and reports all intersections. You would split your segmented lines to set of segments and give this set as the input to algorithm. When some intersection is found just check whether intersecting segments belong to the same segmented line or not. If not it means you've just found intersection of segmented lines.

Please, note that in worst case complexity will be O(n^2) when number of intersections is very large. The worst case for you is two segmented lines which look like intertwining snakes. Remember that there are at least O(N) pseudo-intersections - each segmented line will produce O(length) pseudo-intersections and as lenght1+lenght2 = N, where N is total number of segments, there are O(N) pseudo-intersections. Pseudo-intersection is such intersection that will be detected by Bentley-Ottmann Algorithm but shouldn't be taken to account.

Implementation hints - Bentley-Ottmann Algorithm based on sweep line algo which is based on sorting points - pairs of (X,Y). Now you should just sort triples (X,Y,segmentsLineID). In your case all triples would be (X,Y,1) or (X,Y,2)

Upvotes: 0

Related Questions