Joining unordered line segments

Question

My algorithm produces a list of (usually) several thousand line segments (all 2D) which I need to join up into large polylines. These resulting polylines might be closed or open, but they are never self-intersecting. The line segments are not directed, i.e. it might be needed to flip a line segment before it can be joined to its neighbour.

What would be an extremely fast way of finding these polylines? I have to do this in real-time, so anything that takes longer than -say- 10ms is not a solution.

I'm doing this in C#, but I'm looking for ideas, not source.

Answer 1

Would a hash of endpoints work?

If the endpoints match exactly then you can just store each object twice in a hash, once by each endpoint. Then, for each object, look up both its end points. You will get any other objects that need to be joined.

If the endpoints have any kind of imprecision, then you will need a spatial index, and probably one that uses an R-tree. You can get a similar effect by just making a 2d hash grid. The hash grid contains buckets of nearby endpoints. You will need to check neighboring cells.