any fast way to find the range?

[kfc123456]

I have bunch of coordinates stored in a vector as follows

// the first number is for x coordinate and the second one is for y 
std::vector< pair<double, double> > xy; 

there will be at least 1000000 points stored in the vector. Those points will makeup, more or less, a "close area" and my purpose is to verify if a given point is contained in that area or not. For doing that, one way I can think of is to search all points with x within a certain range around the given points first and then check if the range of the resulting y coordinates contains the y component of the given point too. Firstly, I sort the vector on x

bool myfun(pair<double, double> a, pair<double, double> b) {return (a.first<b.first);}
sort(xy.begin(), xy.end(), myfun);

the sorting function doesn't take too long. After the vector sorted, now I can search the vector on the x coordinates to locate the range near the given X (says X0)

double miny = 10000.0;
double maxy = -10000.0;
double  X0, Y0;
//X0 and Y0 is given point being verified
for (int j=0; j<xy.size(); j++)
{
  x = xy.first;
  if (abs(x-THETA)<0.001)
  {
    y = xy.second;
    if (y>maxy) maxy=y;
    if (y<miny) miny=y;
  }
  else if (x-X0>1.0) break; // since x is in ascending order, when diff b/w x and X is larger than 1.0, just stop the loop
}

Now, we get miny and maxy, if Y0 is within [miny, maxy] then we consider that the point (X0, Y0) is contained in the bound denotes by all points given in xy.

If I have only one point (X0, Y0) to verify, this algorithm won't be too bad. But in my case, I have sooooo many points to verify and it is really slow to run the above algorithm. Is that any better way to do the searching, maybe with some STL algorithm?

[JLBorges]

> Those points will makeup, more or less, a "close area"
> and my purpose is to verify if a given point is contained in that area or not.

Do these points make up a convex polygon?

[kfc123456]

Thank for your reply. Convex polygon is one case but not general. some shape could be really irregular and might not be convex polygon.

[Disch]

I don't understand exactly how your algorithm is supposed to work.

Are the points forming a polygon? If they are, then sorting the vector will completely destroy it. And if they're not forming a polygon, then how they a point be "bound" by them?

Very confused.

[kfc123456]

The points are forming a polygon but they are not in order. One example is there is a elliptic, but the points on the boundary we collected in a random way, that is, they are not in order. Anyway, forget about the polygon stuff. My question is, if I have some points like this

<x0, y0>, <x1, y1>, ... , <xn, yn>

in which x's is sorted by y's might not. Is there any STL algorithm (or boost) to search all points such that
|x-xi|<eps and |y-yi|<eps

where eps is some tolerance. I try two-dimensional loop but it is so slow.

[BlackSheep]

Well it all comes down to implementation. If you only need to verify the points once (A static environment), you could just do it once at the beginning of runtime using something like what you have now.
If not, then I'd suggest using a more advanced type of container. For your purposes a quad tree might serve you well.

[kfc123456]

Thanks. This will be run for many times so I think I need some better way. I will try a tree structure later

[ne555]

IIRC you want to find the nearest neighbour of the test point. And then check if it is close enough.

[kfc123456]

ne555, yes, that's what I am doing now. But the total number of points is too much. I need faster way to do so