The program uses vertices in R^2 as nodes and there are edges between nodes, and ultimately more is built from there. There are a high number of circuitous ways that a point (x,y) in R^2 might be reached that may rely on layer after layer of trig functions. So it makes sense to define one vertex as the canonical vertex for all points in a square with side length 2*epsilon centered at the point. So various calculations happen, out comes a point (x,y) where I wish to put a vertex, a vertex factory checks to see if there is already vertex deemed as canonical that should be used for this point, if so it returns that vertex, if not a new vertex is created with the coordinates of the point and that vertex is now deemed canonical. I know this can lead to ambiguities given the possibility for overlap of the squares but that is immaterial for the moment, epsilon can be set to make the probability of such a case vanishingly small.
Clearly a list of canonical vertices must be kept.
I have working implementations using List<Vertex> and HashSet<Vertex>, however the vertex creation process seems to scale poorly when the number of vertices grows to over over 100,000 and incredibly poorly if the number gets anywhere near 1,000,000.
I have no idea how to efficiently implement the VertexFactory. Right now Vertex has method IsEquivalentTo(Vertex v) and returns true if v is contained in the square around the instance vertex calling it, false otherwise.
So the the vertex creation process looks like this:
Some point (x,y) get calculated and requests a new vertex from the vertex manager.
VertexManager creates a temporary vertex temp then uses a foreach to iterate over every vertex in the container using IsEquivalentTo(temp) to find a match and return it, if no match is found then add temp to the container and return it. I should state that if a match is found obviously it breaks out of the foreach loop.
I may be way off but my first guess would be put an order on the vertices such as
v1 < v2 iff ( (v1.X < v2.X) || ( (v1.X == v2.X) && (v1.Y < v2.Y) ) )
and then store the vertices in a sorted container. But to be honest I do not know enough about about the various containers to know which is the most appropriate for the purpose, standard C# best practices, etc
Edit:
I cannot mark the comment as an answer so thanks to GSerg whose comment guided me to kd-trees. This is exactly what I was looking for.
Thanks
