5

I would like to compare the points from one array to the points from another array and find the closest pair. Till now whatever I have come across is with a single array. I do not want to compare the points from the same array. The brute force algorithm works but it is too slow. Is there an algorithm or implementation for this using divide and conquer method?

EDIT 1 : A point is defined as the pair (latitude, longitude) on the earth's surface.

Lawrence
  • 427
  • 5
  • 15
  • What is the `point` here? (x,y) coordinate of point in 2d space or? – Pham Trung Aug 01 '14 at 10:34
  • @PhamTrung A point is defined as the pair (latitude, longitude) on the earth's surface. – Lawrence Aug 01 '14 at 10:38
  • 1
    Others have already pointed you to good solutions to how to find the nearest neighbour efficiently. It is probably a good idea to transform your longitude/latitude pairs to spatial points, for example the [Earth-centred, Earth-fixed](http://en.wikipedia.org/wiki/ECEF) coordinate system, because the ratio of longitude to distance is not constant over all latitudes. (You can do that transformation once, before your nearest-neighbour search.) – M Oehm Aug 02 '14 at 09:10
  • @MOehm Thank you very much. I shall implement this and let you know how it works out. – Lawrence Aug 04 '14 at 10:08
  • @MOehm I had a question regarding the conversion of latutudes and longitudes to spatial coordinates. Is the conversion necessary if we are dealing with a small area like Paris? – Lawrence Aug 06 '14 at 08:53
  • 1
    If your serach domain is constrained to a relatively small area, the distortion of lat/lng values is negligible and you don't have to use Cartesian coordinates. But Paris is at about 49°N, which means that one unit of longitude covers only about cos(49°) ~ 0.66 times the distance of the same unit of latitude. I would therefore suggest to introduce a constant factor to your distance calculation: `d² = (a*lng)² + lat²`, where `a = 1/cos(lat_m)` and `lat_m` is the mean latitude of your search domain. – M Oehm Aug 06 '14 at 12:04
  • @MOehm Thank you very much. This is of great help. – Lawrence Aug 07 '14 at 08:43

2 Answers2

4

You can build a kd-tree for the first array of points and then find the closest point from the first array for each point of the second array using this tree. It works in O(n log n) on avarage(n is the size of the largest of two arrays). To use kd-tree, you can convert your initial coordinates into 3D-space coordinates.

kraskevich
  • 18,368
  • 4
  • 33
  • 45
  • Thank you for your answer. I shall implement it and get back to you. – Lawrence Aug 04 '14 at 10:10
  • I had a question regarding the conversion of latutudes and longitudes to spatial coordinates. Is the conversion necessary if we are dealing with a small area like Paris? – Lawrence Aug 06 '14 at 08:54
  • @Lawrence It depends on the precision you need, how close the points can be and so on. Maybe you can just try to run it with and without conversion and see if anything breaks. – kraskevich Aug 06 '14 at 09:28
1

you may use kd-tree, octo tree, rtree, rtree*. all this alghorithms O(log n) to search nearest point. There is a implenentation of rtree in boost library

Constantine Kuznetsov
  • 187
  • 2
  • 10
  • 1
    but rtee dont have a function build, only insert(more slow). I write my implementation, but its so raw now. if you want you may write to me via mail and i may send you my implementation. – Constantine Kuznetsov Aug 07 '14 at 10:50
  • I am trying it with kd-tree. It'll be interesting to compare it with your implementation if you are not averse to the idea. If you permit me where do I contact you? – Lawrence Aug 07 '14 at 12:20
  • to build a tree i use inplace count sort. we may contact via email. chapaev28@ya.ru – Constantine Kuznetsov Aug 07 '14 at 12:48
  • @ConstantineKuznetsov: This is not true, it's possible to create a R-tree in a top-down manner, e.g. from a range of Geometries. It's called bulk-loading or pack-creation and in general it's also "divide and conquer" algorithm performing "sorting" locally like in the case of a kd-tree. In particular, Boost.Geometry R-tree implementation supports this method since Boost 1.55. – Adam Wulkiewicz Jan 06 '15 at 18:17