Joining unordered line segments

views:

146

answers:

+1 Q:

Joining unordered line segments

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.

+4 A:

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.

DigitalRoss 2009-09-17 00:13:30

Agreed. Perhaps he's having difficulty linearizing the sequence of connected points. That's easy; just store each undirected segment twice (once for each endpoint) and visit the point you didn't come from.

wrang-wrang 2009-09-17 00:19:51

Oh, definitely, I wanted each object stored twice, once for each endpoint. Good point, I should have said that in so many words.

DigitalRoss 2009-09-17 00:27:24

It might work. I was just wondering if there are specialised algorithms that handle this particular problem very well. The endpoints match exactly, I luckily do not have to deal with tolerance issues.ps. I'll be sure to put them in twice :)

David Rutten 2009-09-17 00:39:01

It should be possible to go a lot faster than this if there are some helpful invariants. For example, is the ordering of joinable segments in any way constrained?

DigitalRoss 2009-09-17 01:02:45

My 2D space is divided into rectangular cells, and each cell contains 0, 1 or 2 segments. The end-points of each segment are on the cell border.

David Rutten 2009-09-17 02:41:34

Oh yeah, I populate the grid in a nested loop (first columns, then rows).

David Rutten 2009-09-17 02:42:05

I suppose a sort of marching squares approach for finding nearby segments might work faster than building a hash table (ps. sorry for putting up so many comments in a row).

David Rutten 2009-09-17 02:43:11

Oh, heh, you already have a 2D grid. It does seem like you know for sure which cells are the only ones that could possibly contain a matching end, and that you have, at some point, a handle on both the cell and the segment at the same time. Does the structure of the program allow you to join the line segments at that point?

DigitalRoss 2009-09-17 02:56:13

ansaurus

tags:

views:

answers:

Joining unordered line segments

Would a hash of endpoints work?

related questions