Создайте несколько квадратов из облаков точек

Question

У меня есть набор точек, и я хочу, чтобы у него было все возможное квадратное. Как я могу это сделать (какие методы?).

Я продолжал следовать следующим образом. Я последовательно перебираю массив точек и не дает все возможные квадраты. Я создаю один основной цикл, где внутри меня есть один второй цикл, чтобы получить в каждой итерации дают мне 3 балла

С наилучшими пожеланиями

Answer 1

Может быть, есть что-то более эффективное, но мое предложение было бы начать с расчета расстояния между каждая пара точек:

distance[N][N]; 
distance[i][j] = distance between point i and point j 

Далее искать точки j и k, которые имеют одинаковое расстояние от заданной точки i. Мы также должны проверить, что угол 90 °. И вы до сих пор найти четвертую точку ..

for (int i=0;i<N;i++){ 
    for (int j=i+1;j<N;j++){ 
     for (int k=j+1;k<N;k++){ 
      if (abs(distances[i][j] - distances[i][k]) < eps){ 
       if (abs(distances[j][k] - sqrt(2)*distances[i][j]) < eps){ 
        ... find a point with same distance from k and j.... 
       } 
      } 
     } 
    }  
} 

... ну, во время написания я понял, что это может быть полный перебор (слишком много петель ..), но это может быть отправной точкой. }