Hello everyone,

i am currently experiencing a problem figuring an algorithm to remove unneeded points from a polygon structure. Normally i wouldn't consider posting here, but this one got me stumped for quite a while.

So here is the problem:

I have a std::vector of a Point structure that form a convexe polygon.

Somes of the points in the vector may be not needed and could be removed without changing the shape of the polygon.

I need to figure out how to remove thoses unneeded points.

I have attached a picture representating this array of points.

As you can see, two point can be removed without changing the shape of the polygon (50,0 and 50,50)

Here is more informations:

The polygon will always be contained within a known range (xmin to xmax, ymin to ymax).

A point always have X or Y equals either known min-max value (can be both). So if xmin = 0, xmax = 100, ymin = 0, ymax = 50, the point (25,25) is impossible.

The polygon is not always a simple square or rectangle and can be anything convexe (Trapeze, triangle, losange, etc...).

The array will always be sorted clockwise but the first point is not always 0,0.

Here is what i already tried to solve this problem:

I tried looking for points in the middle of a side and removing them . I think the idea is good, but my logic is faulty, though.

This algorythm work for a simple rectange but fail with anything more complexe, like a trapeze.

////////////////////////////////////////////////////////////////////////// // void Cull( std::vector<CVector> &_vertices, float _xmin, float _ymin, float _xmax, float _ymax ) { // Work for a simple square or rectangle, but fail for anything else like a trapeze. if(_vertices.size()) { CVector lastvalidx = _vertices[0]; CVector lastvalidy = _vertices[0]; for(unsigned i = 1; i < _vertices.size();) { int n = i + 1 < _vertices.size() ? i + 1 : 0; // next point //Remove any point that is in the middle of a plane if( ( (_vertices[i].x != lastvalidx.x && (_vertices[i].x != _xmin && _vertices[i].x != _xmax) ) || (_vertices[i].y != lastvalidy.y && (_vertices[i].y != _ymin && _vertices[i].y != _ymax) ) ) ) { //remove the point, since it is not needed. _vertices.erase(std::remove(_vertices.begin(), _vertices.end(), _vertices[i]), _vertices.end()); } else { lastvalidx = _vertices[i]; lastvalidy = _vertices[i++]; } } } }

If you would take a look at my problem, i will be thankful. I will continue trying to solve it on my side in the meantime.

I really hope my problem is not too confusing to understand. If more information is needed, i will post it.

As always, thank you very much for your time.

**Edited by Sunsharior, 28 August 2014 - 10:05 PM.**