--- Geo-LatLon2Place/LatLon2Place.xs	2022/03/14 22:48:05	1.3
+++ Geo-LatLon2Place/LatLon2Place.xs	2022/03/15 07:33:40	1.4
@@ -2,6 +2,8 @@
 #include "perl.h"
 #include "XSUB.h"
 
+#include <math.h>
+
 #include "perlmulticore.h"
 
 #if EMBED_CDB
@@ -10,33 +12,118 @@
  #include <cdb.h>
 #endif
 
+#define TORAD(r) ((r) * (M_PI / 180.))
+
 static struct cdb_make make;
 
+struct res
+{
+  double mind;
+  unsigned int respos, reslen;
+  double x, y;
+};
+
+static inline int
+intmin (int a, int b)
+{
+  return a > b ? b : a;
+}
+
+static inline int
+intmax (int a, int b)
+{
+  return a > b ? a : b;
+}
+
 MODULE = Geo::LatLon2Place		PACKAGE = Geo::LatLon2Place
 
 PROTOTYPES: ENABLE
 
-int
-cdb_make_start (int fd)
-	CODE:
-        RETVAL = cdb_make_start (&make, fd);
-        OUTPUT: RETVAL
-
-int
-cdb_make_add (SV *k, SV *v)
+SV *
+lookup_ext_ (SV *cdb, int km, int boxes, NV lat, NV lon, int r0, int r1, int flags)
 	CODE:
 {
-	STRLEN klen; const char *kp = SvPVbyte (k, klen);
-        STRLEN vlen; const char *vp = SvPVbyte (v, vlen);
-        RETVAL = cdb_make_add (&make, kp, klen, vp, vlen);
+        struct cdb *db = (struct cdb *)SvPVX (cdb);
+
+        if (!r1)
+          r1 = km;
+
+        r0 =  r0           / km;
+        r1 = (r1 + km - 1) / km;
+        double coslat = cos (TORAD (lat));
+        int cy = (lat + 90.) * boxes * (1. / 180.);
+        int x, y;
+
+        if (r1 < r0 || r0 < 0 || r1 < 0 || r0 >= boxes / 2 || r1 >= boxes / 2)
+          XSRETURN_EMPTY;
+
+        if (lat < -90. || lat > 90. || lon < -180 || lon > 180.)
+          XSRETURN_EMPTY;
+
+        double mind = 1e99;
+        const U8 *resptr;
+        int reslen = 0;
+
+        for (y = intmax (0, cy - r1); y <= intmin (boxes - 1, cy + r1); ++y)
+          {
+            double glat = y * (180. / boxes) - 90.;
+            double coslat = cos (TORAD (glat));
+            int blat = boxes * coslat; /* can be zero */
+            int cx = (lon + 180.) * blat * (1. / 360.);
+
+            for (x = cx - r1; x <= cx + r1; ++x)
+              {
+                int rx = x;
+                rx += rx <     0 ? blat : 0;
+                rx -= rx >= blat ? blat : 0;
+
+                unsigned char key[4] = {
+                  rx, rx >> 8,
+                   y,  y >> 8,
+                };
+
+                printf ("x,y %4d,%4d blat %d %d %g %02x%02x%02x%02x %d\n", rx, y, blat, (int)glat, TORAD(glat), key[0],key[1],key[2],key[3], sizeof(key));
+
+                if (cdb_find (db, key, sizeof (key)) <= 0)
+                  continue;
+
+                int len = cdb_datalen (db);
+                const U8 *ptr = cdb_get (db, len, cdb_datapos (db));
+
+                while (len > 0)
+                  {
+                    int datalen = ptr[5];
+
+                    double plat = ptr[0] | (ptr[1] << 8) * ( 90. / 32767.);
+                    double plon = ptr[2] | (ptr[3] << 8) * (180. / 32767.);
+                    int w  = ptr[4];
+
+                    double dx = TORAD (lon - plon) * coslat;
+                    double dy = TORAD (lat - plat);
+                    double d2 = (dx * dx + dy * dy) * w;
+                    printf ("%g,%g %g %.*s\n", plat,plon,d2, datalen,ptr+6);
+
+                    if (d2 < mind)
+                      {
+                        mind   = d2;
+                        resptr = ptr;
+                        reslen = datalen;
+                      }
+
+                    len -= datalen + 6;
+                    ptr += datalen + 6;
+                  }
+              }
+          }
+
+        if (!reslen)
+          XSRETURN_EMPTY;
+
+        RETVAL = newSVpvn (resptr + 6, reslen);
 }
-        OUTPUT: RETVAL
+	OUTPUT: RETVAL
 
-int
-cdb_make_finish ()
-	CODE:
-        RETVAL = cdb_make_finish (&make);
-        OUTPUT: RETVAL
+#############################################################################
 
 int
 cdb_init (SV *self, int fd)
@@ -70,3 +157,27 @@
 }
         OUTPUT: RETVAL
 
+#############################################################################
+
+int
+cdb_make_start (int fd)
+	CODE:
+        RETVAL = cdb_make_start (&make, fd);
+        OUTPUT: RETVAL
+
+int
+cdb_make_add (SV *k, SV *v)
+	CODE:
+{
+	STRLEN klen; const char *kp = SvPVbyte (k, klen);
+        STRLEN vlen; const char *vp = SvPVbyte (v, vlen);
+        RETVAL = cdb_make_add (&make, kp, klen, vp, vlen);
+}
+        OUTPUT: RETVAL
+
+int
+cdb_make_finish ()
+	CODE:
+        RETVAL = cdb_make_finish (&make);
+        OUTPUT: RETVAL
+