| Re: data inside a circle [message #44435 is a reply to message #44355] |
Mon, 13 June 2005 15:16   |
Rick Towler
Messages: 821
Registered: August 1998
|
Senior Member |
|
|
Rick Towler wrote:
> In addition of Rob's suggestion, you could cull much of your data set on
> each pass before checking if it is within your circle. Determine the
> X/Y bounds of your circle and then extract that subset of data and
> operate on that.
On my ride home I realized that your data is probably not regularly
gridded but is an unordered list which would make this approach much
less effective. You could squeeze a bit more performance by doing a
gross check on the data with a before actually calculating if the point
falls in the circle. I use a separating axis check which given the
bounding box and your point progressively tests if the point falls on
the "right" side of the four sides of your bounding box. You can google
for separating axis test or I can provide an example. But in the end
you're still looping thru every element which is going to be slow.
A better option would be to first process the data to order it in some
way then cull the data. This way you'll be able to extract the indices
to the data which fall within your bounding box which you can use to
extract your sub-array.
A simple approach would be to use sorting. First sort your entire array
by X (only have to do this once). Then use the separating axis test (or
you can use two calls to where and AND the results) to extract all
values of X and their associated Y's w/in the bounding box. Then sort
that subset by Y and extract a subset of the subset of data which
intersects the bounding box in Y.
You could also apply HISTOGRAM to both your X and Y values independently
and then use the reverse indices to get at the subset of your data that
fall within the bins that are intersect your bounding box. You would
have to do the same 2 step approach as the sorting method. Check out
JD's histogram tutorial on David Fanning's website (www.dfanning.com) to
help bring you up to speed on the HISTOGRAM function.
Lastly, you can do it in C. I have done a lot of this in 3d "the hard
way" by looping thru my vertices, performing the separating axis test,
and then calculating whatever I am calculating. Probably the fastest
solution of the all but there's a bit of a learning curve. If this is
something you will be doing *a lot* of then it might be the best way. I
could probably provide some code to get you started.
-Rick
> angela wrote:
>
>> Hello,
>> I have a list of x,y coordinates and I am trying to make circles of
>> different centers and radii and find how many of the data points are
>> inside in the different circles. Do you happen to know an elegant way
>> to do that?
>> I have tried to do that using FOR loops but my data points are about
>> 10,000 and the number of circles are about 160,000, so it takes about
>> 2-3 hours for my program to run. I was wondering if you know of a
>> faster way to do that.
>>
>> Thank you,
>> Angela
>>
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
