CGAL users discussion list

[Stefan Salewski <>]

On Fri, 2014-01-03 at 20:53 +0100, Stefan Salewski wrote:
> 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

-Start with a point of the convex hull, take the next point and all next
ones in that same direction (use 2d crossproduct to check for straight
line). Remove all intermediate points which have only two neighbors
(closely spaced neighbors), but keep the first, the last and points with
3 or more dense neighbors. Last and first build one desired line
segment.

- Remove again all points with no closely spaced neighbors.

- Build convex hull, start again with one point of the convex hull

- Repeat until no points left

(Generally I am only interested in lines built from at least 3 points,
so I may discard lines with only two points.)

May this work?