Рассчитать, если две линии симметричны

Question

Я разрабатываю приложение, чтобы проверить, симметрична ли ничья c или нет. Все строки пользователей сохраняются в ArrayList, составленном из списка точек, также структурированных:

private ArrayList<ArrayList<Pair<Float,Float>>> segments = new ArrayList<>();

Вот как я строю область рисования:

Черная фигура является частью фона, и мне не нужно учитывать это, когда мне нужно проверить симметрию. Мне нужен только его центр (который я храню как одну координату), так как мне нужно рассмотреть возможность проверки симметрии по нему. Поскольку dr aws сделаны детьми, я также должен учесть некоторую гибкость, поскольку линии никогда не будут абсолютно симметричны c. Я реализовал метод, который делит каждый сегмент на 10 частей, а затем проверяет, имеют ли координаты каждой части одинаковое увеличение / уменьшение:

private boolean checkShape (int z, ArrayList<Pair<Float,Float>> points) {
    ArrayList<Pair<Float,Float>> copia = segments.get(z);
    int nGroupsFirstShape = (segments.get(z).size()*10)/100;
    int nValuesFirstShape[] = new int[10];
    for (int j=0, j2=0; j<10; j++, j2+=nGroupsFirstShape) {
        int sumValues=0;
        sumValues+=copia.get(j2).first-copia.get(j2+nGroupsFirstShape-1).first;
        sumValues+=copia.get(j2).second-copia.get(j2+nGroupsFirstShape-1).second;
        nValuesFirstShape[j] = sumValues;
    }
    ArrayList<Pair<Float,Float>> copia2 = points;
    int nGroupSecondShape = (copia2.size()*10)/100;
    int nValuesSecondShape[] = new int[10];
    for (int j=0, j2=0; j<10; j++, j2+=nGroupSecondShape) {
        int sumValues=0;
        sumValues+=copia2.get(j2).first-copia2.get(j2+nGroupSecondShape-1).first;
        sumValues+=copia2.get(j2).second-copia2.get(j2+nGroupSecondShape-1).second;
        nValuesSecondShape[j] = sumValues;
    }
    int differences[] = new int[10];
    int numberOf = 0;
    for (int index=0; index<10; index++) {
        differences[index] = nValuesFirstShape[index] - nValuesSecondShape[index];
        if (differences[index]<0) differences[index] = -differences[index];
        if (differences[index]<nGroupsFirstShape*2.5) numberOf++;
    }
    if (numberOf>=6) return true; else return false;
}

Если это проверено, по крайней мере, для 6 частей, то я могу рассмотреть сегменты симметрия c. Огромная проблема этого метода состоит в том, что линии могут иметь разные размеры. Знаете ли вы какие-либо методы для расчета симметрии области рисования? Поскольку я сохраняю изображение в виде растрового изображения, я также попытался найти способ рассчитать его непосредственно в файле изображения, но ничего не нашел

Answer 1

Я думаю, что это хороший математический алгоритм:

шаг 1: разделите каждую строку на N частей. (квадраты на диаграмме) количество точек на линиях может различаться, но количество частей теперь будет одинаковым.

например, 1 линия была 100 баллов, разделите ее на 10 частей, 10 баллов попадет в каждого. второй из 90 баллов, он получит 10 частей из 9 баллов.

Рассчитайте среднюю точку каждой части. fig1

шаг 2: между каждой средней точкой обеих линий мы находим середину. (черные точки на диаграмме) fig2

шаг 3: строим линию с минимальным отклонением от этих точек. (красная линия на диаграмме) fig3

шаг 4: оценка отклонения средних точек от линии. по среднему и максимальному отклонению можно будет измерить, насколько похожи линии.

удачи

Answer 2

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

Один дал две кривые curve1 и curve2 и центр отражения c. Вы хотите вычислить, если одна кривая является точечным отражением другой в данном пороге maxDist.

Функция для вычисления этого может выглядеть следующим образом:

function checkSymmetry(Curve curve1, Curve curve2, Vector c, float maxDist) {
    // reflect one curve
    Curve curve2refl = reflect(curve2, c);
    // compute curve distance
    float d = dist(curve1, curve2refl);
    // check if distance is below threshold
    return d < maxDist;

(I Я сделал некоторые классы вместо ваших ArrayLists of ArrayLists of Pairs of ... для лучшей читаемости. Я бы рекомендовал вам сделать то же самое в вашем коде.)

Отражение точек

Формула точки Отражение можно найти в Википедии : отражение точки p с центром отражения c равно: 2*c - p.

Чтобы отразить кривую, необходимо отразить все ее вершины .

Кривая расстояния - кривая

Если две красные кривые (почти) симметричны, то после отражения одной из них они должны быть (почти) идентичными, то есть иметь расстояние (почти) ) нуль. Но каково расстояние двух кривых?

В математической теории множеств существует расстояние Хаусдорфа . Это немножко сложно для нематематиков. Но это дает возможность определить расстояние ваших кривых: максимальное расстояние вершины одной кривой до другой кривой:

function dist(Curve curve1, Curve curve2) {
    d = 0;
    for (Vector p : curve1.vertices) {
        d = max(d, dist(curve2, p));
    }
    for (Vector p : curve2.vertices) {
        d = max(d, dist(curve1, p));
    }
    return d;
}

Расстояние от точки до кривой

Таким образом, мы сократили задача вычислить расстояние от точки до кривой. Это минимальное расстояние от точки до любого из сегментов кривой:

function dist(Curve curve, Vector p) {
    d = dist(p, curve.vertices.get(0));
    for (int i = 1, n = curve.vertices.size(); i < n; ++i) {
        Vector p1 = curve.vertices.get(i-1);
        Vector p2 = curve.vertices.get(i);
        d = min(d, dist(new Segment(p1, p2), p));
    }
    return d;
}

Расстояние от точки до сегмента

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