I am working on a project where I need to generate surfaces from user-defined points to create polygons. For convex polygons, I am able to generate surfaces using the Delaunay2D triangulation method without any issues. However, when I try to generate surfaces for concave polygons, I am encountering some problems.

For example, when I define points on a concave polygon, such as the one shown in the image below, and generate a surface using Delaunay2D, I get a filled surface that does not accurately represent the polygon:

I have tried many other methods for surface generation, but I have not been able to figure out the right way to perform surface generation for concave polygons.

Can anyone suggest a method for generating surfaces from user-defined points for concave polygons? Any help would be greatly appreciated. Thank you in advance!

I think Delaunay triangulation will always give you a convex hull. Iâ€™m not a mathematician, but vtkDelaunay2D (or anything that uses Delaunay triangulation) will always give you a convex output.

There are probably algorithms that will work for you, but I think that all of them will need for you to give them hints about what is â€śinsideâ€ť and â€śoutsideâ€ť for your polygon. That might be something like a signed distance function, or distance gradients evaluated at the polygon points.

Probably duplicates what was in the link I posted, but this would be where I would start: vtkPoissonReconstruction. Youâ€™ll probably have to compile something to get it working â€¦ I gather from the example that you should provide normals (or estimates of normals) at the points. If you donâ€™t have them, they can be estimated with vtkPCANormalEstimation â€¦ but as they say, your mileage may vary.

Well, the convex hull is a unique solution, thatâ€™s why itâ€™s relatively easy to find algorithmically. Concave hulls are another game entirely. Taking your example, you could easily fit a great number of different concave polygons to that point set because itâ€™s so sparse. For example, the opening of the â€śCâ€ť shape could be to one side, upwards and so on. All those shapes are equally valid answers. So, you need to tell the algorithm what you want in the result in addition to being concave (e.g. the barycenter must be outside, the perimeter/area ratio must be maximal, can have points inside, no manifolds, no crossings, etc.). These extra parameters may allow your algorithm to converge to a single answer or to at least a small number of them for some tie-breaking heuristics to decide. Of course, the denser the points the more â€śobviousâ€ť is the answer.

What I understand from your answer is that if I have a cluster of points, it is difficult to predict the way in which these points will form a polygon, right? In my case, I know the sequence in which these points form the polygon (as shown in the above image). My problem is that I donâ€™t know how to generate a surface from these points. Could you please help me to understand how to approach this problem.
Thank you,
Jishnu

So, if it is a curve in the plane, and you know the order that the points are in, you could estimate an outward-pointing normal by threading a curve through the points and using either the left-hand or right-hand normal to the curve. Then you might be able to use vtkPoissonReconstruction?

Hi rexthor,
I am trying with the vtkPoissonReconstruction based on your previous suggestion. But, seems I am unable to figure out how to set the normals. If possible can you further elaborate on what you mean by â€śyou could estimate an outward-pointing normal by threading a curve through the points and using either the left-hand or right-hand normal to the curveâ€ť, I have not much exposure to surface creation in vtk.
Thank you,
Jishnu

This might be a silly question, but are your points already in the correct order? What I mean is, If you connect them with line segments, will they show the outline of the polygon, like in your first image? If so, then you can use vtkContourTriangulator or constrained Delaunay triangulation.

You could estimate your normals by rotating (by 90 degrees about z) the tangent vector between each point. Essentially estimating the normal vector from the TNB frame. That is much less elegant than Pauloâ€™s answer.

Thank you very much @Paulo_Carvalho and @rexthor for patiently hearing my issue and helping me to find a solution.
Thank you all once again for your time and assistance.