Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Curve or path reconstruction question

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Curve or path reconstruction question


Chronological Thread 
  • From: "Sebastien Loriot (GeometryFactory)" <>
  • To:
  • Subject: Re: [cgal-discuss] Curve or path reconstruction question
  • Date: Tue, 07 Jan 2014 10:11:42 +0100
  • Organization: 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








Archive powered by MHonArc 2.6.18.

Top of Page