多边形任意两个顶点之间的最大距离
Maximum distance between any two vertices of a polygon
我有一个多边形顶点的经度和纬度列表。这些坐标在投影坐标系中，以米为单位。任意两个顶点之间的距离可以计算为简单的欧氏距离。
我想计算任意两个顶点之间的最大距离，可以称为多边形的直径。
lis_lat_long = [['1835512.146', '-3239236.854'],
['1835395.956', '-3239257.039'],
['1835139.106', '-3239366.877'],
['1834981.710', '-3239356.042'],
['1834938.231', '-3239375.154'],
['1834770.578', '-3239540.771'],
['1834734.402', '-3239557.223'],
['1834438.641', '-3239555.921'],
['1834223.286', '-3239586.463'],
['1834085.627', '-3239559.935'],
['1833968.551', '-3239557.085'],
['1833765.725', '-3239632.053'],
['1833728.380', '-3239656.957'],
['1833728.426', '-3239639.481'],
['1833686.217', '-3239533.590'],
['1833691.401', '-3239521.642'],
['1833644.753', '-3239460.690'],
['1833605.786', '-3239455.803'],
['1833483.844', '-3239468.720'],
['1833449.012', '-3239480.277'],
['1833344.883', '-3239595.946'],
['1833295.328', '-3239623.781'],
['1833166.992', '-3239652.882'],
['1833128.570', '-3239672.435'],
['1832983.109', '-3239786.355'],
['1832939.996', '-3239798.097'],
['1832888.462', '-3239795.852'],
['1832701.447', '-3239745.817'],
['1832592.984', '-3239704.983'],
['1832481.850', '-3239610.119'],
['1832419.197', '-3239530.270'],
['1832372.714', '-3239511.904'],
['1832218.735', '-3239291.581'],
['1832063.013', '-3239183.406'],
['1831951.167', '-3239132.681'],
['1831863.114', '-3239111.652'],
['1831744.389', '-3239107.381'],
['1831701.505', '-3239096.349'],
['1831637.554', '-3239046.953'],
['1831553.772', '-3239016.069'],
['1831441.089', '-3238992.231'],
['1831358.195', '-3238955.454'],
['1831104.618', '-3238809.221'],
['1831064.761', '-3238778.801'],
['1831040.021', '-3238695.083'],
['1831009.800', '-3238640.200'],
['1830984.046', '-3238618.579'],
['1830813.824', '-3238552.980'],
['1830737.693', '-3238506.874'],
['1830684.415', '-3238469.741'],
['1830576.412', '-3238346.902'],
['1830524.522', '-3238321.013'],
['1830452.078', '-3238336.643'],
['1830368.231', '-3238395.289'],
['1830282.442', '-3238503.561'],
['1830244.647', '-3238505.171'],
['1830224.131', '-3238475.403'],
['1830224.533', '-3238407.833'],
['1830214.603', '-3238369.477'],
['1830175.525', '-3238325.177'],
['1830158.692', '-3238324.743'],
['1830061.388', '-3238361.880'],
['1830011.852', '-3238328.626'],
['1829964.991', '-3238251.386'],
['1829920.391', '-3238136.856'],
['1829936.304', '-3238067.307'],
['1829970.006', '-3238014.828'],
['1829969.739', '-3237985.122'],
['1829934.065', '-3237892.636'],
['1829928.018', '-3237808.819'],
['1829911.678', '-3237759.867'],
['1829890.037', '-3237746.091'],
['1829826.524', '-3237732.756'],
['1829739.089', '-3237746.368'],
['1829633.080', '-3237680.587'],
['1829558.529', '-3237686.734'],
['1829516.868', '-3237668.724'],
['1829464.967', '-3237659.687'],
['1829364.924', '-3237615.948'],
['1829312.409', '-3237605.049'],
['1829280.061', '-3237569.848'],
['1829273.684', '-3237522.288'],
['1829290.245', '-3237468.112'],
['1829353.217', '-3237397.127'],
['1829329.545', '-3237247.234'],
['1829308.104', '-3237209.801'],
['1829289.443', '-3237204.445'],
['1829235.164', '-3237217.078'],
['1829100.663', '-3237152.101'],
['1829067.738', '-3237177.139'],
['1829062.856', '-3237221.343'],
['1829046.186', '-3237248.053'],
['1829019.402', '-3237251.989'],
['1828985.913', '-3237232.224'],
['1828968.381', '-3237233.790'],
['1828922.173', '-3237282.727'],
['1828901.318', '-3237289.327'],
['1828844.121', '-3237182.202'],
['1828822.191', '-3237165.064'],
['1828733.547', '-3237121.718'],
['1828685.036', '-3237115.742'],
['1828632.013', '-3237071.453'],
['1828566.550', '-3237048.093'],
['1828545.802', '-3237045.412'],
['1828508.815', '-3237063.973'],
['1828481.129', '-3237059.472'],
['1828464.959', '-3237113.708'],
['1828440.386', '-3237137.125'],
['1828397.567', '-3237154.366'],
['1828388.351', '-3237190.611'],
['1828390.286', '-3237228.979'],
['1828381.847', '-3237237.118'],
['1828339.253', '-3237216.758'],
['1828323.458', '-3237231.757'],
['1828317.185', '-3237245.201'],
['1828320.478', '-3237296.834'],
['1828268.860', '-3237299.688'],
['1828212.770', '-3237324.341'],
['1828185.908', '-3237320.297'],
['1828170.340', '-3237331.124'],
['1828155.782', '-3237329.375'],
['1828139.314', '-3237312.064'],
['1828110.533', '-3237306.958'],
['1828031.357', '-3237316.290'],
['1828016.624', '-3237330.122'],
['1828014.854', '-3237386.527'],
['1828002.702', '-3237400.303'],
['1827956.965', '-3237429.061'],
['1827851.667', '-3237460.252'],
['1827827.078', '-3237531.042'],
['1827839.289', '-3237647.549'],
['1827833.156', '-3237683.042'],
['1827790.529', '-3237741.707'],
['1827786.734', '-3237766.926'],
['1827749.508', '-3237804.159'],
['1827733.895', '-3237854.717'],
['1827647.598', '-3237922.528'],
['1827587.042', '-3237923.707'],
['1827564.401', '-3237947.419'],
['1827519.506', '-3237939.776'],
['1827487.033', '-3237944.741'],
['1827458.030', '-3237980.555'],
['1827458.774', '-3238006.455'],
['1827425.864', '-3238085.291'],
['1827418.256', '-3238127.313'],
['1827370.535', '-3238181.120'],
['1827362.571', '-3238234.045'],
['1827464.503', '-3238387.963'],
['1827462.060', '-3238463.967'],
['1827450.127', '-3238500.580'],
['1827455.408', '-3238570.553'],
['1827471.556', '-3238612.939'],
['1827385.809', '-3238740.163'],
['1827154.723', '-3238948.119'],
['1827140.742', '-3238937.272'],
['1827041.048', '-3238774.397'],
['1826971.637', '-3238687.358'],
['1826948.507', '-3238705.794'],
['1826873.362', '-3238687.737'],
['1826807.692', '-3238547.581'],
['1826768.755', '-3238420.857'],
['1826720.026', '-3238351.323'],
['1826554.765', '-3238062.593'],
['1826533.565', '-3237991.997'],
['1826533.341', '-3237919.246'],
['1826549.338', '-3237849.706'],
['1826670.287', '-3237642.105'],
['1826683.334', '-3237592.821'],
['1826663.727', '-3237543.163'],
['1826518.674', '-3237382.105'],
['1826494.123', '-3237342.331'],
['1826459.375', '-3237177.832'],
['1826495.472', '-3237098.144'],
['1826638.764', '-3236976.583'],
['1826668.729', '-3236924.532'],
['1826682.421', '-3236875.566'],
['1826713.483', '-3236841.167'],
['1826745.591', '-3236781.467'],
['1826803.185', '-3236606.174'],
['1826803.564', '-3236539.269'],
['1826773.001', '-3236448.782'],
['1826783.082', '-3236377.800'],
['1826854.642', '-3236308.761'],
['1826890.009', '-3236214.909'],
['1826936.445', '-3236180.167'],
['1827024.431', '-3236158.317'],
['1827181.609', '-3236075.927'],
['1827240.471', '-3236011.178'],
['1827262.000', '-3235956.751'],
['1827307.430', '-3235920.862'],
['1827437.089', '-3235874.290'],
['1827477.981', '-3235883.653'],
['1827541.025', '-3235932.987'],
['1827590.248', '-3235930.321'],
['1827711.630', '-3235875.094'],
['1827820.787', '-3235850.455'],
['1827849.646', '-3235818.936'],
['1827854.711', '-3235786.603'],
['1827836.023', '-3235736.750'],
['1827787.182', '-3235661.330'],
['1827771.854', '-3235604.897'],
['1827782.069', '-3235536.372'],
['1827817.103', '-3235482.207'],
['1827868.764', '-3235457.440'],
['1827910.952', '-3235413.539'],
['1827925.603', '-3235431.132'],
['1828032.472', '-3235482.082'],
['1828137.470', '-3235550.901'],
['1828309.129', '-3235699.485'],
['1828437.541', '-3235740.624'],
['1828488.964', '-3235867.237'],
['1828626.377', '-3235914.275'],
['1828676.868', '-3235913.796'],
['1828795.362', '-3236009.669'],
['1828827.106', '-3236056.179'],
['1828877.598', '-3236062.785'],
['1828938.744', '-3236124.571'],
['1829038.557', '-3236158.748'],
['1829168.368', '-3236164.570'],
['1829317.950', '-3236079.513'],
['1829492.278', '-3236025.856'],
['1829553.371', '-3235979.519'],
['1829569.386', '-3235781.598'],
['1829763.275', '-3235681.137'],
['1829985.907', '-3234978.341'],
['1830084.642', '-3234991.598'],
['1830103.115', '-3235032.348'],
['1830147.224', '-3235039.088'],
['1830199.403', '-3234995.161'],
['1830189.149', '-3234940.523'],
['1830191.556', '-3234859.155'],
['1830287.759', '-3234824.355'],
['1830337.464', '-3234915.375'],
['1830611.541', '-3234991.131'],
['1833425.390', '-3238626.813'],
['1833361.604', '-3238824.512'],
['1833606.583', '-3238583.326'],
['1833976.391', '-3238589.144'],
['1834240.904', '-3238477.109'],
['1834349.419', '-3238460.625'],
['1834560.042', '-3238491.230'],
['1834616.158', '-3238528.161'],
['1834734.615', '-3238647.457'],
['1834951.986', '-3238938.772'],
['1835039.258', '-3239002.100'],
['1835113.411', '-3239029.358'],
['1835225.012', '-3239037.149'],
['1835337.586', '-3239076.191'],
['1835438.778', '-3239179.715'],
['1835512.146', '-3239236.854']]
对于这一数量的数据点 (~ 200)，我们可以构建简单的 for-loop 覆盖所有顶点对并计算每对顶点的距离。如果此距离高于当前最大值，则成为当前最大值。
此外，您的距离存储为字符串，需要转换为浮点数。
欧氏距离的转换和计算我都用了numpy
在@aerobiomat 的评论建议使用 itertools.combinations 而不是 itertools.product
后进行编辑
import numpy as np
from itertools import combinations
lis_lat_long = np.array(lis_lat_long, float)
current_max = 0
for a, b in combinations(np.array(lis_lat_long), 2):
current_distance = np.linalg.norm(a-b)
if current_distance > current_max:
current_max = current_distance
这应该有效：
from itertools import combinations
import math
def calc_dist(p1, p2):
x1 = p1[0] - p2[0]
y1 = p1[1] - p2[1]
return math.sqrt(pow(x1, 2) + pow(y1, 2))
def diameter(data):
data = [list(map(float, c)) for c in data]
combs = list(combinations(data, 2))
print(max([calc_dist(*points) for points in combs]))
Returns 9283.977292891426 为您的数据
有很多关于使用 numpy 及其 einsum 函数确定距离的帖子。
首先，您的字符串数据需要转换为浮点数，然后是一点 einsum 魔法。
a = np.array(lis_lat_long).astype('float')
a0 = a[:, None]
diff = a - a0
dist_arr = np.sqrt(np.einsum('ijk,ijk->ij', diff, diff))
np.max(dist_arr)
Out[42]: 9283.977292891426
时间安排
每个循环 1.52 毫秒 ± 18.5 µs（7 次运行的平均值 ± 标准偏差，每次 1000 次循环）
接受时间
每个循环 213 毫秒 ± 14.9 毫秒（7 次运行的平均值 ± 标准偏差，每次 1 个循环）
我有一个多边形顶点的经度和纬度列表。这些坐标在投影坐标系中，以米为单位。任意两个顶点之间的距离可以计算为简单的欧氏距离。 我想计算任意两个顶点之间的最大距离，可以称为多边形的直径。
lis_lat_long = [['1835512.146', '-3239236.854'],
['1835395.956', '-3239257.039'],
['1835139.106', '-3239366.877'],
['1834981.710', '-3239356.042'],
['1834938.231', '-3239375.154'],
['1834770.578', '-3239540.771'],
['1834734.402', '-3239557.223'],
['1834438.641', '-3239555.921'],
['1834223.286', '-3239586.463'],
['1834085.627', '-3239559.935'],
['1833968.551', '-3239557.085'],
['1833765.725', '-3239632.053'],
['1833728.380', '-3239656.957'],
['1833728.426', '-3239639.481'],
['1833686.217', '-3239533.590'],
['1833691.401', '-3239521.642'],
['1833644.753', '-3239460.690'],
['1833605.786', '-3239455.803'],
['1833483.844', '-3239468.720'],
['1833449.012', '-3239480.277'],
['1833344.883', '-3239595.946'],
['1833295.328', '-3239623.781'],
['1833166.992', '-3239652.882'],
['1833128.570', '-3239672.435'],
['1832983.109', '-3239786.355'],
['1832939.996', '-3239798.097'],
['1832888.462', '-3239795.852'],
['1832701.447', '-3239745.817'],
['1832592.984', '-3239704.983'],
['1832481.850', '-3239610.119'],
['1832419.197', '-3239530.270'],
['1832372.714', '-3239511.904'],
['1832218.735', '-3239291.581'],
['1832063.013', '-3239183.406'],
['1831951.167', '-3239132.681'],
['1831863.114', '-3239111.652'],
['1831744.389', '-3239107.381'],
['1831701.505', '-3239096.349'],
['1831637.554', '-3239046.953'],
['1831553.772', '-3239016.069'],
['1831441.089', '-3238992.231'],
['1831358.195', '-3238955.454'],
['1831104.618', '-3238809.221'],
['1831064.761', '-3238778.801'],
['1831040.021', '-3238695.083'],
['1831009.800', '-3238640.200'],
['1830984.046', '-3238618.579'],
['1830813.824', '-3238552.980'],
['1830737.693', '-3238506.874'],
['1830684.415', '-3238469.741'],
['1830576.412', '-3238346.902'],
['1830524.522', '-3238321.013'],
['1830452.078', '-3238336.643'],
['1830368.231', '-3238395.289'],
['1830282.442', '-3238503.561'],
['1830244.647', '-3238505.171'],
['1830224.131', '-3238475.403'],
['1830224.533', '-3238407.833'],
['1830214.603', '-3238369.477'],
['1830175.525', '-3238325.177'],
['1830158.692', '-3238324.743'],
['1830061.388', '-3238361.880'],
['1830011.852', '-3238328.626'],
['1829964.991', '-3238251.386'],
['1829920.391', '-3238136.856'],
['1829936.304', '-3238067.307'],
['1829970.006', '-3238014.828'],
['1829969.739', '-3237985.122'],
['1829934.065', '-3237892.636'],
['1829928.018', '-3237808.819'],
['1829911.678', '-3237759.867'],
['1829890.037', '-3237746.091'],
['1829826.524', '-3237732.756'],
['1829739.089', '-3237746.368'],
['1829633.080', '-3237680.587'],
['1829558.529', '-3237686.734'],
['1829516.868', '-3237668.724'],
['1829464.967', '-3237659.687'],
['1829364.924', '-3237615.948'],
['1829312.409', '-3237605.049'],
['1829280.061', '-3237569.848'],
['1829273.684', '-3237522.288'],
['1829290.245', '-3237468.112'],
['1829353.217', '-3237397.127'],
['1829329.545', '-3237247.234'],
['1829308.104', '-3237209.801'],
['1829289.443', '-3237204.445'],
['1829235.164', '-3237217.078'],
['1829100.663', '-3237152.101'],
['1829067.738', '-3237177.139'],
['1829062.856', '-3237221.343'],
['1829046.186', '-3237248.053'],
['1829019.402', '-3237251.989'],
['1828985.913', '-3237232.224'],
['1828968.381', '-3237233.790'],
['1828922.173', '-3237282.727'],
['1828901.318', '-3237289.327'],
['1828844.121', '-3237182.202'],
['1828822.191', '-3237165.064'],
['1828733.547', '-3237121.718'],
['1828685.036', '-3237115.742'],
['1828632.013', '-3237071.453'],
['1828566.550', '-3237048.093'],
['1828545.802', '-3237045.412'],
['1828508.815', '-3237063.973'],
['1828481.129', '-3237059.472'],
['1828464.959', '-3237113.708'],
['1828440.386', '-3237137.125'],
['1828397.567', '-3237154.366'],
['1828388.351', '-3237190.611'],
['1828390.286', '-3237228.979'],
['1828381.847', '-3237237.118'],
['1828339.253', '-3237216.758'],
['1828323.458', '-3237231.757'],
['1828317.185', '-3237245.201'],
['1828320.478', '-3237296.834'],
['1828268.860', '-3237299.688'],
['1828212.770', '-3237324.341'],
['1828185.908', '-3237320.297'],
['1828170.340', '-3237331.124'],
['1828155.782', '-3237329.375'],
['1828139.314', '-3237312.064'],
['1828110.533', '-3237306.958'],
['1828031.357', '-3237316.290'],
['1828016.624', '-3237330.122'],
['1828014.854', '-3237386.527'],
['1828002.702', '-3237400.303'],
['1827956.965', '-3237429.061'],
['1827851.667', '-3237460.252'],
['1827827.078', '-3237531.042'],
['1827839.289', '-3237647.549'],
['1827833.156', '-3237683.042'],
['1827790.529', '-3237741.707'],
['1827786.734', '-3237766.926'],
['1827749.508', '-3237804.159'],
['1827733.895', '-3237854.717'],
['1827647.598', '-3237922.528'],
['1827587.042', '-3237923.707'],
['1827564.401', '-3237947.419'],
['1827519.506', '-3237939.776'],
['1827487.033', '-3237944.741'],
['1827458.030', '-3237980.555'],
['1827458.774', '-3238006.455'],
['1827425.864', '-3238085.291'],
['1827418.256', '-3238127.313'],
['1827370.535', '-3238181.120'],
['1827362.571', '-3238234.045'],
['1827464.503', '-3238387.963'],
['1827462.060', '-3238463.967'],
['1827450.127', '-3238500.580'],
['1827455.408', '-3238570.553'],
['1827471.556', '-3238612.939'],
['1827385.809', '-3238740.163'],
['1827154.723', '-3238948.119'],
['1827140.742', '-3238937.272'],
['1827041.048', '-3238774.397'],
['1826971.637', '-3238687.358'],
['1826948.507', '-3238705.794'],
['1826873.362', '-3238687.737'],
['1826807.692', '-3238547.581'],
['1826768.755', '-3238420.857'],
['1826720.026', '-3238351.323'],
['1826554.765', '-3238062.593'],
['1826533.565', '-3237991.997'],
['1826533.341', '-3237919.246'],
['1826549.338', '-3237849.706'],
['1826670.287', '-3237642.105'],
['1826683.334', '-3237592.821'],
['1826663.727', '-3237543.163'],
['1826518.674', '-3237382.105'],
['1826494.123', '-3237342.331'],
['1826459.375', '-3237177.832'],
['1826495.472', '-3237098.144'],
['1826638.764', '-3236976.583'],
['1826668.729', '-3236924.532'],
['1826682.421', '-3236875.566'],
['1826713.483', '-3236841.167'],
['1826745.591', '-3236781.467'],
['1826803.185', '-3236606.174'],
['1826803.564', '-3236539.269'],
['1826773.001', '-3236448.782'],
['1826783.082', '-3236377.800'],
['1826854.642', '-3236308.761'],
['1826890.009', '-3236214.909'],
['1826936.445', '-3236180.167'],
['1827024.431', '-3236158.317'],
['1827181.609', '-3236075.927'],
['1827240.471', '-3236011.178'],
['1827262.000', '-3235956.751'],
['1827307.430', '-3235920.862'],
['1827437.089', '-3235874.290'],
['1827477.981', '-3235883.653'],
['1827541.025', '-3235932.987'],
['1827590.248', '-3235930.321'],
['1827711.630', '-3235875.094'],
['1827820.787', '-3235850.455'],
['1827849.646', '-3235818.936'],
['1827854.711', '-3235786.603'],
['1827836.023', '-3235736.750'],
['1827787.182', '-3235661.330'],
['1827771.854', '-3235604.897'],
['1827782.069', '-3235536.372'],
['1827817.103', '-3235482.207'],
['1827868.764', '-3235457.440'],
['1827910.952', '-3235413.539'],
['1827925.603', '-3235431.132'],
['1828032.472', '-3235482.082'],
['1828137.470', '-3235550.901'],
['1828309.129', '-3235699.485'],
['1828437.541', '-3235740.624'],
['1828488.964', '-3235867.237'],
['1828626.377', '-3235914.275'],
['1828676.868', '-3235913.796'],
['1828795.362', '-3236009.669'],
['1828827.106', '-3236056.179'],
['1828877.598', '-3236062.785'],
['1828938.744', '-3236124.571'],
['1829038.557', '-3236158.748'],
['1829168.368', '-3236164.570'],
['1829317.950', '-3236079.513'],
['1829492.278', '-3236025.856'],
['1829553.371', '-3235979.519'],
['1829569.386', '-3235781.598'],
['1829763.275', '-3235681.137'],
['1829985.907', '-3234978.341'],
['1830084.642', '-3234991.598'],
['1830103.115', '-3235032.348'],
['1830147.224', '-3235039.088'],
['1830199.403', '-3234995.161'],
['1830189.149', '-3234940.523'],
['1830191.556', '-3234859.155'],
['1830287.759', '-3234824.355'],
['1830337.464', '-3234915.375'],
['1830611.541', '-3234991.131'],
['1833425.390', '-3238626.813'],
['1833361.604', '-3238824.512'],
['1833606.583', '-3238583.326'],
['1833976.391', '-3238589.144'],
['1834240.904', '-3238477.109'],
['1834349.419', '-3238460.625'],
['1834560.042', '-3238491.230'],
['1834616.158', '-3238528.161'],
['1834734.615', '-3238647.457'],
['1834951.986', '-3238938.772'],
['1835039.258', '-3239002.100'],
['1835113.411', '-3239029.358'],
['1835225.012', '-3239037.149'],
['1835337.586', '-3239076.191'],
['1835438.778', '-3239179.715'],
['1835512.146', '-3239236.854']]
对于这一数量的数据点 (~ 200)，我们可以构建简单的 for-loop 覆盖所有顶点对并计算每对顶点的距离。如果此距离高于当前最大值，则成为当前最大值。
此外，您的距离存储为字符串，需要转换为浮点数。
欧氏距离的转换和计算我都用了numpy
在@aerobiomat 的评论建议使用 itertools.combinations 而不是 itertools.product
import numpy as np
from itertools import combinations
lis_lat_long = np.array(lis_lat_long, float)
current_max = 0
for a, b in combinations(np.array(lis_lat_long), 2):
current_distance = np.linalg.norm(a-b)
if current_distance > current_max:
current_max = current_distance
这应该有效：
from itertools import combinations
import math
def calc_dist(p1, p2):
x1 = p1[0] - p2[0]
y1 = p1[1] - p2[1]
return math.sqrt(pow(x1, 2) + pow(y1, 2))
def diameter(data):
data = [list(map(float, c)) for c in data]
combs = list(combinations(data, 2))
print(max([calc_dist(*points) for points in combs]))
Returns 9283.977292891426 为您的数据
有很多关于使用 numpy 及其 einsum 函数确定距离的帖子。 首先，您的字符串数据需要转换为浮点数，然后是一点 einsum 魔法。
a = np.array(lis_lat_long).astype('float')
a0 = a[:, None]
diff = a - a0
dist_arr = np.sqrt(np.einsum('ijk,ijk->ij', diff, diff))
np.max(dist_arr)
Out[42]: 9283.977292891426
时间安排 每个循环 1.52 毫秒 ± 18.5 µs（7 次运行的平均值 ± 标准偏差，每次 1000 次循环） 接受时间 每个循环 213 毫秒 ± 14.9 毫秒（7 次运行的平均值 ± 标准偏差，每次 1 个循环）