Sign in to follow this  
adamjmac

STL list containing iterators

Recommended Posts

Hi, I'd like to make two linked lists with elements that can reference each other: typedef list< pair<xy, iter> >::iterator iter; list< pair<xy, iter> > list1; list< pair<xy, iter> > list2; iter it = list1.insert(list1.begin(), make_pair(xy(0,0), NULL)); list2.insert(list2.begin, make_pair(xy(0,0), it)); As you can see, I cannot define the iterator type since the list itself needs to be defined, which needs the iterator, and so on. Is there a base type of iterator that I can use, or anything I can cast between? I tried void* but it can't be casted. I can store a pointer to the address of an iterator (by casting (&it) to void *), but this would involve making a vector of iterators. Is this the best way?

Share this post


Link to post
Share on other sites
A pointer to the elements gives me the data, but I need the node in the linked list so that I can traverse forwards and backwards within the list.

The problem is to calculate intersecting polygons. I store each vertex in a linked list, so that I can travel forwards/backwards, and efficiently remove or add vertices on the fly.

I find all the intersection points, and add them to the lists for both polygons as I go. For each intersection, I need the cross-link information of how to get to the associated vertex on the other polygon.

Then, to find the subtraction of two polygons, I can travel one counter-clockwise until I find an intersection, switch over to the other polygon, and travel that clockwise.

This approach works, but I ran into trouble in the special cases, like when I try and subtract a polygon from itself, or deal with colinear edges. I found a nice library called GPC (Generic Polygon Clipper) which works very well so far.

Share this post


Link to post
Share on other sites
I think you've over complexified. I know "just use a simple pointer" is considered scary advice in some circles, but if you have element A and B in separate lists, and you want to get from A to B, having A simply point to B seems simple and obvious. Intrusive, yes, but that's not as evil as some make it out to be.

It's possible that what you really want is a lattice, where the intersection points have two parents and two children and everything else is essentially linked lists, but I don't know if STL supports them directly.

I had a problem that involved computing many unions and intersections of simple polygons (and sometimes circles), and I went far, far out of my way to avoid solving the polygon intersection problem in pure form. Ask yourself if you *need* to do this. I found I didn't.

Share this post


Link to post
Share on other sites
Can't you just make a third list that contains a pair of iterators?

[source language="cpp"]

typedef std::list<point> poly_type;
typedef std::pair<poly_type::iterator, poly_type::iterator> iter_pair;
typedef std::list<iter_pair> intersection_type;

poly_type poly1;
poly_type poly2;
intersection_type intersection;

bool done = false;
while (!done)
{
//By searching poly1 and poly2 in parallel, suppose you find that
//the line formed by v_a and v_b from poly1 intersect the line formed
//by v_k and v_j from poly2, at the point x. Furthermore, since these
//vertices were found by searching through the lists, WLOG we can assume
//that v_k, v_j, v_a, and v_b are iterators into their respective lists,
//rather than actual points.

//If the intersection point was in poly1, don't re-insert it. Either way
//when this is done v_k is an iterator inside poly1 to the intersection
//point and the insert operation takes constant time due to the hint.
if (*v_a != x)
v_a = poly1.insert(v_a, x);

//If the intersection point was in poly2, don't re-insert it. Either way
//when this is done v_k is an iterator inside poly2 to the intersection
//point and the insert operation takes constant time due to the hint.
if (*v_k != x)
v_k = poly2.insert(v_k, x);

intersection.insert(std::make_pair(v_a, v_k));
}




Now you can iterate over the list "intersection", which will contain iterators into each of the respective lists

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this