0

Consider lots of 3D lines distributed randomly inside a 3D convex body. To find out intersections between all lines, we go to have two loops as follows.

n = number of lines
for i: 1 to n-1 {
  for j: i+1 to n {
    if line(i) intersects line(j): {
      store (i,j)
    }
  }
}

Considering that n will be large, e.g., 1 million and more, what are optimizations that we could implement to speed up the processing? Lines could have any length, any orientation.

Update 1: The following comments helped to add this update:

  1. Lines in our problem are "line segments" with finite length limited to the shape of the convex body.
  2. Intersection or "minimum distance smaller than a tolerance" (very small value, indeed) between two lines is investigated.

Update 2: As suggested in the precious comments below, I was able to benefit from space partitioning, or in simple case, bounding box collision test, to speed up significantly. The optimization framework that I have implemented was as follows.

  1. Evaluate bounding box intersection for all lines, mark those intersect. (this is so fast and low cost)
  2. Do intersection test for those were marked.
Developer
  • 8,258
  • 8
  • 49
  • 58
  • 1
    Since the output size can be quadratic (all lines might intersect all other lines), in the worst case there isn't anything better to do. What does a typical case look like? – harold Feb 28 '17 at 19:11
  • 1
    Some [space partitioning](https://en.wikipedia.org/wiki/Space_partitioning) is needed, [Quadtree](https://en.wikipedia.org/wiki/Quadtree) or [BSP](https://en.wikipedia.org/wiki/Binary_space_partitioning) or some similar. – Ante Feb 28 '17 at 21:04
  • 3
    Your distribution of lines must be special, as random lines just *do not intersect* in 3D (with probability 1). And if you speak of *length*, then you must mean line segments, not lines. They intersect even less ! What are you trying to achieve ? –  Feb 28 '17 at 21:26
  • @Ante those should be helpful. – Developer Mar 01 '17 at 10:11
  • @YvesDaoust some updates were added to the post. – Developer Mar 01 '17 at 10:11
  • 1
    @Developer: would be helpful to provide more information about those segments. Are they truly random ? Uniformly ? Do you expect intersections anywhere ? ... –  Mar 01 '17 at 10:57
  • 1
    "_minimum distance smaller than a tolerance (very small value, indeed)_" Small/very small are relative, so relative to what? – weston Mar 01 '17 at 17:37
  • @weston I usually consider 1e-9 as small for this purpose. So if any line is closer than this to another line, it is quite acceptable to be interpreted as intersection in my study case. – Developer Mar 01 '17 at 21:16
  • @YvesDaoust Your points are so precise and even though they are just comment, they are helpful to me to notice things that I missed. I don't expect intersections anywhere but as there are distributed based on a uniform random function and considering the minimum distance addition in the update, I would expect to have some intersection everywhere. Are you pointing to a certain condition? – Developer Mar 01 '17 at 21:19
  • @Ante Thank you for reminding me of "space partitioning" not particularly for this question but it was very useful for my other work which is on finding colliding polygons in the space. That simple to implement idea could speed up 10s times. – Developer Mar 01 '17 at 21:22
  • @harold You're correct, however, I would say that space partitioning could be used to speed up to some extent. Checking if two bounding box for any collision is trivial and so fast, and hence if two BBox are not intersecting then two lines are distant from each other. – Developer Mar 01 '17 at 21:26
  • see [Implementing Hoey Shamos algorithm with C#](http://stackoverflow.com/q/18512815/2521214) – Spektre Mar 02 '17 at 09:07

1 Answers1

0

If indeed lines intersect in 3D they also intersect in any projection to 2D. So you can project all lines to a plane and run a classical line sweep, for example a Bentley-Ottmann algorithm. That runs in O((n+k) log n) time and linear space for n lines and k intersections. As I would assume (like @Yves Daoust) that k should be very small, this seems like a good idea. Clearly you can get some false positives, as in, lines that intersect in the plane but not so in 3D. Validating a 2D intersection in 3D is a constant time operation, therefore is no big issue in the total view.

gue
  • 1,868
  • 1
  • 16
  • 21
  • Contrary to the 3D case, (where two random lines meet with probability 0), in 2D random lines meet with probability 1; and line segments meet with a finite probability. If those segments are tightly packed, k is O(n²) in the worst case even if there are no 3D intersections at all, which ruins all the benefit of the sweep line. So this technique is acceptable for sparse segments only. –  Mar 01 '17 at 07:26
  • Yes I know, as I have mentioned in the false negative argument. But, as the original approach is guaranteed to take n^2 time the projected variant (using line segments) may only take n log n time. As there was no clarification due to the nature of the 3D intersections, we do not know why he suspects intersections. Of course space partitioning using various techniques could be better suited but this is a very simple approach that is easily implemented and can lead to a speed up. – gue Mar 01 '17 at 08:27
  • Idea of projecting 3D lines into 2D is appealing. – Developer Mar 01 '17 at 10:14
  • I got a little more deep in your idea and would say, as you expressed it could have some performance improvement by filtering out those lines that appear separate on the projected plane. The point is as @YvesDaoust expressed there is no guarantee that the lines are that much sparse. – Developer Mar 01 '17 at 21:36