CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

On 01/03/2014 08:53 PM, Stefan Salewski wrote:
> On Fri, 2014-01-03 at 10:06 +0100, Andreas Fabri wrote:
> > 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.
>
> OK, here is an example picture:
>
> http://www.ssalewski.de/tmp/tut1.png
>
> I want to find the red lines, the endpoints.

The 2D alpha-shape might be a good solution for this case if the 
distance between points to connect is smaller than between points
not to connect. Remind that the alpha is related to the square of
a distance.

http://doc.cgal.org/latest/Alpha_shapes_2/index.html

There is an ipelet and a demo if you want to try it.

Sebastien.

> The red lines are barriers for copper traces on the Printed Circuit
> Board, as shown at
>
> http://www.ssalewski.de/Router.html.en
>
> Note, the gray rectangles and circles can be regarded simple as points
> each. And all the points I am interested in are lying exactly on a line,
> the line may have any angle, mostly horizontally or vertically.
>
> Yesterday I did some thinking and google search...
> My feeling is, that the crust algorithm as described in
> http://sarielhp.org/research/CG/applets/Crust/Crust.html
> and already supported by CGAL in
> /usr/share/doc/cgal-4.3/demo/CGAL_ipelets/hull.cpp
> is not very helpful to finding the individual lines.
>
> One strategy may be:
> -Create the delaunay triangulation.
> -Remove all vertices which have no closely spaced neighbor. (Closely
> spaced is well defined, it depends on the thickness of the copper traces
> used for the PCB board, generally only points closer than 1 mm can build
> obstacle lines.)
> -Take the convex hull of the remaining points -- that points should be
> endpoints of my red lines. Basic strategy may be to skip to the next
> point as long there is one -- the last is the other end of the line. But
> one problem is of course, that there is not always only one next point,
> because two lines may touch each other, or there may be some other
> random points close to the line.
>
> I think that may work, it is not very nice, and not very fast.
> I do not need exact results, but only an estimation of the larger
> obstacle structures.
>
> One other idea: There exists programs which can convert raster bitmap
> pictures into vector graphics, I think one of these is Incscape. I have
> no idea how that is done or about the name of the algorithm -- may that
> be available as a library?
>
> Best regards
>
> Stefan Salewski