Line segment intersection

[Lindley]

I need a C++ implementation of an efficient algorithm to detect line segment intersection. I'm reasonably familiar with Bentley-Ottmann, but it has limitations on what sorts of inputs it can handle that I'm pretty sure will be violated in my case. I've also read about this one:
http://www.akira.ruc.dk/~keld/teachi...Chazelle92.pdf
but unfortunately I don't have time to read through all that and it doesn't seem to include anything as useful as pseudocode or a step-by-step summary.

I'm wondering if anyone knows a robust, public domain implementation out there which I can leverage until I have time to write my own version.

[BioPhysEngr]

Hi,

I don't know about a robust implementation, but the fastest hack-your-way-to-victory method I can think would be to express the line equations parametrically (x(t), y(t), z(t)), equate them, solve for t1 and t2 and then bounds check the parameters to verify that they are within the segment (instead of generically on the line).

Example (in 2D, but I don't see why it wouldn't work in 3D):

Do y=x and y=2x-1 intersect within the unit box?

y=x parametrically:
x(t1) = t1
y(t1) = t1
Where t1 in [0,1]

y=2x-1 parametrically:
x(t2)=2*t2-1
y(t2) = t2
Where t2 in [.5,1]

Equate:
x(t1)=y(t1): t1 = 2*t2-1
y(t2)=y(t2): t1 = t2

Solve (it's just a linear equation, use whatever method you like):
t1 = 1; t2=1

Query: t1 in [0,1]? Yes. t2 in [.5,1]? Yes. Both? Return true for intersection.

Might need some special handling for equivalent lines (since they they have infinitely many solutions).

[Lindley]

That works fine for two lines. I'm looking for the case when I have n lines, and I want to avoid O(n^2) time.

[BioPhysEngr]

Ah, okay; I didn't appreciate that requirement. Bently-Ottmann algorithm looks interesting now that I look at it with it's O(n log n) complexity... wouldn't have thought you could beat naive in this case.