0

I have a set of N line segments in 3-space where each segment is represented by two coordinates denoting the endpoints of the segment: (x1, y1, z1)-(x2, y2, z2)

I want to know if any line segments are touching, or more formally, if they are:

  • intersecting
  • partially or fully overlapping

Of course there is the naive search of testing each one against the other in O(N^2) with 2 nested loops, but is there a more efficient algorithm?

Co-linear lines are ok so long as they do not overlap; touching at exactly at the endpoints is acceptable. (This is a sanity for NEC2 because it does not handle wires that touch unless they connect at endpoints. Any that touch but do not touch at endpoints must be broken into multiple wires.)

KJ7LNW
  • 1,437
  • 5
  • 11
  • 1
    Are these half-lines/closed lines or are the lines stretched infinitely? – user1984 Nov 19 '21 at 21:27
  • @user1984, they are line segments. (x1, y1, z1)-(x2, y2, z2) are endpoints. I updated the question. – KJ7LNW Nov 20 '21 at 04:57
  • 1
    using BVH or any spatial subdivision will lead to lower complexity see https://stackoverflow.com/q/18512815/2521214 – Spektre Nov 20 '21 at 07:35
  • 1
    I believe you can use a BVH tree structure to check the intersection of a line against a set of lines, that is a O(log N) search. E.g., check answer to this question: https://stackoverflow.com/questions/51897251/check-if-one-line-segment-intersects-with-a-set-of-line-segments/51903195#51903195 then you can check all lines against the other lines in O(N log N) where N is the number of lines. – Mauricio Cele Lopez Belon Nov 21 '21 at 01:41
  • As a rule, line segments do not intersect in 3D. If you have specific reasons to believe that they do in your case, you should state them. –  Nov 21 '21 at 19:07
  • @YvesDaoust, user error could make it possible. This is for a sanity check to warn the user to fix their NEC code. – KJ7LNW Nov 23 '21 at 01:50
  • Makes sense now, thanks. –  Nov 23 '21 at 07:13
  • 1
    A possible solution is to run an efficient 2D intersection algorithm on a projection of the segments (say onto XY), and check existence of true 3D intersections. Bentley-Ottman takes time O((n+k) log n). Unfortunately, in the projection, k will be larger than needs be. –  Nov 23 '21 at 07:17

0 Answers0