Mon, 04/19/2004 - 18:01
Forums:
I need to iterate over the vertices of a TopoDS_Shape. I tried to use iterators (TopExp_Explorer) or MapShape (a method of TopExp), but, in the two cases, each vertices is duplicated several times. Personnaly, I would like to have only one occurrence of each vertice.
More generally, it would be useful to do it for every kind of cells. For instance, getting all the edges of a solid.
I hope someone could help me. thanks,
franck
Mon, 04/19/2004 - 18:18
When I need to avoid duplicates in an iteration, I usually create a TopTools_MapOfShape. On each item, skip it if it is already in the map. If not in the map, place it in the map and process it. This also prevents processing the same edge twice when it has FORWARD and REVERSE orientation on 2 faces.
Tue, 04/20/2004 - 10:22
Thanks for your explanation.
To be precise, you begin by creating a TopTools_MapOfShape, then you traverse it and for each item, you look if it already in the map. To do that, you necessary program a double loop.
Currently, I process a similar method, but I would like to reduce complexity. Indeed, in the worst case, such an algorithm must be O(n2), but more generally O(nlog n) + the complexity of creating a TopTools_MapOfShape.
Tue, 04/20/2004 - 10:23
Thanks for your explanation.
To be precise, you begin by creating a TopTools_MapOfShape, then you traverse it and for each item, you look if it already in the map. To do that, you necessary program a double loop.
Currently, I process a similar method, but I would like to reduce complexity. Indeed, in the worst case, such an algorithm must be O(n2), but more generally O(nlog n) + the complexity of creating a TopTools_MapOfShape.
Tue, 04/20/2004 - 15:18
If I understand your not correctly, you are concerned that the map lookup is a O(n) algorithm. Creating the "double loop" when looking items up in the map. This should not be the case as the map is implemented as a hash table. When looking a shape up in the map, the shape is transformed into a map index and accessed in O(1) time. At least, that is the theory.
Wed, 04/21/2004 - 11:38
I think you're right, I confused my self topological data structure with Open Cascade Ones.