Есть ли способ найти полигоны в заданных точках?

Question

В настоящее время я работаю над тем, чтобы найти прямоугольники / многоугольники в максимум 15 заданных точках (изображение ниже).

Заданных точек

Моя цель -это найти полигоны в этом массиве точек, как я отметил на изображении ниже.Полигоны - это прямоугольники в реальном мире, но они немного искажены, поэтому они могут выглядеть как многоугольники или другие формы.Я должен найти лучший прямоугольник / многоугольник.

Моя идея состояла в том, чтобы проверить все соединения между точками, но общее количество, которое должно быть большим, чтобы пройти, и заняло.

Есть ли у кого-нибудьИдея, как решить эту проблему, я исследовал в сети и нашел алгоритм k-Nearest в sklearn для python, но у меня нет опыта с этим, если это правильный способ решить и как это сделать.Возможно, мне также понадобится метод, чтобы отфильтровать некоторые выбросы, чтобы алгоритму было еще легче найти правильные угловые точки многоугольника.

Фрагмент кода ниже разбивает данную строку точек на отдельныеМассивы, массив координатOnly содержит только значения x и y точек.

Большое спасибо за помощь.

Полигон в заданных точках

import math
import numpy as np
import matplotlib.pyplot as plt
import time

from sklearn.neighbors import NearestNeighbors


millis = round(int(time.time())) / 1000

####input String
print("2D to 3D convert")

resultString = "0,487.50,399.46,176.84,99.99;1,485.93,423.43,-4.01,95.43;2,380.53,433.28,1.52,94.90;3,454.47,397.68,177.07,90.63;4,490.20,404.10,-6.17,89.90;5,623.56,430.52,-176.09,89.00;6,394.66,385.44,90.22,87.74;7,625.61,416.77,-177.95,87.02;8,597.21,591.66,-91.04,86.49;9,374.03,540.89,-11.20,85.77;10,600.51,552.91,178.29,85.52;11,605.29,530.78,-179.89,85.34;12,583.73,653.92,-82.39,84.42;13,483.56,449.58,-91.12,83.37;14,379.01,451.62,-6.21,81.51"


resultString = resultString.split(";")

resultStringSplitted = list()
coordinatesOnly = list()
for i in range(len(resultString)):
        resultStringSplitted .append(resultString[i].split(","))
        newList = ((float(resultString[i].split(",")[1]),float(resultString[i].split(",")[2])))
        coordinatesOnly.append(newList)
        for j in range(len(resultStringSplitted[i])):
                resultStringSplitted[i][j] = float(resultStringSplitted[i][j])

#Check if score is valid
validScoreList = list()
for i in range(len(resultStringSplitted)):
        if resultStringSplitted[i][len(resultStringSplitted[i])-1] != 0:
                validScoreList.append(resultStringSplitted[i])
resultStringSplitted = validScoreList

#Result String array contains all 2D results
# [Point Number, X Coordinate, Y Coordinate, Angle, Point Score]
for i in range(len(resultStringSplitted)):
        plt.scatter(resultStringSplitted[i][1],resultStringSplitted[i][2])

plt.show(block=True)

Answer 1

Поскольку вы упомянули, что у вас может быть максимум 15 баллов, я предлагаю проверить все возможные комбинации из 4 баллов и оставить все прямоугольники достаточно близкими к идеальным прямоугольникам. Для 15 очков это «только» 15*14*13*12=32760 потенциальные прямоугольники.

import math
import itertools
import numpy as np

coordinatesOnly = ((0,0),(0,1),(1,0),(1,1),(2,0),(2,1),(1,3)) # Test data
rectangles = []

# Returns True if l0 and l1 are within 10% deviation
def isValid(l0, l1):
    if l0 == 0 or l1 == 0:
        return False
    return abs(max(l0,l1)/min(l0,l1) - 1) < 0.1

for p in itertools.combinations(np.array(coordinatesOnly),4):
    for r in itertools.permutations(p,4):
        l01 = np.linalg.norm(r[1]-r[0]) # Side
        l12 = np.linalg.norm(r[2]-r[1]) # Side
        l23 = np.linalg.norm(r[3]-r[2]) # Side
        l30 = np.linalg.norm(r[0]-r[3]) # Side
        l02 = np.linalg.norm(r[2]-r[0]) # Diagonal
        l13 = np.linalg.norm(r[2]-r[0]) # Diagonal
        areSidesEqual = isValid(l01,l23) and isValid(l12,l30)
        isDiag1Valid = isValid(math.sqrt(l01*l01+l30*l30),l13) # Pythagore
        isDiag2Valid = isValid(math.sqrt(l01*l01+l12*l12),l02) # Pythagore
        if areSidesEqual and isDiag1Valid and isDiag2Valid:
            rectangles.append(r)
            break

print(rectangles)

Требуется приблизительно 1 секунда, чтобы бежать на 15 пунктах на моем компьютере. Это действительно зависит от того, каковы ваши требования к времени вычислений, то есть к реальному времени, интерактивному времени, «я просто не хочу тратить дни в ожидании ответа».