Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Culling points from a polygon.


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
3 replies to this topic

#1 Sunsharior   Members   -  Reputation: 477

Like
0Likes
Like

Posted 28 August 2014 - 10:01 PM

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.

Attached Thumbnails

  • culling.png

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


Sponsor:

#2 taz0010   Members   -  Reputation: 276

Like
3Likes
Like

Posted 28 August 2014 - 11:46 PM

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).



#3 Sunsharior   Members   -  Reputation: 477

Like
0Likes
Like

Posted 29 August 2014 - 07:07 AM

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) );
}

Edited by Sunsharior, 29 August 2014 - 08:24 AM.


#4 Álvaro   Crossbones+   -  Reputation: 13684

Like
2Likes
Like

Posted 29 August 2014 - 01:34 PM

Here's what I would have done.
 
#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';
}





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS