Points in rectangles

Range selections on data points

Sometimes you have many data points and you may want to apply multiple range selections to them and see all points that belong to all selections at the end. This bit demonstrates such an example in the context of geo-coordinates of American cities.

cities = { 'San Antonio': (29.424122, -98.493628), 'Phoenix': (33.448377, -112.074037), 'Atlanta': (33.748995, -84.387982), 'Dallas': (32.776664, -96.796988), 'Houston': (29.760427,-95.369803), 'San Francisco': (37.774929, -122.419416), 'Chicago': (41.878114, -87.629798), 'Seattle': (47.606209, -122.332071), 'Fresno': (36.746842, -119.772587), 'New York': (40.712784, -74.005941), 'Indianapolis': (39.768403, -86.158068), 'Los Angeles': (34.052234, -118.243685), 'Philadelphia': (39.952584, -75.165222), 'Austin': (30.267153, -97.743061), 'Charlotte': (35.227087, -80.843127), 'Seattle': (47.606209, -122.332071), 'Denver': (39.739236, -104.990251), 'Boston': (42.360082, -71.058880), 'Washington': (47.751074, -120.740139), 'Milwalkee': (43.038902, -87.906474), 'Albaquerque': (35.085334, -106.605553), 'Sacramento': (38.581572, -121.494400), 'Miami': (25.761680, -80.191790), 'Detroit': (42.331427, -83.045754), 'Memphis': (35.149534, -90.048980), 'Portland': (45.523062, -122.676482), 'Oakland': (37.804364, -122.271114), 'Minneapolis': (44.977753, -93.265011), 'Celeveland': (41.499320, -81.694361), 'Tampa': (27.950575, -82.457178), 'St. Louis': (38.627003, -90.199404) } rectangle_coords = [ ((34.12, -81.15), (45.41, -93.74)), ((38.27, -76.55), (47.91, -88.78)), ((41.41, -85.55), (44.05, -100.78)) ] class Point: def __init__(self, x, y): self.x = x self.y = y class Rectangle: def __init__(self, p1, p2): self.x1, self.y1 = p1 self.x2, self.y2 = p2 def contains_point(self, point): # The places of y1 and y2 are switched due to the minus sign return self.x1 <= point.x <= self.x2 and self.y2 <= point.y <= self.y1 def intersect_rectangles(self, rectangles): """ Finds the bounding box for all rectangle intersections """ x1s, x2s, y1s, y2s = [self.x1], [self.x2], [self.y1], [self.y2] for rect in rectangles: x1s.append(rect.x1) x2s.append(rect.x2) y1s.append(rect.y1) y2s.append(rect.y2) return Rectangle((max(x1s), min(y1s)), (min(x2s), max(y2s))) cities_items = cities.items() points = [Point(lat_lon[0], lat_lon[1]) for city_name, lat_lon in cities_items] rectangles = [Rectangle(p1, p2) for p1, p2 in rectangle_coords] # Goal: find all points that belong to all rectangles # Case 1: Find all points in each rectangle separately, intersect the results. Has potentially high peak memory usage. points_found = [set([]) for _ in range(len(rectangles))] for i, rectangle in enumerate(rectangles): for point in points: if rectangle.contains_point(point): points_found[i].add((point.x, point.y)) points_in_all_rects = points_found[0] & points_found[1] & points_found[2] cities_in_all_rects = [city for city, coord in cities_items if coord in points_in_all_rects] print(cities_in_all_rects) # ['Milwalkee', 'Chicago'] # Case 2: Find the intersection of all rectangles first. Then find all points in that rectangle only. Avoid intersections with many objects. rect1, rect2, rect3 = rectangles rectangle_intersection = rect1.intersect_rectangles([rect2, rect3]) points_in_all_rects = [(point.x, point.y) for point in points if rectangle_intersection.contains_point(point)] cities_in_all_rects = [city for city, coord in cities_items if coord in points_in_all_rects] print(cities_in_all_rects) # ['Milwalkee', 'Chicago']