469,592 Members | 1,713 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,592 developers. It's quick & easy.

std::vector and erase problem

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
Jul 23 '05 #1
5 2199
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_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


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
Jul 23 '05 #2
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_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


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
Jul 23 '05 #3
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
Jul 23 '05 #4
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
Jul 23 '05 #5
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_points1(vec);

void eliminate_points1(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_back(i);
cout << "***** Erasing element : " << cur.x << "," << cur.y << endl;
} else if ( (cur.y == prev.y) && (cur.y == next.y) )
{
IntVec.push_back(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_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

Jul 23 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

5 posts views Thread by Sir_Ciph3r | last post: by
10 posts views Thread by Stefan Höhne | last post: by
1 post views Thread by Tino | last post: by
2 posts views Thread by Clement RAMBACH | last post: by
2 posts views Thread by Chris Thompson | last post: by
9 posts views Thread by Amadeus W. M. | last post: by
1 post views Thread by mscava | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.