std::vector and erase problem

[Billy Patton]

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

[Karl Heinz Buchegger]

Billy Patton wrote:

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

the end() iterator is not an iterator which can be used to dereference
into the vector. So if it1 equals vp->end() it still will be the end()
iterator after this: You don't set it to something else.

What you want is:

it1 = it + 1; // set middle point
if (it1 == vp->end()) // if middle is end
it1 = vp->begin();

it2 = it1 + 1; // set third the be first point of vec
if( it2 == vp->end() )
it2 = vp->end();

--
Karl Heinz Buchegger
kb******@gascad .at

[Karl Heinz Buchegger]

Karl Heinz Buchegger wrote:

Billy Patton wrote:

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

the end() iterator is not an iterator which can be used to dereference
into the vector. So if it1 equals vp->end() it still will be the end()
iterator after this: You don't set it to something else.

What you want is:

it1 = it + 1; // set middle point
if (it1 == vp->end()) // if middle is end
it1 = vp->begin();

it2 = it1 + 1; // set third the be first point of vec
if( it2 == vp->end() )
it2 = vp->end();

Sorry. The last lines obviously has to read
it2 = vp->begin();

--
Karl Heinz Buchegger
kb******@gascad .at

[Karl Heinz Buchegger]

Karl Heinz Buchegger wrote:

What you want is:

it1 = it + 1; // set middle point
if (it1 == vp->end()) // if middle is end
it1 = vp->begin();

it2 = it1 + 1; // set third the be first point of vec
if( it2 == vp->end() )
it2 = vp->end();

:-)
it2 = vp->begin();
--
Karl Heinz Buchegger
kb******@gascad .at

[Billy Patton]

Karl,
Thanks a bunch. It works perfectly.

On Mon, 25 Apr 2005, Karl Heinz Buchegger wrote:

Karl Heinz Buchegger wrote:

What you want is:

it1 = it + 1; // set middle point
if (it1 == vp->end()) // if middle is end
it1 = vp->begin();

it2 = it1 + 1; // set third the be first point of vec
if( it2 == vp->end() )
it2 = vp->end();

:-)
it2 = vp->begin();
--
Karl Heinz Buchegger
kb******@gascad .at

___ _ ____ ___ __ __
/ _ )(_) / /_ __ / _ \___ _/ /_/ /____ ___
/ _ / / / / // / / ___/ _ `/ __/ __/ _ \/ _ \
/____/_/_/_/\_, / /_/ \_,_/\__/\__/\___/_//_/
/___/
Texas Instruments ASIC Circuit Design Methodology Group
Dallas, Texas, 214-480-4455, b-******@ti.com

[Haro Panosyan]

Hi Billy,

Usually in this cases I do erasing in two steps, "for safety".
1.Find all erasable elements.
2.Erase backword, so indexing won't corrupt.

Here is a code which works fine, and call it by passing a reference
argument:
eliminate_point s1(vec);

void eliminate_point s1(vector<xy_t> & vp)
{
vector<int> IntVec;
for ( int i = 1; i < vp.size(); i++)
{
xy_t cur, prev, next;
cur = vp[i];
prev = vp[i-1];
next =vp[i+1];
if ( i == (vp.size()-1) )
next =vp[0];

cout << "***** Chercking element : " << cur.x << "," << cur.y << endl;
if ( (cur.x == prev.x) && (cur.x == next.x) )
{
IntVec.push_bac k(i);
cout << "***** Erasing element : " << cur.x << "," << cur.y << endl;
} else if ( (cur.y == prev.y) && (cur.y == next.y) )
{
IntVec.push_bac k(i);
cout << "***** Erasing element : " << cur.x << "," << cur.y << endl;
}

cout << "********** Erase Size = " << IntVec.size() << endl;

for ( int j = 0; j < IntVec.size(); j++)
vp.erase( vp.begin() + IntVec[IntVec.size()-1-j]);
}

-haro
ext 1883 in FL

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