STL list containing iterators
Author
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?
Author
It works well to make a vector of iterators and store in the list the index within the vector (pair<xy, int>). It's a little extra work but it's pretty clean.
Why do you need linked lists with cross links? The awkwardness and lack of clarity may be a sign you need a different data structure.
List nodes never change their location in memory, so you can just obtain and store pointers to elements. But what is the cross-linking for?
Author
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.
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.
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.
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.
Can't you just make a third list that contains a pair of iterators?
Now you can iterate over the list "intersection", which will contain iterators into each of the respective lists
[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
Why not just create the subtraction as a separate list? Are you familiar with the .splice() member function? You might find it useful here.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
