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_point s(vector<xy_t> *vp)

{

xy_t pt,pt1,pt2;

vector<xy_t>::i terator 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,p t2.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(p t);

pt.x = 300; pt.y = 0; vec.push_back(p t);

pt.x = 200; pt.y = 0; vec.push_back(p t);

pt.x = 100; pt.y = 0; vec.push_back(p t);

pt.x = 0; pt.y = 0; vec.push_back(p t);

pt.x = 0; pt.y = 100; vec.push_back(p t);

pt.x = 100; pt.y = 100; vec.push_back(p t);

pt.x = 200; pt.y = 100; vec.push_back(p t);

eliminate_point s(&vec);

vector<xy_t>::i terator 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