comp.lang.idl-pvwave archive: archive » Re: Find all points within a set of polygons

Home » Public Forums » archive » Re: Find all points within a set of polygons

Show: Today's Messages :: Show Polls :: Message Navigator
E-mail to friend

Re: Find all points within a set of polygons [message #46654 is a reply to message #46631]

Thu, 08 December 2005 07:53

Maarten[1]
Messages: 176
Registered: November 2005

Senior Member

Hi,

JD Smith wrote:

> Here's a good reference:
>
> http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly/

Thanks, that helped, but David's pointer to IDL's own IDLanROI object
is
what I use now.

> I believe Mark Hadfield has coded up one or more of these in his
> Motley library, which at least vectorizes over the points to test.
> Since all your polygons are the same length (4), it is possible to
> simultaneously vectorize over both points and polygons (this would not
> be true for arbitrary-sized polygons).

[snip]

> However, similar to the "points inside a sphere" problem I just
> commented on, you'll run out of memory fast using such a brute force
> method.

I decided to apply some prior knowledge to the problem and limit the
number of points I have to search, reducing the memory requirements
significantly. The trick? The points are geolocation points from MODIS,

and are neatly arranged. What is more important: I have a set of 1x1 km

gelocations and another set of 5x5 km geolocations. Now I search the
coarse array first, take those indices and make a generous estimate of
the
indices I can expect in the fine array. I then create a subset from the
fine
arrays and search those instead, searching on the order of 800 points
(selecting up to 500), instead of searching 2.7 million. In the end the

speedup is a factor of ~ 22, and that is without vectorizing the code.

> For a smallish number of points and polygons, this brute force method
> will definitely be the fastest, thanks to the overhead of loops.
> However, for larger sized problems, just like for the spherical search
> case, you would do well to pre-reject points which definitely cannot
> be inside a given polygon.

I could probably speed things up by further pre-selection, but for now
I
think I have enough other things to do in each loop to get away with
what
I have now.

Thanks,

Maarten

Report message to a moderator

[Message index]

		Re: Find all points within a set of polygons By: JD Smith on Wed, 30 November 2005 12:45
		Re: Find all points within a set of polygons By: Maarten[1] on Wed, 30 November 2005 08:03
		Re: Find all points within a set of polygons By: David Fanning on Wed, 30 November 2005 07:51
		Re: Find all points within a set of polygons By: Maarten[1] on Wed, 30 November 2005 07:43
		Re: Find all points within a set of polygons By: David Fanning on Wed, 30 November 2005 07:23
		Re: Find all points within a set of polygons By: Maarten[1] on Thu, 08 December 2005 07:53

Previous Topic:	Re: idl license server an mac powerbook
Next Topic:	Re: Parameters and MPFIT

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

] [

]

Current Time: Tue Dec 02 08:14:35 PST 2025

Total time taken to generate the page: 1.04378 seconds