Creating complex concave polygonal surface from points

[Jishnu]

Hi All,

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!

[rexthor]

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.

This may only be semi-related to what you were looking for, but there are lots of other posts here that may have hints, such as: How to triangulate a surface from point cloud - #4 by Paulo_Carvalho.

[Jishnu]

Hi rexthor, I will check this. Thank you.

[rexthor]

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.

[Paulo_Carvalho]

Hello,

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.

For sparse, dubious point clouds like the example, you could try this: The Concave Hull. Creating a cluster border using a… | by João Paulo Figueira | Towards Data Science (code in Python) or this: Python Concave Hull Polygon of a set of lines - Stack Overflow.

take care,

Paulo

[Jishnu]

Hi Paulo Carvalho,

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

[rexthor]

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?

[Jishnu]

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

[dgobbi (David Gobbi)]

Hi 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.

David

[Paulo_Carvalho]

Hello, J,

Well, if you know beforehand the point order, then your problem is trivial. Just start with the first point and connect them by lines following the order: https://kitware.github.io/vtk-examples/site/Python/GeometricObjects/PolyLine/

best,

PC

[Paulo_Carvalho]

Once you have a vtkPolyData representing the boundary, you can use 2D Delaunay to fill it with trinagle faces: https://www.programcreek.com/python/example/112796/vtk.vtkDelaunay2D

[rexthor]

You asked about how to set normals - I can empathize with being new to VTK. You would set normals for some object roughly in this manner:

# python
normals = vtkFloatArray()
normals.SetNumberOfComponents( 3 )
normals.SetNumberOfTuples(however_many_points_you_have)
normals.SetName("Normals")
normals.InsertNextTuple([0, 1, 0])
...

otherthing.GetPointData().SetNormals(normals)

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.

[Jishnu]

Hi @dgobbi David Gobbi,
I tried using vtkContourTriangulator, and it successfully solved my problem. Thank you very much.

.

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.