[SciPy-User] KD Tree with great circle distances

7 messages
Open this post in threaded view
|

[SciPy-User] KD Tree with great circle distances

 Hello,           I am using - https://docs.scipy.org/doc/scipy/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-speed-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 [hidden email] https://mail.python.org/mailman/listinfo/scipy-user
Open this post in threaded view
|

Re: KD Tree with great circle distances

 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/pykdtreeAnd 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/scipy/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-speed-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 > [hidden email] > https://mail.python.org/mailman/listinfo/scipy-user> _______________________________________________ SciPy-User mailing list [hidden email] https://mail.python.org/mailman/listinfo/scipy-user
Open this post in threaded view
|

Re: KD Tree with great circle distances

 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 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/scipy/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-speed-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 [hidden email] https://mail.python.org/mailman/listinfo/scipy-user _______________________________________________ SciPy-User mailing list [hidden email] https://mail.python.org/mailman/listinfo/scipy-user _______________________________________________ SciPy-User mailing list [hidden email] https://mail.python.org/mailman/listinfo/scipy-user
Open this post in threaded view
|

Re: KD Tree with great circle distances

 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 spherehttp://scikit-learn.org/stable/modules/generated/sklearn.neighbors.BallTree.htmlHope that helps,EdOn 20 May 2018 at 17:49, ashwin .D 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 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/scipy/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-speed-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 [hidden email] https://mail.python.org/mailman/listinfo/scipy-user _______________________________________________ SciPy-User mailing list [hidden email] https://mail.python.org/mailman/listinfo/scipy-user _______________________________________________ SciPy-User mailing list [hidden email] https://mail.python.org/mailman/listinfo/scipy-user -- Public key available at pgp.mit.edu, ID:B30279BC _______________________________________________ SciPy-User mailing list [hidden email] https://mail.python.org/mailman/listinfo/scipy-user
Open this post in threaded view
|

Re: KD Tree with great circle distances

 On Sun, May 20, 2018 at 1:57 PM, Edward Gryspeerdt 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 spherehttp://scikit-learn.org/stable/modules/generated/sklearn.neighbors.BallTree.htmlHope that helps,EdOn 20 May 2018 at 17:49, ashwin .D 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 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/scipy/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-speed-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 [hidden email] https://mail.python.org/mailman/listinfo/scipy-user _______________________________________________ SciPy-User mailing list [hidden email] https://mail.python.org/mailman/listinfo/scipy-user _______________________________________________ SciPy-User mailing list [hidden email] 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 _______________________________________________ SciPy-User mailing list [hidden email] https://mail.python.org/mailman/listinfo/scipy-user