On Thu, Jun 30, 2011 at 6:42 PM, Michael Mc Donnell michael@mcdonnell.dk wrote:
On Thu, Jun 30, 2011 at 4:10 PM, Henri Verbeet hverbeet@gmail.com wrote:
On 30 June 2011 14:49, Michael Mc Donnell michael@mcdonnell.dk wrote:
In init_edge_face_map I initialize an array of edge_face structs, and in find_adjacent_face I do a linear search through that array. I would like to replace the array with a hash table, so that the search time becomes constant. I've found a standard list (wine/list.h) and red-black tree implementation (wine/rbtree.h), but not a standard hash table implementation. Is there a standard hash table implementation, should I roll my own or find an LGPL'ed one?
I'm not sure if a hash table would be faster and how much, but an easy way to make the lookup cheaper would be to store the edge -> face map as a list for each vertex.
...
It's then mostly trivial to determine adjacency. This assumes most vertices are only part of a handful of edges, but I don't think that's unreasonable in practice.
Thanks for your suggestion. I think you're right that it is safe to assume that most vertices will only be a part of a few edges. I'll implement that for now.
I've implemented the look-up scheme that you described.
I have another question about my test. I've basically copied all the test data from my ConvertAdjacencyToPointReps test, and then just inverted the conditions. Should I merge the two tests, put the test data in a separate function, or just ignore the duplication?