Nearest neighbour search in a constantly changing set of line segments

Question

I have a set of line segments. I want to perform the following operations on them:

1. Insert a new line segment.
2. Find all line segments within radius R of a given point.
3. Find all points within radium R1 of a given point.
4. Given a line segment, find if it intersects any of the existing line segments. Exact intersection point is not necessary(though that probably doesnt simplify anything.)

The problem is algorithms like kd/bd tree or BSP trees is that they assume a static set of points, and in my case the points will constantly get augmented with new points, necessitating rebuilding the tree.

What data-structure/algorithms will be most suited for this situation ?

Edit: Accepted the answer that is the simplest and solves my problem. Thanks everyone!

Answer 1

One possibility is dividing your space into a grid of boxes - perhaps 10 in the y-axis and 10 in the x-axis for a total of 100.

Store these boxes in an array, so it's very easy/fast to determine neighboring boxes. Each box will hold a list vector of line segments that live in that box.

When you calculate line segments within R of one segment, you can check only the relevant neighboring boxes.

Of course, you can create multiple maps of differing granularities, maybe 100 by 100 smaller boxes. Simply consider space vs time and maintenance trade-offs in your design.

• updating segment positions is cheap: just integer-divide by box sizes in the x and y directions. For example, if box-size is 20 in both directions and your new coordinate is 145,30. 145/20==7 and 30/20==1, so it goes into box(7,1), for a 0-based system.

Answer 2

Maintaining a dynamic tree might not be as bad as you think.

As you insert new points/lines etc into the collection it's clear that you'd need to refine the current tree, but I can't see why you'd have to re-build the whole tree from scratch every time a new entity was added, as you're suggesting.

With a dynamic tree approach you'd have a valid tree at all times, so you can then just use the fast range searches supported by your tree type to find the geometric entities you've mentioned.

For your particular problem:

• You could setup a dynamic geometric tree, where the leaf elements maintain a list of geometric entities (points and lines) associated with that leaf.

• When a line is inserted into the collection it should be pushed onto the lists of all leaf elements that it intersects with. You can do this efficiently by traversing the subset of the tree from the root that intersects with the line.

• To find all points/lines within a specified radial halo you first need to find all leaves in this region. Again, this can be done by traversing the subset of the tree from the root that is enclosed by, or that intersects with the halo. Since there maybe some overlap, you need to check that the entities associated with this set of leaf elements actually lie within the halo.

• Once you've inserted a line into a set of leaf elements, you can find whether it intersects with another line by scanning all of the lines associated with the subset of leaf boxes you've just found. You can then do line-line intersection tests on this subset.

A potential dynamic tree refinement algorithm, based on an upper limit to the number of entities associated with each leaf in the tree, might work along these lines:

function insert(x, y)

find the tree leaf element enclosing the new entitiy at (x,y) based on whatever 
fast search algorithm your tree supports

if (number of entities per leaf > max allowable) do

    refine current leaf element (would typically either be a bisection 
    or quadrisection based on a 2D tree type)

    push all entities from the old leaf element list onto the new child element
    lists, based on the enclosing child element

else

    push new entity onto list for leaf element

endif

This type of refinement strategy only makes local changes to the tree and is thus generally pretty fast in practice. If you're also deleting entities from the collection you can also support dynamic aggregation by imposing a minimum number of entities per leaf, and collapsing leaf elements to their parents when necessary.

I've used this type of approach a number of times with quadtrees/octrees, and I can't at this stage see why a similar approach wouldn't work with kd-trees etc.

Hope this helps.

Answer 3

While items 2 & 3 are relatively easy, using a simple linear search with distance checks as each line is inserted, item 4 is a bit more involved.

I'd tend to use a constrained triangulation to solve this, where all the input lines are treated as constraints, and the triangulation is balanced using a nearest neighbour rather than Delaunay criterion. This is covered pretty well in Triangulations and applications by Øyvind Hjelle, Morten Dæhlen and Joseph O'Rourkes Computational Geometry in C Both have source available, including getting sets of all intersections.

The approach I've taken to do this dynamically in the past is as follows;

• Create a arbitrary triangulation (TIN) comprising of two triangles surrounding the extents (current + future) of your data.

• For each new line

• Insert both points into the TIN. This can be done very quickly by traversing triangles to find the insertion point, and replacing the triangle found with three new triangles based on the new point and old triangle.

• Cut a section through the TIN based on the two end points, keeping a list of points where the section cuts any previously inserted lined. Add the intersection point details to a list stored against both lines, and insert them into the TIN.

• Force the inserted line as a constraint

• Balance all pairs of adjacent triangles modified in the above process using a nearest neighbour criterion, and repeat until all triangles have been balanced.

This works better than a grid based method for poorly distributed data, but is more difficult to implement. Grouping end-point and lines into overlapping grids will probably be a good optimization for 2 & 3.

Note that I think using the term 'nearest neighbour' in your question is misleading, as this is not the same as 'all points within a given distance of a line', or 'all points within a given radius of another point'. Nearest neighbour typically implies a single result, and does not equate to 'within a given point to point or point to line distance'.

Answer 4

Instead of inserting and deleting into a tree you can calculate a curve that completely fills the plane. Such a curve reduce the 2d complexity to a 1d complexity and you would be able to find the nearest neighbor. You can find some example like z curve and hilbert curve. Here is a better description of my problem http://en.wikipedia.org/wiki/Closest_pair_of_points_problem.