[RESOLVED] binary_search with return position and predicate

[_uj]

I´m wondering if there´s a better solution to this.

A standard solution to check for proximity is to overlay a coarse-grain pixel coordinate system over the vertex coordinate system.

Say the 5% difference is dx, dy in the vertex coordinate system. You can transform any vertex (x, y) to a corresponding pixel (i, j) like,

int i = (int) (x/dx);
int j = (int) (y/dy);

This simple formula transforms any vertex into a corresponding pixel. And if two vertexes are close and lie within the same dx, dy square they transform to the same pixel. Close vertexes have the same pixel, that's the basic idea.

So what you do is that you maintain a map (preferably unordered, that is hash based). For each pixel the map associates a list with all vertexes that transform to that pixel.

When you have a new vertex you transform it to a pixel. Then you check if that pixel is in the map. If it is you get a corresponding vertex-list with vertexes that have the same pixel. So you compare those.

Now a small complication. It's not enougth to check whether the pixel is in the map. You'll also have to check the pixel's 8 closest pixel neighbours. So all in all, when you have a new vertex you need to check the vertex-lists of 9 pixels in the map. Or rather at the most 9 vertex-lists. If a pixel and its 8 neighbours aren't in the map you know the corresponding vertex has no close vertexes.