473,597 Members | 2,835 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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

Jul 23 '05 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
6075
by: Sir_Ciph3r | last post by:
Can someone explain what is happening in the following code? #include <iostream> #include <vector> #include <map> using namespace std; int main() {
10
7060
by: Stefan Höhne | last post by:
Hi, as I recon, std::vector::clear()'s semantics changed from MS VC++ 6.0 to MS' DOT.NET - compiler. In the 6.0 version the capacity() of the vector did not change with the call to clear(), in DOT.NET the capacity() is reduced to 0.
1
2299
by: Tino | last post by:
I have a std::vector<int> which, after some initialization, has a fixed number of elements...after initialization I must do the following repeatedly: I remove an element which could be anywhere in the vector, and add another element which will always be at the end, ie. vector<int> v; int i, x; .... initialization
2
1708
by: Clement RAMBACH | last post by:
Hi, here is my problem: I have a std::vector< A* >. This vector contains pointers to the objects A i create (lets say about 4000 items). I do this several times in my application, and at the end of each pass, i have to delete about 3/4 of the objects (0x0 is put in the vector at the index of the object destroyed). The criteria of destruction isn't simple so it is not a "linear" destruction from the begin of the vector up to its end....
2
4757
by: Chris Thompson | last post by:
Hi I'm writing a p2p client for an existing protocol. I used a std::vector<char> as a buffer for messages read from the server. The message length is the first 4 bytes. The message code the second 4. The total message length is therefore 4 + message length. A number of messages work fine/as expected but there are consistant errors occuring. After a period
8
4884
by: Jason Heyes | last post by:
Does the STL have a function like this one? template <typename T> void remove(std::vector<T> &v, std::vector<T>::size_type index) { std::swap(v, v.back()); v.resize(index); } Unlike std::vector::erase, it calls T::operator= only three times no matter
9
5189
by: Amadeus W. M. | last post by:
I have a vector from which I want to erase elements between iterators i,j. If i<j, everything works as expected, but if j>i, an insertion is actually performed. Example: vector<double> x(10); vector<double>::iterator i=x.begin()+2, j=x.begin()+6; x.erase(i,j); // i<j, ok, erases 4 elements. x.erase(j,i); // j>i, no error, just inserts 4 elements.
1
5159
by: mscava | last post by:
How can I make this construction valid? It still gives me error about no matching function std::sort(...). I made a little search and wrong thing is probably the predicate... template <typename TT Polygon<T:: Height() const { class BinPred : public std::binary_function< Vector2D<T>, Vector2D<T>, bool > {
5
2046
by: Anil | last post by:
I am facing problem while erasing an elemet from stl vector when its size is 2. It works fine when SIZE 2. Can anybody help me in this?? Following is the sample code which i tried. #include <iostream> #include <vector> using namespace std; #define SIZE 2
13
7469
by: thomas | last post by:
suppose I will delete an element pointed to by "iter". like this: vector<ints; for(vector<int>::iterator iter=s.begin(); iter!=s.end(); iter++){ if(*iter==3) s.erase(iter); //A } in line A, if element by "iter" is erased, will "iter" point to the
0
7967
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
7885
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
8272
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
8031
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8258
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
6687
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
5847
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
3923
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
1493
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.