std::vector and erase problem

B

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_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).x,(*vp).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, (e-mail address removed)
 
K

Karl Heinz Buchegger

Billy said:
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).x,(*vp).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
Click to expand...


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();
 
K

Karl Heinz Buchegger

Karl said:
Billy said:
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).x,(*vp).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
Click to expand...


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();
Click to expand...


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

Karl Heinz Buchegger

Karl said:
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();
Click to expand...

:)
it2 = vp->begin();
 
B

Billy Patton

Karl,
Thanks a bunch. It works perfectly.

:)
it2 = vp->begin();
Click to expand...

___ _ ____ ___ __ __
/ _ )(_) / /_ __ / _ \___ _/ /_/ /____ ___
/ _ / / / / // / / ___/ _ `/ __/ __/ _ \/ _ \
/____/_/_/_/\_, / /_/ \_,_/\__/\__/\___/_//_/
/___/
Texas Instruments ASIC Circuit Design Methodology Group
Dallas, Texas, 214-480-4455, (e-mail address removed)
 
H

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_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;
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).x,(*vp).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, (e-mail address removed)
Click to expand...
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

How should unordered_map be used correctly ... ? 16
Paranoid about style/elegance and function size, please quell 35
comp.lang.c Answers to Frequently Asked Questions (FAQ List) 1

Members online

Total: 35 (members: 1, guests: 34)
Robots: 352

Forum statistics

Threads
473,767
Messages
2,569,571
Members
45,045
Latest member
DRCM

Latest Threads

Top