CODEWITHSUNDEEP
pythonpython-2.7computational-geometry
Bensciens
Bensciens

Reputation: 292

Finding which points are in a 2D region

I have a very large data set comprised of (x,y) coordinates. I need to know which of these points are in certain regions of the 2D space. These regions are bounded by 4 lines in the 2D domain (some of the sides are slightly curved).

For smaller datasets I have used a cumbersome for loop to test each individual point for membership of each region. This doesn't seem like a good option any more due to the size of data set.

Is there a better way to do this?

For example:

If I have a set of points: (0,1) (1,2) (3,7) (1,4) (7,5)

and a region bounded by the lines:

y=2
y=5
y=5*sqrt(x) +1
x=2

I want to find a way to identify the point (or points) in that region.

Thanks.

The exact code is on another computer but from memory it was something like:

point_list = []
for i in range(num_po):
    a=5*sqrt(points[i,0]) +1
    b=2
    c=2
    d=5

    if (points[i,1]<a) && (points[i,0]<b) && (points[i,1]>c) && (points[i,1]<d):
         point_list.append(points[i])

This isn't the exact code but should give an idea of what I've tried.

Upvotes: 4

Views: 1577

Answers (3)

user1196549
user1196549

Reputation:

Long comment:

You are not telling us the whole story.

If you have this big set of points (say N of them) and one set of these curvilinear quadrilaterals (say M of them) and you need to solve the problem once, you cannot avoid exhaustively testing all points against the acceptance area.

Anyway, you can probably preprocess the M regions in such a way that testing a point against the acceptance area takes less than M operations (closer to Log(M)). But due to the small value of M, big savings are unlikely.

Now if you don't just have one acceptance area but many of them to be applied in turn on the same point set, then more sophisticated solutions are possible (namely range searching), that can trade N comparisons to about Log(N) of them, a quite significant improvement.

It may also be that the point set is not completely random and there is some property of the point set that can be exploited.

You should tell us more and show a sample case.

Upvotes: 0

strubbly
strubbly

Reputation: 3477

If you have a single (or small number) of regions, then it is going to be hard to do much better than to check every point. The check per point can be fast, particularly if you choose the fastest or most discriminating check first (eg in your example, perhaps, x > 2).

If you have many regions, then speed can be gained by using a spatial index (perhaps an R-Tree), which rapidly identifies a small set of candidates that are in the right area. Then each candidate is checked one by one, much as you are checking already. You could choose to index either the points or the regions.

I use the python Rtree package for spatial indexing and find it very effective.

Upvotes: 4

John Coleman
John Coleman

Reputation: 51998

This is called the range searching problem and is a much-studied problem in computational geometry. The topic is rather involved (with your square root making things nonlinear hence more difficult). Here is a nice blog post about using SciPy to do computational geometry in Python.

Upvotes: 2

Related Questions