[SciPy-User] KD Tree with great circle distances

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

[SciPy-User] KD Tree with great circle distances

ashwin .D
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
Reply | Threaded
Open this post in threaded view
|

Re: KD Tree with great circle distances

David Hoese
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
Reply | Threaded
Open this post in threaded view
|

Re: KD Tree with great circle distances

ashwin .D
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 <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: KD Tree with great circle distances

Edward Gryspeerdt
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 <[hidden email]> 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 <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: KD Tree with great circle distances

Charles R Harris


On Sun, May 20, 2018 at 1:57 PM, Edward Gryspeerdt <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: KD Tree with great circle distances

ashwin .D
In reply to this post by Edward Gryspeerdt
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.


On Mon, May 21, 2018 at 1:27 AM, Edward Gryspeerdt <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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



_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.python.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: KD Tree with great circle distances

Chris Barker - NOAA Federal
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 <[hidden email]> 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.


On Mon, May 21, 2018 at 1:27 AM, Edward Gryspeerdt <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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



_______________________________________________
SciPy-User mailing list
[hidden email]
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

[hidden email]

_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.python.org/mailman/listinfo/scipy-user