Get 2d alpha shape boundary vertices from set of points

Question

I haven't used CGAL before, and all I want is a function that takes a 2d set of points and alpha parameter, and returns a vector of points that represents the bounding polygon. I can make an alpha shape object, but I don't know how to get a vector from there. EDIT: One caveat is that there may be several disconnected components, and I would want to know that somehow. Is there a neat solution such that I get an ordered vector of vertices for each polygon?

score 1 · Answer 1 · answered Jun 14 '17 at 16:24

I've faced the same problem and finally ended up sorting all vertices like suggested in the top answer here. Maybe, it would help someone.

I'm not exactly satisfied by this approach, though. @Flowers, do you still have code with which you iterated over edges? I couldn't manage to do this. Sorry, I have not enough reputation to ask it in a comment.

score 0 · Answer 2 · answered Jun 08 '15 at 07:31

0

Try something like this:

Alpha_shape_2 A(points.begin(), points.end(),
                FT(10000),
                Alpha_shape_2::GENERAL);

std::vector<Alpha_shape_2::Point> points;

for (Alpha_shape_2::Alpha_shape_vertices_iterator
       avit = A.alpha_shape_vertices_begin(),
       avit_end=A.alpha_shape_vertices_end();
       avit!=avit_end; ++avit)
{
  points.push_back(avit->point());
}

See the reference manual of the function here.

answered Jun 08 '15 at 07:31

sloriot

6,070
18
27

Thanks, but that's pretty much what I have right now, but the vertices don't seem to come in order. – Flowers Jun 08 '15 at 17:12
What order are you looking for? – sloriot Jun 09 '15 at 08:31
For each polygon, I would like to get the vertices in cw or ccw order – Flowers Jun 09 '15 at 19:34

score 0 · Accepted Answer · answered Jun 09 '15 at 18:47

0

Ended up going over the edges instead and used that to find the vertices in order.

answered Jun 09 '15 at 18:47

Flowers

191
1
9

Get 2d alpha shape boundary vertices from set of points

3 Answers3