找到在 X 英里半径内捕获最多商店位置的前 X 坐标点

Question

我有 500 家商店及其纬度和经度坐标的列表。我正在尝试找到 30 个独特的坐标点，这些坐标点捕获 15 英里半径内最多数量的“受限”商店，没有任何重叠，并最小化从中心点到商店的平均距离。

我的方法是创建一个经纬度网格，并用 Python 测试每个点，但这似乎是一种缓慢的方法。所有商店都在美国。

这是我的代码：

# Define the 15-mile radius in kilometers
RADIUS_KM = 15 * 1.60934

# Define a grid with a given range of latitudes and longitudes
def generate_grid(lat_range, lon_range, lat_step, lon_step):
    latitudes = np.arange(lat_range[0], lat_range[1], lat_step)
    longitudes = np.arange(lon_range[0], lon_range[1], lon_step)
    return [(lat, lon) for lat, lon in product(latitudes, longitudes)]

def calculate_distance(lat1, lon1, lat2, lon2):
    return geodesic((lat1, lon1), (lat2, lon2)).km

# Create a grid of candidate points (this is for Texas as an example)
lat_range = (25.83, 43)  
lon_range = (-106.6466, -93.5072)  
lat_step = .05
lon_step = .05

grid = generate_grid(lat_range, lon_range, lat_step, lon_step)

# Create a list to store results for each grid point
results = []

for point in grid:
    constrained_distances = []
    for index, row in Texas.iterrows():
        distance = calculate_distance(point[0], point[1], row['Latitude'], row['Longitude'])
        if distance <= RADIUS_KM and row['Constraint Check'] == 'Constrained':
            constrained_distances.append(distance)
    
    constrained_count = len(constrained_distances)
    average_distance = np.mean(constrained_distances) if constrained_distances else float('inf')
    
    results.append({
        'Location': point,
        'Constrained Count': constrained_count,
        'Average Distance': average_distance
    })

Answer 1

我开始为此构建一个分析解决方案。也许这可以帮助您想象这里的问题。

我所做的是创建一个相距 3 英里的点网格。我在网格中生成 500 个随机商店。然后，我创建一个半径为 15 英里（即 5 个网格点）的圆数组。对于每个商店，我都会将该圆圈添加到大主网格中。之后，网格数组的值为“距离我 15 英里内有多少家商店？”。

import random
import numpy as np

# Create a grid of candidate points (this is for Texas as an example)
lat_range = (25.83, 43)  
lon_range = (-106.6466, -93.5072)  
lat_step = .05
lon_step = .05

stepsx = int(abs((lat_range[1]-lat_range[0]) / lat_step))
stepsy = int(abs((lon_range[1]-lon_range[0]) / lon_step))

def x2lat(x):
    return lat_range[0]+x*lat_step

def y2lon(y):
    return lon_range[0]+y*lon_step

def generate_random_stores():
    stores = []
    for i in range(500):
        x = x2lat(random.random() * stepsx)
        y = y2lon(random.random() * stepsy)
        stores.append((x,y))
    return stores

stores = generate_random_stores()

# Define a 15 mile radius circle.

R=5
R2=R+R+1
R4=R2+R2

circle = np.zeros((R2,R2))
for x in range(-R,R+1):
    for y in range(-R,R+1):
        circle[x+R,y+R] = x*x+y*y <= R*R

# Define a complete grid with a border, so we don't have to clip the edges.

grid = np.zeros( (stepsx+R4,stepsx+R4) )

# Add circles around all of the stores.

for lat,lon in stores:
    x = int((lat-lat_range[0]) / lat_step)
    y = int((lon-lon_range[0]) / lon_step)
    grid[x+R2:x+R4,y+R2:y+R4] += circle

largest = int(grid.max())

for n in range(3):
    cur = largest - n
    print("These points have",cur,"stores within 15 miles:")
    for x,y in np.argwhere(grid==cur):
        print("%.2f %.2f" % (x2lat(x-31),y2lon(y-31)))

输出示例：

These points have 5 stores within 15 miles:
40.63 -103.80
These points have 4 stores within 15 miles:
26.68 -104.30
26.68 -103.20
26.68 -103.15
26.73 -104.45
26.73 -104.40
26.73 -104.35
26.73 -104.30
26.73 -104.25
26.73 -104.20
26.78 -104.45
26.78 -104.40
26.78 -104.35
26.78 -104.30
26.78 -104.25
26.83 -104.40
26.93 -104.40
27.73 -103.70
33.28 -102.90
37.28 -97.35
37.33 -97.40
37.33 -97.35
37.38 -97.40
37.38 -97.35
37.43 -97.40
37.43 -97.35
37.48 -97.45
... etc ...