CGAL users discussion list

[Stefan Salewski <>]

I have a set of points in 2D, subsets of these build line segments like
this graphic:

    ....

    ....         .   .
                 .   .
          .      .   .
           .
            . 
             .       ......
                     .    .
                     .    .
                     ......

Two to a few hundred dense spaces points may build horizontal, vertical
or diagonal lines or rectangles. Additional there exist many randomly
distributed points.

I want to replace the point-paths by line segments, I need the endpoints
of these line segments. (The application is my topological PCB router,
see http://www.ssalewski.de/Router.html.en, the dense point paths are
obstacles, I need to calculate the detour...)

Can you recommend an algorithm? Starting with a Delaunay triangulation
may be an option, I think long time ago I have seen some path
reconstruction pictures for curved closed paths.

Best regards,

Stefan Salewski