Генерация нескольких квадратов из облака точек
У меня есть множество точек, и я хочу получить из них все возможные квадраты.
Как я могу сделать, чтобы достичь этого (какие методы?).
Я действовал следующим образом: я последовательно перебираю массив точек, и он не дает всех возможных квадратов. Я создаю один основной цикл, где внутри у меня есть один второй цикл, чтобы получить в каждой итерации дать мне 3 балла
С наилучшими пожеланиями
Решение
Может быть, есть что-то более эффективное, но я бы предложил начать с расчета расстояний между каждой парой точек:
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....
}
}
}
}
}
…хорошо, во время написания я понял, что это может быть полным перебором (слишком много циклов ..), но это может быть отправной точкой.
}
Другие решения
Других решений пока нет …