View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

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

3 replies to this topic

### #1Sunsharior  Members

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)

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

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

### #2taz0010  Members

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

### #3Sunsharior  Members

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  Members

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];
Point const &next = (read_index + 1u) < n ? polygon[read_index + 1u] : polygon[0];
if (signed_area_times_2(previous, current, next) >= 1e-4f)
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.