[SciPy-User] KD Tree with great circle distances

[Chris Barker]

can't help working if great circle distance matters.

sure, it's a different value than euclidean distance, but for finding
neighbors, the absolute value doesn't matter, only the relative distances
-- and locally, relative distances may be close enough.

just a thought...

-CHB


On Sun, May 20, 2018 at 6:35 PM, ashwin .D <winash12 at gmail.com> wrote:

> Hi Ed,
>            I believe it is indeed very helpful and I may end up using
> either the VP tree or the Ball tree. In order to give you few more details
> I have data on a WGS 84 ellipsoid(we can assume this to be a sphere) from
> 66 N to 66 S and all the longitudes. The data is three dimensional but is
> equidistant along the third dimension i.e. height. The data is also highly
> sparse. From a flattened version of the 3d array I have 22163680 points and
> out of that only 266111 points  have finite values(greater than zero). The
> rest are all  NaNs.But the finite data(those values that are greater than
> zero) is clustered i.e. possibly very close to each other. The resolution
> horizontally is around 5 kms. What I intend to do is to 2D interpolation
> for each height level.
>
> Best regards,
> Ashwin.
> <https://scicomp.stackexchange.com/questions/tagged/python>
>
>
> On Mon, May 21, 2018 at 1:27 AM, Edward Gryspeerdt <edward.grys at gmail.com>
> wrote:
>
>> Hi Ashwin,
>>
>> If you are using the whole globe, you might want to consider using
>> something like a VP-tree instead.  A KD-tree needs left/right to be
>> defined, which you can't do on a sphere.
>>
>> Scikit-learn has a BallTree, which you can use with a 'haversine'
>> distance metric, which should allow you to do do nearest neighbours on a
>> sphere
>>
>> http://scikit-learn.org/stable/modules/generated/sklearn.
>> neighbors.BallTree.html
>>
>> Hope that helps,
>> Ed
>>
>>
>> On 20 May 2018 at 17:49, ashwin .D <winash12 at gmail.com> wrote:
>>
>>> Hi David,
>>>                 Many thanks for your prompt response and that maybe the
>>> route that I may have to take eventually. I was just wondering whether
>>> scipy has any equivalent for the stuff described in this paper -
>>> http://www.soest.hawaii.edu/wessel/sphspline/Wessel+Becker_2008_GJI.pdf
>>> ?
>>>
>>> Regards,
>>> Ashwin.
>>>
>>> On Sun, May 20, 2018 at 9:56 PM, David Hoese <dhoese at gmail.com> wrote:
>>>
>>>> Hi Ashwin,
>>>>
>>>> As far as I know this is the easiest way to do it. I'm not a scipy
>>>> developer, but you may be interested in the pyresample package:
>>>>
>>>> http://pyresample.readthedocs.io/en/latest/
>>>>
>>>> Which uses the pykdtree library:
>>>>
>>>> https://github.com/storpipfugl/pykdtree
>>>>
>>>> And can perform resampling of irregularly spaced data. For certain
>>>> calculations/utilities it will also convert to XYZ space as described in
>>>> that SO answer. Hope this helps a little, sorry if it isn't the answer
>>>> you're looking for.
>>>>
>>>> Dave
>>>>
>>>>
>>>> On 5/20/18 11:09 AM, ashwin .D wrote:
>>>>
>>>>> Hello,
>>>>>             I am using - https://docs.scipy.org/doc/sci
>>>>> py/reference/generated/scipy.spatial.KDTree.html#scipy.spatial.KDTree
>>>>> which  I believe is using Euclidean distances underneath the hood. But I
>>>>> want to be able to use great circle distances. Is this the only way to do
>>>>> this - https://stackoverflow.com/questions/20654918/python-how-to-s
>>>>> peed-up-calculation-of-distances-between-cities or is there some way
>>>>> I can extend that class to use great circle distances(maybe somebody has
>>>>> already done that ? ) I have a irregular shaped grid in a WGS 84
>>>>> ellipsoid(can be assumed to be a sphere) and so I want to use great circle
>>>>> distances or if somebody can convince me not to that would be great as well.
>>>>>
>>>>>
>>>>> Best regards,
>>>>> Ashwin.
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> SciPy-User mailing list
>>>>> SciPy-User at python.org
>>>>> https://mail.python.org/mailman/listinfo/scipy-user
>>>>>
>>>>> _______________________________________________
>>>> SciPy-User mailing list
>>>> SciPy-User at python.org
>>>> https://mail.python.org/mailman/listinfo/scipy-user
>>>>
>>>
>>>
>>> _______________________________________________
>>> SciPy-User mailing list
>>> SciPy-User at python.org
>>> https://mail.python.org/mailman/listinfo/scipy-user
>>>
>>>
>>
>>
>> --
>> Public key available at pgp.mit.edu
>> <http://pgp.mit.edu:11371/pks/lookup?search=gryspeerdt&op=index>,
>> ID:B30279BC
>>
>> _______________________________________________
>> SciPy-User mailing list
>> SciPy-User at python.org
>> https://mail.python.org/mailman/listinfo/scipy-user
>>
>>
>
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at python.org
> https://mail.python.org/mailman/listinfo/scipy-user
>
>


-- 

Christopher Barker, Ph.D.
Oceanographer

Emergency Response Division
NOAA/NOS/OR&R            (206) 526-6959   voice
7600 Sand Point Way NE   (206) 526-6329   fax
Seattle, WA  98115       (206) 526-6317   main reception

Chris.Barker at noaa.gov
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-user/attachments/20180521/f959e208/attachment.html>