# Creating complex concave polygonal surface from points
**URL:** https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959
**Category:** Support
**Tags:** python
**Created:** [March 14, 2023, 4:09am UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959 "2023-03-14T04:09:55Z")
**Posts on this page:** 13
**Page:** 1
### Author:  [@Jishnu](https://discourse.vtk.org/u/Jishnu)
#### Post date: [March 14, 2023, 4:09am UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959/1 "2023-03-14T04:09:55Z")
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!
---
### Author:  [@rexthor](https://discourse.vtk.org/u/rexthor)
#### Post date: [March 14, 2023, 2:58pm UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959/2 "2023-03-14T14:58:58Z")
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](https://discourse.vtk.org/t/how-to-triangulate-a-surface-from-point-cloud/2240/4).
---
### Author:  [@Jishnu](https://discourse.vtk.org/u/Jishnu)
#### Post date: [March 14, 2023, 3:06pm UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959/3 "2023-03-14T15:06:25Z")
Hi rexthor, I will check this. Thank you.
---
### Author:  [@rexthor](https://discourse.vtk.org/u/rexthor)
#### Post date: [March 14, 2023, 3:16pm UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959/4 "2023-03-14T15:16:52Z")
Probably duplicates what was in the link I posted, but this would be where I would start: [vtkPoissonReconstruction](https://kitware.github.io/vtk-examples/site/Cxx/Points/PoissonExtractSurface/). 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.
---
### Author:  [@Paulo\_Carvalho](https://discourse.vtk.org/u/Paulo_Carvalho)
#### Post date: [March 14, 2023, 6:56pm UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959/5 "2023-03-14T18:56:20Z")
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](https://towardsdatascience.com/the-concave-hull-c649795c0f0f) (code in Python) or this: [Python Concave Hull Polygon of a set of lines - Stack Overflow](https://stackoverflow.com/questions/57260352/python-concave-hull-polygon-of-a-set-of-lines).
take care,
Paulo
---
### Author:  [@Jishnu](https://discourse.vtk.org/u/Jishnu)
#### Post date: [March 15, 2023, 1:07pm UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959/6 "2023-03-15T13:07:50Z")
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
---
### Author:  [@rexthor](https://discourse.vtk.org/u/rexthor)
#### Post date: [March 15, 2023, 1:11pm UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959/7 "2023-03-15T13:11:13Z")
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`?
---
### Author:  [@Jishnu](https://discourse.vtk.org/u/Jishnu)
#### Post date: [March 15, 2023, 1:18pm UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959/8 "2023-03-15T13:18:25Z")
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
---
### Author:  [@dgobbi](https://discourse.vtk.org/u/dgobbi)
#### Post date: [March 15, 2023, 2:25pm UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959/9 "2023-03-15T14:25:57Z")
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](https://kitware.github.io/vtk-examples/site/Cxx/Modelling/ContourTriangulator) or [constrained Delaunay triangulation](https://kitware.github.io/vtk-examples/site/Cxx/Filtering/ConstrainedDelaunay2D).
David
---
### Author:  [@Paulo\_Carvalho](https://discourse.vtk.org/u/Paulo_Carvalho)
#### Post date: [March 15, 2023, 5:17pm UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959/10 "2023-03-15T17:17:47Z")
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/](https://kitware.github.io/vtk-examples/site/Python/GeometricObjects/PolyLine/)
best,
PC
---
### Author:  [@Paulo\_Carvalho](https://discourse.vtk.org/u/Paulo_Carvalho)
#### Post date: [March 15, 2023, 5:21pm UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959/11 "2023-03-15T17:21:43Z")
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](https://www.programcreek.com/python/example/112796/vtk.vtkDelaunay2D)
---
### Author:  [@rexthor](https://discourse.vtk.org/u/rexthor)
#### Post date: [March 15, 2023, 7:02pm UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959/12 "2023-03-15T19:02:03Z")
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:
```auto
# 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](https://en.wikipedia.org/wiki/Frenet%E2%80%93Serret_formulas). That is _much less elegant_ than Paulo’s answer.
---
### Author:  [@Jishnu](https://discourse.vtk.org/u/Jishnu)
#### Post date: [March 16, 2023, 5:01am UTC](https://discourse.vtk.org/t/creating-complex-concave-polygonal-surface-from-points/10959/13 "2023-03-16T05:01:53Z")
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.