Sweep Line Algorithm to find intersections

Sweep Line Algorithm to find intersections

Post by Emmanuel Quetela » Fri, 07 Jun 2002 17:51:53



Hello,
I search an open source implementation or documentation of the sweep
line algorithm to find intersections points of a set of line-segment.
If someone now a link about this topic,
thanks
 
 
 

Sweep Line Algorithm to find intersections

Post by Fernando Cacciol » Sat, 08 Jun 2002 02:24:45



Quote:> Hello,
> I search an open source implementation or documentation of the sweep
> line algorithm to find intersections points of a set of line-segment.
> If someone now a link about this topic,
> thanks

FWIW, these are the canonical references to the subject:

(1) Algorithms for reporting and counting geometric intersections, Bentley
and Ottman, IEEE Trans on Comp. 1979.
(2) An optimal algorithm for intersecting line segments in the plane,
Chazelle and Edelsbrunner, Journal of the ACM, 1992

You might find them (or similar documents) on the NEC Research Library:
http://citeseer.nj.nec.com/cs

HTH,

--
Fernando Cacciola
Sierra s.r.l.

www.gosierra.com

 
 
 

Sweep Line Algorithm to find intersections

Post by Prem Rachakond » Sat, 08 Jun 2002 06:14:56


I  am not sure about the name of the algorithm, but if you want to know the
intersecting segments of two sets of data fitted to a straight line, I know
some algorithms. Let me know if you are looking out for them.

Prem.


Quote:> Hello,
> I search an open source implementation or documentation of the sweep
> line algorithm to find intersections points of a set of line-segment.
> If someone now a link about this topic,
> thanks

 
 
 

1. sweep line algorithm for line intersection

this question goes for anyone who is familiar with and has tried to
implement the sweep line algorithm to find all intersections between a
group of sections. my problem is: supose my sweep line moves from left
to right. how do i sort vertical sections in the status data structure.
(the definition of the Status sorting function does not cover the cse of
vertical lines)
thanks in advance

2. THANKS To all who answered my question about AM

3. Looking for algorithms to find intersection line of two surfaces

4. newbie to open inventor

5. Need line/line intersection algorithm

6. Heightfield questions

7. What,(Where Find Algorithm) Fast Find Nearest Line ???

8. Finding 2d Line Intersection Points

9. fast method for finding points of intersection between a line and a circle

10. Finding the intersection between two 3D Lines

11. Help me with finding intersections of 2 2D line segments

12. HELP: Finding intersection of two line segments