CGAL users discussion list

[Efraim Fogel <>]

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    /__________  __  //
(____ (   (    (    (_/ (_/-(-'_(/
                        _/