I have a polygon loaded into a vector. I need to remove redundant points.
Here is an example line segment that shows redundant points
a---------b--------c--------d
Both b and c are not necessary. The function below is supposed to remove this
It seems to work unitl the last point is removed. It seems to have something
to do with the fact that vp->end() is a redundant point. THe test case is code
so that "a" is the initial point, c,d,g,h are redundant and need to be removed.
f-------g--------------h---------------a
| |
| |
e-------d--------------c---------------b
THis has to be an obvious error that I can't see. I've rewritten this function
5 times and get the same results. I can't see the trees for the forest :(
#include <stdio.h>
#include <vector>
using namespace std;
typedef struct { long x,y; } xy_t;
typedef xy_t *xy_p;
/*
* The purpose of the function is to remove redundant
* points in a vector of points representing a closed
* polygon.
* It will look at 3 points at a time.
* If the x values are the same then the middle point is
* redundant and should be eliminated.
* If the y values are the same then the middle point is
* redundant and should be eliminated.
*/
void eliminate_points(vector<xy_t> *vp)
{
xy_t pt,pt1,pt2;
vector<xy_t>::iterator it,it1,it2;
it = vp->begin();
while (it != vp->end())
{
size_t i;
fprintf(stderr,"the points in vec : ");
for (i = 0; i < vp->size(); i++)
fprintf(stderr," %d,%d",(*vp)[i].x,(*vp)[i].y);
fprintf(stderr,"\n");
it1 = it + 1; // set middle point
if (it1 == vp->end()) // if middle is end
it2 = vp->begin(); // set third the be first point of vec
else it2 = it1 + 1; // set third to be next, after middle
pt = *it; // value of first point
pt1 = *it1; // value of middle point
pt2 = *it2; // value of third point
fprintf(stderr," checking points %d,%d %d,%d %d,%d\n"
,pt.x,pt.y,pt1.x,pt1.y,pt2.x,pt2.y);
if (pt.x == pt1.x && pt.x == pt2.x) // verticle line
vp->erase(it1); // remove middle point
else if (pt.y == pt1.y && pt.y == pt2.y) // horizontal line
{
vp->erase(it1); // remove middle point
fprintf(stderr," erasing %d,%d\n",pt1.x,pt1.y);
}
else
it++; // no point removed this cycle increment base iterator
if (it == vp->end()) break;
}
}
int main(void)
{
vector<xy_t> vec;
xy_t pt;
pt.x = 300; pt.y = 100; vec.push_back(pt);
pt.x = 300; pt.y = 0; vec.push_back(pt);
pt.x = 200; pt.y = 0; vec.push_back(pt);
pt.x = 100; pt.y = 0; vec.push_back(pt);
pt.x = 0; pt.y = 0; vec.push_back(pt);
pt.x = 0; pt.y = 100; vec.push_back(pt);
pt.x = 100; pt.y = 100; vec.push_back(pt);
pt.x = 200; pt.y = 100; vec.push_back(pt);
eliminate_points(&vec);
vector<xy_t>::iterator it;
it = vec.begin();
short cnt = 0;
while (it != vec.end())
{
pt = *it;
printf("%d. %-3d %d\n",cnt,pt.x,pt.y);
it++;
cnt++;
}
/*
* what should be returned is
* 300,100 , 300,0 , 0,0 , 0,100
* to complete a rectangle.
*/
return 1;
}
Results:
the points in vec : 300,100 300,0 200,0 100,0 0,0 0,100 100,100
200,100
checking points 300,100 300,0 200,0
the points in vec : 300,100 300,0 200,0 100,0 0,0 0,100 100,100
200,100
checking points 300,0 200,0 100,0
erasing 200,0
the points in vec : 300,100 300,0 100,0 0,0 0,100 100,100
200,100
checking points 300,0 100,0 0,0
erasing 100,0
the points in vec : 300,100 300,0 0,0 0,100 100,100 200,100
checking points 300,0 0,0 0,100
the points in vec : 300,100 300,0 0,0 0,100 100,100 200,100
checking points 0,0 0,100 100,100
the points in vec : 300,100 300,0 0,0 0,100 100,100 200,100
checking points 0,100 100,100 200,100
erasing 100,100
the points in vec : 300,100 300,0 0,0 0,100 200,100
checking points 0,100 200,100 200,100
erasing 200,100
the points in vec : 300,100 300,0 0,0 0,100
checking points 0,100 200,100 300,100
erasing 200,100
0. 300 100
1. 300 0
2. 0 0
___ _ ____ ___ __ __
/ _ )(_) / /_ __ / _ \___ _/ /_/ /____ ___
/ _ / / / / // / / ___/ _ `/ __/ __/ _ \/ _ \
/____/_/_/_/\_, / /_/ \_,_/\__/\__/\___/_//_/
/___/
Texas Instruments ASIC Circuit Design Methodology Group
Dallas, Texas, 214-480-4455, b-******@ti.com
