CGAL users discussion list

[Stefan Salewski <>]

On Tue, 2014-01-07 at 10:11 +0100, Sebastien Loriot (GeometryFactory)
wrote:
> 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.

Yes, the Alpha_Shapes are interesting.
But I think they can help me only finding all the dense points which are
part of my desired line segments, but not to separate that point set
into the lines itself, i.e. finding the endpoints of the lines.

I have played with the ipelet -- works fine to highlight all the points
of my desired lines. (I tried to make a screenshot, but got an empty
picture, may be related to GL drawing.)

But finding the points is an easy task, in the delaunay triangulation I
can select the points which have near by neighbors. Then generation
lines from that reduced point set is a little bit more complicated:
One problem is, when a point has more than two close neighbors (two or
more lines touch each other, or a random point is close by accident).
The other problem may occur when the points have minimal deviation from
the exact line shape -- for that case crossproduct is not exactly zero.
But coding such simple line detection should not be too complicated, and
speed is not really a concern, I have only a few hundred or a few
thousand points. But it is good to know that there is no ready made
smart solution available before starting coding.

Best regards,

Stefan Salewski