Определение того, образует ли массив точек примерно круг

Question

Я и мой друг потратили час или два на то, чтобы сделать код в java, чтобы найти, приблизительно ли массив точек, представленных x[] (для x координат) и y[] (для y координат), приблизительно круг или нет.

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

Мы думали о том, чтобы взять первые 3 точки массива и найти центр (центр окружности) этих 3 точек, затем мы можем найти радиус окружности, образованной этими 3 точками, и если другие точки также удовлетворяют расстоянию форма центра примерно равна радиусу, то у нас есть круг.

Как мы можем это сделать?

Answer 1

"Как мы можем это сделать?"

По сути, немного математики.

Предположим, у вас есть N очков от P ₁ до P _n .

1. Выберите пару точек P ₁ и P ₂ .
2. Найти среднюю точку M ₁ линии L ₁ между точками P ₁ и P ₂ .
3. Построить еще одну линию R ₁ под прямым углом к ​​L ₁ , проходящему через M ₁ .
4. Повторите шаги с 1 по 3 для точек P ₂ и P ₃ , чтобы получить вторую строку R ₂ .
5. Найдите точку пересечения R ₁ и R ₂ . Это кандидат в центр C круга.
6. Для каждой точки P _i рассчитайте расстояние от C до P _i .

Если ваши точки «примерно» в круге, то расстояния от каждой точки до центра будут «примерно» одинаковыми.

Шаги с 1 по 6 можно превратить в аналитические формулы с помощью некоторой простой алгебры. Разработайте формулы, затем превратите их в код.

Answer 2

Итак, я поиграл в Python (просто потому, что мне проще всего прототипировать решение) и придумал следующее:

from collections import namedtuple
from math import sqrt
from statistics import mean

Point = namedtuple('Point', ['x', 'y'])

def length_between_points(a: Point, b: Point):
    squared = (pow(a.x - b.x, 2) + pow(a.y - b.y, 2))
    return sqrt(squared)

def normalize(raw):
    return [float(i)/max(raw) for i in raw]

def is_roughly_circle(x, y, confidence=0.1):
    center = Point(x=mean(x), y=mean(y))
    points = [Point(x[i], y[i]) for i in range(len(x))]

    lengths_from_center = [length_between_points(p, center) for p in points]
    normalized = normalize(lengths_from_center)
    is_circle = all([length > 1 - confidence for length in normalized])
    return is_circle


x = [1, 2, 3, 4, 5]
y = [1, 2, 3, 4, 5]
print(is_roughly_circle(x, y)) # False

x = [0, 1, 0, -1]
y = [1, 0, -1, 0]
print(is_roughly_circle(x, y)) # True

x = [0, 1.1, 0, -1]
y = [1, 0, -1, 0]
print(is_roughly_circle(x, y)) # True

x = [0, 1.2, 0, -1]
y = [1, 0, -1, 0]
print(is_roughly_circle(x, y)) # False

x = [0, 1.2, 0, -1]
y = [1, 0, -1, 0]
print(is_roughly_circle(x, y, confidence=0.2)) # True

Предположения:

1. Лучше рассчитать центр всех точек, а не только первые 3. Он не самый оптимальный, но обрабатывает случай, если первая точка ввода находится в геометрическом центре.
2. Овалы и эллипсы не являются "примерно кругом"
3. Как можно установить «грубый» круг с помощью параметра достоверности [0,1)

Алгоритм:

1. Рассчитать среднее значение всех точек (в центре)
2. Рассчитать расстояние от центра для всех точек
3. Нормализация расстояний до диапазона [0,1]
4. Все значения в нормализованном векторе больше 0,9?
5. Если это так, набор точек представляет собой круг с уверенностью 0,1.

Answer 3

Это потенциальное O (n) решение, которое, я считаю, работает. Он использует простое двумерное уравнение круга: x^2 + y^2 = r^2. Я на самом деле не проверял это, поэтому возьмите его с крошкой соли.

Кроме того, вы не изложили все допущения в своей проблеме. Являются ли отношения между x и y один-к-одному? Как насчет порядка элементов? Они одинаковой длины? Что означает примерно ?

Предполагая, что x и y являются целочисленными массивами одинаковой длины с упорядоченным однозначным отображением, вы можете циклически перебирать x и y и создавать новый массив со значениями x^2 + y^2. Давайте назовем этот новый массив r2.

Сейчас настало время, чтобы определить «примерно». Предположим, что если все значения r2 равны допустимому смещению delta = 10, у нас есть круг. Вы можете выбрать любое произвольное значение для delta, чтобы оно соответствовало вашему определению грубого круга.

В псевдокоде это будет выглядеть так:

delta = 10;
r2 = [];
for i = 0 to length(x) {
    r2.append(x[i] * x[i] + y[i] * y[i]);
}

random_r2_value = r2(randomInt(0, length(r2));
upper_bound = random_r2_value + delta;
lower_bound = random_r2_value - delta;

isCircle = true;

for value in r2 {
    if value >= lower_bound && value <= upper_bound {
    // yay
    continue;
    } else {
        isCircle = false;
        break;
    }
}

print(isCircle)

И вы можете объединить два цикла, используя жадный метод, если хотите.

Удачи!