[SciPy-User] KD Tree with great circle distances

[Charles R Harris]

On Sun, May 20, 2018 at 1:57 PM, 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
>>
>>
>
If the points are on the surface of the globe and the deviation of the
ideal surface from a sphere can be neglected, then the mapping from 3-D
distance to great circle distance is 1-1 and well defined. Not sure how
inefficient 3-D indexing of points on the surface would be, but suspect it
isn't too bad. Much depends on the specifics of the problem, and the amount
of data. If nothing else, selected points could be checked for spherical
distance. I've also mapped spheres onto an octahedron and indexed the
sides, but that may not be useful for what you want to do. I suppose you
could also use a tetrahedron, which is self dual and would allow two
similar indexes and avoid edges and vertices if you were only looking for
nearby points.

Chuck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-user/attachments/20180520/81fc0a58/attachment.html>