Mercurial > hg > GlobalNeighbors

annotate globalneighbors/distance.py @ 16:4583d0d9331a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
stub command line entry for gridding neighbors
author Jeff Hammel <k0scist@gmail.com>
date Sun, 25 Jun 2017 15:03:54 -0700
parents 27925261c137
children 811adc9736eb
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
1 """
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
2 distance functionality
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
3 """
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
4
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
5 import argparse
8
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
6 import bisect
0
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
7 import json
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
8 import sys
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
9 import time
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
10 from math import asin, sin, cos, sqrt, pi, fabs
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
11 from .cli import CitiesParser
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
12 from .constants import Rearth
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
13 from .locations import locations
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
14 from .read import read_cities
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
15 from .schema import fields
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
16
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
17 DEGREESTORADIANS = pi/180.
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
18
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
19
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
20 def haversine(lat1, lon1, lat2, lon2, r=1):
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
21 """
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
22 see
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
23 https://en.wikipedia.org/wiki/Haversine_formula
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
24 Coordinates in radians
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
25 """
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
26 return 2*r*asin(
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
27 sqrt(sin(0.5*(lat2-lat1))**2
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
28 +cos(lat1)*cos(lat2)*(sin(0.5*(lon2-lon1))**2)
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
29 ))
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
30
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
31
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
32 def deg_to_rad(degrees):
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
33 return degrees*DEGREESTORADIANS
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
34
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
35
5
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
36 def insert_distance(distances, i, new_distance, k):
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
37 """
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
38 insert `(i, new_distance)` into `distances`
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
39 keeping distances in order with maximum of size `k`
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
40 """
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
41
7
254195d0bac2 partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want
Jeff Hammel <k0scist@gmail.com>
parents: 6
diff changeset
42 if len(distances) == k and new_distance >= distances[-1][-1]:
254195d0bac2 partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want
Jeff Hammel <k0scist@gmail.com>
parents: 6
diff changeset
43 return
254195d0bac2 partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want
Jeff Hammel <k0scist@gmail.com>
parents: 6
diff changeset
44
5
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
45 # TODO: Binary Search Tree
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
46 for _index, (geoid, old_distance) in enumerate(distances):
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
47 if new_distance < old_distance:
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
48 distances.insert(_index, (i, new_distance))
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
49 if len(distances) == k+1:
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
50 distances.pop()
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
51 break
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
52 else:
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
53 distances.append((i, new_distance))
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
54
9
638fad06e556 use bisect function; it has been tested faster
Jeff Hammel <k0scist@gmail.com>
parents: 8
diff changeset
55
638fad06e556 use bisect function; it has been tested faster
Jeff Hammel <k0scist@gmail.com>
parents: 8
diff changeset
56 class KeyWrapper(object):
638fad06e556 use bisect function; it has been tested faster
Jeff Hammel <k0scist@gmail.com>
parents: 8
diff changeset
57 """wrapper for python's `bisect` methods"""
8
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
58 def __init__(self, iterable, key):
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
59 self.it = iterable
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
60 self.key = key
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
61
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
62 def __getitem__(self, i):
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
63 return self.key(self.it[i])
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
64
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
65 def __len__(self):
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
66 return len(self.it)
7
254195d0bac2 partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want
Jeff Hammel <k0scist@gmail.com>
parents: 6
diff changeset
67
9
638fad06e556 use bisect function; it has been tested faster
Jeff Hammel <k0scist@gmail.com>
parents: 8
diff changeset
68
7
254195d0bac2 partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want
Jeff Hammel <k0scist@gmail.com>
parents: 6
diff changeset
69 def insert_distance_bisect(distances, i, new_distance, k):
8
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
70
7
254195d0bac2 partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want
Jeff Hammel <k0scist@gmail.com>
parents: 6
diff changeset
71 if not distances:
254195d0bac2 partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want
Jeff Hammel <k0scist@gmail.com>
parents: 6
diff changeset
72 distances.append((i, new_distance))
254195d0bac2 partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want
Jeff Hammel <k0scist@gmail.com>
parents: 6
diff changeset
73 return
254195d0bac2 partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want
Jeff Hammel <k0scist@gmail.com>
parents: 6
diff changeset
74 if new_distance >= distances[-1][-1]:
254195d0bac2 partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want
Jeff Hammel <k0scist@gmail.com>
parents: 6
diff changeset
75 if len(distances) < k:
254195d0bac2 partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want
Jeff Hammel <k0scist@gmail.com>
parents: 6
diff changeset
76 distances.append((i, new_distance))
254195d0bac2 partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want
Jeff Hammel <k0scist@gmail.com>
parents: 6
diff changeset
77 return
6
316e1d54ffd4 move to jinja templates
Jeff Hammel <k0scist@gmail.com>
parents: 5
diff changeset
78
8
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
79 point = bisect.bisect_left(KeyWrapper(distances,
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
80 key=lambda x: x[-1]),
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
81 new_distance)
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
82 distances.insert(point, (i, new_distance))
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
83 if len(distances) == k+1:
e3d6919130ca insert via BST
Jeff Hammel <k0scist@gmail.com>
parents: 7
diff changeset
84 distances.pop()
5
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
85
0
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
86 def calculate_distances(locations, r=Rearth):
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
87 """
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
88 WARNING! This is an N-squared approach
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
89 """
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
90
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
91 # convert to rad
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
92 rad_locations = [(location, tuple([deg_to_rad(i)
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
93 for i in latlon]))
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
94 for location, latlon
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
95 in locations.items()]
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
96
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
97 # use haversince function on N-body problem
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
98 for index, loc1 in enumerate(rad_locations):
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
99 id1, (lat1, lon1) = loc1
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
100 for loc2 in rad_locations[index+1:]:
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
101 id2, (lat2, lon2) = loc2
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
102 key = (id1, id2) if id2 > id1 else (id2, id1)
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
103 yield (key,
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
104 haversine(lat1, lon1, lat2, lon2, r=r))
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
105
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
106
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
107 def calculate_neighbors(locations,
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
108 k=10,
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
109 lat_tol=1.,
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
110 lon_tol=1.,
3
49aae0c0293b improved test coverage
Jeff Hammel <k0scist@gmail.com>
parents: 1
diff changeset
111 output=None,
0
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
112 neighbors=None):
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
113 """
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
114 calculate `k` nearest neighbors for each location
3
49aae0c0293b improved test coverage
Jeff Hammel <k0scist@gmail.com>
parents: 1
diff changeset
115
49aae0c0293b improved test coverage
Jeff Hammel <k0scist@gmail.com>
parents: 1
diff changeset
116 locations -- dict of `geoid: (lat, lon)`
0
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
117 """
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
118 neighbors = neighbors or {}
3
49aae0c0293b improved test coverage
Jeff Hammel <k0scist@gmail.com>
parents: 1
diff changeset
119 items = locations.items() # copy
0
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
120 index = 0
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
121 n_items = len(items)
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
122 start = int(time.time())
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
123 while items:
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
124 index += 1
3
49aae0c0293b improved test coverage
Jeff Hammel <k0scist@gmail.com>
parents: 1
diff changeset
125 if output and not index % output:
0
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
126 # output status counter
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
127 now = int(time.time())
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
128 duration = now - start
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
129 start = now
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
130 print ('{},{},{},{}'.format(index,
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
131 len(items),
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
132 n_items,
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
133 duration))
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
134 id1, (lat1, lon1) = items.pop()
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
135 for loc2 in items:
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
136 id2, (lat2, lon2) = loc2
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
137
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
138 # filter out locations based on latlon boxing
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
139 if fabs(lat2 - lat1) > lat_tol:
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
140 continue
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
141 if fabs(lon2 - lon1) > lon_tol:
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
142 continue
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
143
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
144 # determine distance
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
145 args = [deg_to_rad(i) for i in
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
146 (lat1, lon1, lat2, lon2)]
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
147 new_distance = haversine(*args, r=Rearth)
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
148
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
149 # insert in order
14
27925261c137 fix broken tests including an aggregious case where we add ourselves as a neighbor to ourself
Jeff Hammel <k0scist@gmail.com>
parents: 9
diff changeset
150 ids = (id1, id2)
27925261c137 fix broken tests including an aggregious case where we add ourselves as a neighbor to ourself
Jeff Hammel <k0scist@gmail.com>
parents: 9
diff changeset
151 for i in (0, 1):
27925261c137 fix broken tests including an aggregious case where we add ourselves as a neighbor to ourself
Jeff Hammel <k0scist@gmail.com>
parents: 9
diff changeset
152 distances = neighbors.setdefault(ids[i], [])
27925261c137 fix broken tests including an aggregious case where we add ourselves as a neighbor to ourself
Jeff Hammel <k0scist@gmail.com>
parents: 9
diff changeset
153 insert_distance_bisect(distances,
27925261c137 fix broken tests including an aggregious case where we add ourselves as a neighbor to ourself
Jeff Hammel <k0scist@gmail.com>
parents: 9
diff changeset
154 ids[i-1],
27925261c137 fix broken tests including an aggregious case where we add ourselves as a neighbor to ourself
Jeff Hammel <k0scist@gmail.com>
parents: 9
diff changeset
155 new_distance,
27925261c137 fix broken tests including an aggregious case where we add ourselves as a neighbor to ourself
Jeff Hammel <k0scist@gmail.com>
parents: 9
diff changeset
156 k)
0
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
157
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
158 return neighbors
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
159
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
160
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
161 def main(args=sys.argv[1:]):
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
162 """CLI"""
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
163
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
164 # parse command line arguments
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
165 description = """write nearest neighborfiles"""
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
166 parser = CitiesParser(description=description)
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
167 parser.add_argument('output', type=argparse.FileType('w'),
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
168 help="output file to dump JSON to")
9
638fad06e556 use bisect function; it has been tested faster
Jeff Hammel <k0scist@gmail.com>
parents: 8
diff changeset
169 parser.add_argument('--latlon', dest='latlon', type=float,
638fad06e556 use bisect function; it has been tested faster
Jeff Hammel <k0scist@gmail.com>
parents: 8
diff changeset
170 nargs=2, metavar=("LAT", "LON"),
638fad06e556 use bisect function; it has been tested faster
Jeff Hammel <k0scist@gmail.com>
parents: 8
diff changeset
171 default=(1., 1.),
638fad06e556 use bisect function; it has been tested faster
Jeff Hammel <k0scist@gmail.com>
parents: 8
diff changeset
172 help="tolerance of latitude and longitude in degrees [DEFAULT: %(default)s]")
0
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
173 parser.add_argument('--counter', '--output-counter',
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
174 dest='output_counter',
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
175 type=int, default=100,
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
176 help="how often to output progress updates [DEFAULT: %(default)s]")
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
177 parser.add_argument('-k', dest='k',
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
178 type=int, default=50,
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
179 help="number of neighbors to determine [DEFAULT: %(default)s]")
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
180 options = parser.parse_args(args)
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
181
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
182 # parse cities
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
183 cities = list(read_cities(options.cities, fields=fields))
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
184
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
185 # get locations
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
186 city_locations = locations(cities)
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
187
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
188 # calculate neighbors
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
189 neighbors = calculate_neighbors(city_locations,
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
190 k=options.k,
9
638fad06e556 use bisect function; it has been tested faster
Jeff Hammel <k0scist@gmail.com>
parents: 8
diff changeset
191 lat_tol=options.latlon[0],
638fad06e556 use bisect function; it has been tested faster
Jeff Hammel <k0scist@gmail.com>
parents: 8
diff changeset
192 lon_tol=options.latlon[-1],
0
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
193 output=options.output_counter)
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
194
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
195 # output
5
7e27e874655b test a larger grid + move distance insertion to its own function
Jeff Hammel <k0scist@gmail.com>
parents: 3
diff changeset
196 options.output.write(json.dumps(neighbors))
0
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
197
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
198 if __name__ == '__main__':
5dba84370182 initial commit; half-working prototype
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
199 main()