Поиск всех кластеров координат, в которых каждая координата в кластере отделена друг от друга менее чем на некоторое максимальное расстояние - PullRequest
Новая
       13

Поиск всех кластеров координат, в которых каждая координата в кластере отделена друг от друга менее чем на некоторое максимальное расстояние

0 голосов
/ 26 января 2020

У меня есть этот набор координат: 

[[211,76], [235,84], [240,88], [300,79], [230,100], [203,110], [202,95], [203,98], [214,97], [248,137], [249,111], [282,120], [263,144], [245,167], [192,172], [124,161], [322,146], [338,142], [355,146], [322,90], [343,105], [363,105], [368,116], [349,83], [348,67], [348,56], [390,75], [327,69], [443,73], [363,96], [396,104], [467,87], [499,87], [197,201], [199,200], [229,201], [227,219], [243,235], [403,166], [370,189], [399,212], [408,227], [214,292], [297,236], [352,276], [430,304], [437,348], [457,347], [430,277], [459,317], [709,153], [772,113], [828,103], [758,308], [767,320], [771,325], [803,330], [778,346], [795,348], [808,341], [834,341], [831,359], [762,391], [764,402], [817,404], [844,426], [827,440], [862,467], [729,433], [732,449], [747,477], [767,480], [657,454], [647,468], [649,467], [626,480], [670,499], [645,524], [652,547], [649,562], [688,566], [580,645], [580,645], [387,632], [419,625], [417,617], [419,614], [575,419]]

Я хочу найти все кластеры координат, где каждая координата в кластере отделена друг от друга менее чем на максимальное расстояние 215.05813167606567.

Я думал о том, можно ли выбрать координату, а затем добавить ее в пустой список. Затем выберите вторую координату и, если она находится на расстоянии от каждой координаты, уже имеющейся в таком списке, менее чем на 215,05813167606567, добавьте ее в список сразу после существующих координат. Затем выберите третью координату и повторите, добавляя ее в список сразу после существующих координат, если она отделена от каждой координаты, уже находящейся в списке, менее чем на 215.05813167606567. В конечном итоге будет выбрано 88 координат, так как всего 88 координат, некоторые из которых не попадают в список. Есть 88! способ, которым 88 пунктов могут быть выбраны, поскольку выполнение этого процесса является перестановкой с n = 88 и r = 88. Тогда, если еще не было сгенерированного списка координат, разделенных на расстояние меньше максимального значения 215.05813167606567, которые одинаковы, но были выбраны только в другом порядке, то вновь созданный список с координатами, разделенными максимальным расстоянием 215.05813167606567, сохраняется в переменной.

Я попытался сгенерировать каждый из 88! перестановки, для которых нужно выполнить вышеупомянутый процесс условного добавления каждой координаты в другой список с 88 вложенными циклами for в Python, но это не работает, и я не знаю, как еще это сделать. 

elements = [[211,76], [235,84], [240,88], [300,79], [230,100], [203,110], [202,95], [203,98], [214,97], [248,137], [249,111], [282,120], [263,144], [245,167], [192,172], [124,161], [322,146], [338,142], [355,146], [322,90], [343,105], [363,105], [368,116], [349,83], [348,67], [348,56], [390,75], [327,69], [443,73], [363,96], [396,104], [467,87], [499,87], [197,201], [199,200], [229,201], [227,219], [243,235], [403,166], [370,189], [399,212], [408,227], [214,292], [297,236], [352,276], [430,304], [437,348], [457,347], [430,277], [459,317], [709,153], [772,113], [828,103], [758,308], [767,320], [771,325], [803,330], [778,346], [795,348], [808,341], [834,341], [831,359], [762,391], [764,402], [817,404], [844,426], [827,440], [862,467], [729,433], [732,449], [747,477], [767,480], [657,454], [647,468], [649,467], [626,480], [670,499], [645,524], [652,547], [649,562], [688,566], [580,645], [580,645], [387,632], [419,625], [417,617], [419,614], [575,419]]
for x1 in elements:
    tempelements1 = elements.copy()
    tempelements1.remove(x1)
    for x2 in tempelements1:
        tempelements2 = tempelements1.copy()
        tempelements2.remove(x2)
        for x3 in tempelements2:
            tempelements3 = tempelements2.copy()
            tempelements3.remove(x3)
            for x4 in tempelements3:
                tempelements4 = tempelements3.copy()
                tempelements4.remove(x4)
                for x5 in tempelements4:
                    tempelements5 = tempelements4.copy()
                    tempelements5.remove(x5)
                    #...
                        for x88 in tempelements87:
                            permutations = [x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34, x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45, x46, x47, x48, x49, x50, x51, x52, x53, x54, x55, x56, x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67, x68, x69, x70, x71, x72, x73, x74, x75, x76, x77, x78, x79, x80, x81, x82, x83, x84, x85, x86, x87, x88]
                            # 'permutations' is the variable that gets re-assigned one
                            # after another every permutation of the list of 88 coordinates
...