CGAL users discussion list

[Andreas Fabri <>]

Hello,

Just from your Ascii image it is hard to tell what
a good strategy would be.  Feel free to post a screenshot
of a real world example.

Just from my gut feeling I would say that you should
exploit that the non-noise points are horizontal
vertical or diagonal.

What is the ratio of noise/non-noise points?
If you had zero noise, is it easy to separate
the path objects, or can they get arbitrarily close.

How ambiguous can it get, that is can this happen:

. . .
. . .
. . .


Best,

Andreas

On 02/01/2014 20:46, Stefan Salewski wrote:
> 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

--
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri