sweep line algorithm for line intersection

sweep line algorithm for line intersection

Post by nir » Mon, 10 Jan 2000 04:00:00



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
 
 
 

sweep line algorithm for line intersection

Post by Graham Smit » Mon, 10 Jan 2000 04:00:00


I may misunderstand your question, but:

I believe vertical lines are handeled as a special case of the algorithm,
and never need to be added to the data structure. Evey endpoint
intersection should be checked for verticallity, and if vertical, just
compute
all intersections and report them. Adjacency before and after the vertical
line will not change.

Cheers,

Graham


>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


 
 
 

sweep line algorithm for line intersection

Post by nir » Wed, 12 Jan 2000 04:00:00


Thanks.

> I may misunderstand your question, but:

> I believe vertical lines are handeled as a special case of the algorithm,
> and never need to be added to the data structure. Evey endpoint
> intersection should be checked for verticallity, and if vertical, just
> compute
> all intersections and report them. Adjacency before and after the vertical
> line will not change.

> Cheers,

> Graham


> >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