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.

I have solved problems very similar to this by using the "Signed triangle area" formula.

http://geomalgorithms.com/a01-_area.html

All you need to do is loop over the points in the shape, and test the triangle at each vertex. i.e. for vertex v, you form the triangle with vertices {v-1, v, v+1}. You know the shape has vertices in a straight line if the triangle area is very close to zero. Unfortunately you can't rely on using an exact comparison against zero when dealing with floating point numbers, so you compare against epsilon (+-0.000001 or whatever suits).

Thank you. It worked like a charm!

Here is the code for anyone that could need it later.

#define EPSILON 0.0001f
//////////////////////////////////////////////////////////////////////////
//Culling mean removing unneeded vector.
void Cull(std::vector<CVector> &_val)
{
    if(_val.size())
    {
        for(int i = 0; i < static_cast<int>(_val.size());)
        {
            int n = i + 1 < _val.size() ? i + 1 : 0; //next
            int l = i - 1 >= 0 ? i - 1 : _val.size() - 1; //last
            
            if((SignedArea(_val[l], _val[i], _val[n]) * 0.5f) < EPSILON)
                _val.erase(std::remove(_val.begin(), 
                                       _val.end(), 
                                       _val[i]), 
                                       _val.end());
            else 
                i++;           
        }
    }   
}

//////////////////////////////////////////////////////////////////////////
//
float SignedArea( CVector _a, CVector _b, CVector _c )
{
    return ( (_b.x - _a.x) * (_c.y - _a.y)
           - (_c.x - _a.x) * (_b.y - _a.y) );
}

#include <iostream>
#include <vector>

struct Point {
  float x, y;
  
  Point(float x, float y) : x(x), y(y) {
  }
};

std::ostream &operator<<(std::ostream &os, Point const &p) {
  return os << '(' << p.x << ',' << p.y << ')';
}

float signed_area_times_2(Point const &a, Point const &b, Point const &c) {
  return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

typedef std::vector<Point> Polygon;

void remove_redundant_vertices(Polygon &polygon) {
  size_t n = polygon.size();
  size_t write_index = 0u;
  
  Point previous = polygon[n-1];
  for (size_t read_index = 0u; read_index < n; ++read_index) {
    Point const &current = polygon[read_index];
    Point const &next = (read_index + 1u) < n ? polygon[read_index + 1u] : polygon[0];
    if (signed_area_times_2(previous, current, next) >= 1e-4f)
      polygon[write_index++] = polygon[read_index];
    else
      previous = current;
  }
  polygon.erase(polygon.begin() + write_index, polygon.end());
}

int main() {  
  Polygon polygon = {
    Point(0.0f, 0.0f), Point(50.0f, 0.0f), Point(100.0f, 0.0f),
    Point(100.0f, 50.0f), Point(50.0f, 50.0f), Point(0.0f, 50.0f)
  };
  
  remove_redundant_vertices(polygon);
  
  for (auto vertex : polygon)
    std::cout << vertex << '\n';
}