Best Algorithm to find the edges (polygon) of vertices

Question

I have a large array of vertices, some of them are edges, some are redundant (inside the shape) and I want to remove those.

The simplest algorithm I could think of is checking one by one if they hit the shape formed by the others. But it should be a very slow algorithm.

I thought about picking one from the edge (the one farthest from origin per example) and calculate the longest path from this start... should get the edge path, right?

Any suggestion?

Stenotypy

Do you want a polygon that covers all the points, or do you want the smallest (in terms of area) polygon that covers all the points? – Sympathin

@sykora, a polygon that covers all the points. graham scan seems valid. thanks. – Stenotypy

Answer 1

The trick with polyhedral algorithms is choosing one that fits with your input and your desired output, since there is more than one way to represent a polyhedron and converting between the representations can be expensive. In this case, you are starting with points and want to end with vertices, so the Graham scan algorithm to compute the vertices of the convex hull should do the trick, though it might take some effort to extend it past the 2-D case. It's O(n log n) in the number of input vertices.

Eelgrass

THe Graham scan basically gives you the convex hull. – Mullens

Answer 2

I do not know what the best algorithm to find that polygon is, but the polygon you are looking for is called "Convex Hull".

By searching for that, you should find a matching algorithm.

Siebert

I don't think he is looking for the convex hull, since he wants the edges of the polygon formed by his vertices. A convex hull would exclude even some that he might want. – Sympathin

"some are redundant (inside the shape) and I want to remove those." – Siebert

i'm not looking to reduce the edges... I'm looking into building a polygon from a vertices collection that has some of them redundant. – Stenotypy

Hi, how do i get back the vertices that i used to insert a polygon into mysql database? – Crown

Answer 3

The Convex Hull is one of the more researched problems of Computational Geometry. The Graham Scan is one of the simpler convex hull algorithms, but certainly not the only one. The Gift-wrapping Algorithm, also called Jarvis' March, is the simplest I know of. The Stony Brook algorithm repository has several implementations of convex hull algorithms in C and C++. Geometry in Action shows mainly applications of convex hulls. Here's a collection of low-dimensional and arbitrary-dimensional convex hull calculating programs.

Coakley