Subject: CGAL users discussion list
List archive
- From: Efraim Fogel <>
- To:
- Subject: Re: [cgal-discuss] sweep line algorithm for horizontal/vertical lines
- Date: Wed, 25 Jul 2007 16:00:56 +0300
The number of intersections between n vertical lines and m horizontal
lines is always mn, so I assume you meant segments and not lines.
You can use the function
template <class InputIterator, class OutputIterator>
OutputIterator CGAL::get_intersection_points(InputIterator curves_begin,
InputIterator curves_end,
OutputIterator points)
and then count the number of intersections. As it is based on the sweep
line paradigm, it is output sensitive with complexity O(k log(k)), where
k is the number of intersections.
I don't know about an alg. with a lower asymptotic complexity, but you
can implement a fairly simple algorithm that counts the number of
intersections of such segments yourself using only kernel predicates. It
might be easier to consider the dual setting where the dual of each
horizontal segment is a wedge centered on the x axis, and the dual of
each vertical segment is a strip bounded by parallel lines. You need to
sort the events on the x axis.
wrote:
> Hi all,
>
> is there an algorithm in CGAL which computes the number of intersections of
> a bunch of horizontal and vertical lines? I don´t need to know which lines
> intersect or the exact intersection point. But only the info that some
> lines intersect is not enough.
>
> I found the sweep line algorithm in CGAL, but i suspect it´s oversized,
> because i only have horizonal or vertical lines.
>
> Do you think there is a faster algorithm regarding these constraints or is
> it ok to use the algo from CGAL? Or is there a simple way to modify the
> existing sweep line algorithm?
>
>
> Thanks in advance!
>
> Sebastian
>
--
____ _ ____ _
/_____/_) o /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/
- sweep line algorithm for horizontal/vertical lines, seven, 07/22/2007
- Re: [cgal-discuss] sweep line algorithm for horizontal/vertical lines, Efraim Fogel, 07/25/2007
Archive powered by MHonArc 2.6.16.