How-to find surrounding polygon (Convex Hull)?

[KroMignon]

Hi all,

I wonder if Qt contains a function to find a surrounding polygon which includes a given list of 2D points?
Qt is so a big framework, perhaps there is such a function.

Does anyone know this?
Or is there another algebra library which include this kind of function?

[Bondrusiek]

Hi,
I found this example: https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/. Maybe this help you solve problem.

[KroMignon]

@Bondrusiek Thanks for your suggestion, but this is not what I want to do. I want to find the polygon which is surrounding a given list of 2D points.

Your example is to check if a point is inside a polygon, but I want to find this polygon!

[JonB]

@KroMignon
Does this make sense? There are many possible polygons which "surrounding a given list of 2D points". So what do you mean? One example would be a polygon which runs through every one of the points (i.e. has them as its vertices, with some algorithm so arcs do not cross each other), but won't there be many such not just one? I suppose another might "find the smallest area polygon which encloses a bunch of points"? Or smallest perimeter/arc length. Or smallest number of arcs?

I'm not a mathematician, but that's how it seems to me? It sounds a bit travelling salesman/Hamiltonian to me?!

[KroMignon]

@JonB said in How-to find surrounding polygon?:

I'm not a mathematician, but that's how it seems to me? It sounds a bit travelling salesman/Hamiltonian to me?!

Perhaps I am not finding right words, english is not my first language...
I have a list of points and I want to find the edge of a Polygon which will contains all those points. Like this:

Is this more clear?

[KroMignon]

@KroMignon I reply to myself, it seems that the algorithm I am look for is call "Convex Hull".

I found an implementation here: ==> https://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/

But perhaps someone could recommend me a better algorithm?

[mrjj]

@KroMignon
hi
the picture makes it really clear :)

https://math.stackexchange.com/questions/1143878/find-polygon-with-smallest-perimeter-that-encompasses-all-points

Maybe this algro
https://en.wikipedia.org/wiki/Graham_scan

c++ version here
https://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
(oh you already found :)

regarding the best algorithm.
They all have tradeoffs and really only matter if you have huge list of points.

[gbettega]

Hi
http://www.qhull.org/
Giovanni