-1

I'm looking for the most elegant, fastest and most efficient way to store several objects of the class Point with an index/key in any kind of collection.

Point contains attributes like index, posX, posY, area, neighborPoints[], AdjacentTriangles[], etc. and are used for creating a Delaunay-Triangulation and a Voronoi-Mesh.
For reasons of selection the single points should have an index in the collection, but don't need to be ordered.
While triangulating, I'm creating and deleting points. Also I want to loop through all points in the collection. Hence, the type of collection should be optimized for these operations.

In the beginning I used a List<Point> for storing the points and the occurence in the list was identical with the index of the point. In case of deleting one point of the list, I had to decrease all indices of the higher points. This sounds pretty inconvenient and time-consuming to me.

This is why I tried Dictionary<int, Point> afterwards. Here the indices are fixed and if I delete for example the second point, then all higher points, maybe Point[5] stays Point[5], just Point[1] is not there anymore (return is null). However, my runtimes are now even longer (see picture), although I don't have to do the index-shifting anymore. (Why is this?) runtimes

Using a Hashmap makes no sence to me, since then I would not be able to use calls like Point.posX (error code CS1061), because in a Hashmap the datatype is not set.

Do you have any suggestion for a efficient type of collection with faster performance?

Pixel_95
  • 954
  • 2
  • 9
  • 21
  • 1
    Do you really need a dictionary to have Key access? This may help you: [HashSet vs. List performance](https://stackoverflow.com/questions/150750/hashset-vs-list-performance) and [HashSet vs List vs Dictionary. HashSet](https://theburningmonk.com/2011/03/hashset-vs-list-vs-dictionary/), –  Nov 05 '19 at 16:37
  • Possible duplicate of [HashSet vs. List performance](https://stackoverflow.com/questions/150750/hashset-vs-list-performance) –  Nov 05 '19 at 16:41
  • 1
    I'm having trouble understanding how a Dictionary of just 5000 points could take so long to process. Could you post a simple version of your code so we can diagnose what's going on? – Slothario Nov 05 '19 at 16:53
  • @Slothario more or less its the Bowyer-Watson algorithm from the pseudocode in Wikipedia https://en.m.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm I have one collection for all points and one for all triangles – Pixel_95 Nov 05 '19 at 17:22

1 Answers1

0

You could sort the points along a hilbert curve. Basically the Bowyer-Watson algorithm use the hilbert curve.

Micromega
  • 12,486
  • 7
  • 35
  • 72