Вычислите, симметричны ли две прямые

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

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

Вот как я строю область рисования: введите здесь описание изображения

Черная фигура является частью фона, и мне не нужно ее учитывать, когда нужно проверить симметрию. Мне нужен только его центр (который я храню как единую координату), так как мне нужно рассмотреть возможность проверки симметрии по нему. Поскольку рисунки делают дети, мне также нужно учитывать некоторую гибкость, поскольку линии никогда не будут точно симметричными. Я реализовал метод, который делит каждый сегмент на 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 частях, то я могу считать отрезки симметричными. Огромная проблема этого метода заключается в том, что линии могут иметь разный размер. Знаете ли вы какие-либо методы расчета симметрии области рисования? Поскольку я сохраняю изображение в виде растрового изображения, я также пытался найти метод, чтобы вычислить его непосредственно в файле изображения, но ничего не нашел.


person Babbara    schedule 14.02.2020    source источник
comment
Какую симметрию вы ищете? Вы упомянули центр. Так является ли это точечным размышлением об известном центре?   -  person Nico Schertler    schedule 14.02.2020
comment
В вашем примере есть несколько изогнутых линий, но ваша структура данных хранит только две точки, что означает, что у вас есть только прямые линии.   -  person Code-Apprentice    schedule 14.02.2020
comment
@NicoSchertler Да, я ищу точечное отражение в центре черной фигуры.   -  person Babbara    schedule 14.02.2020
comment
@Code-Apprentice Кривые сохраняются по пунктам в ArrayList.   -  person Babbara    schedule 14.02.2020
comment
@Babbara Итак, ArrayList в основном представляет собой множество небольших линейных сегментов, составляющих кривую?   -  person Code-Apprentice    schedule 14.02.2020
comment
@Code-Apprentice внешний ArrayList, называемый сегментами, содержит две красные линии, которые вы можете видеть на рисунках. Каждая строка соответствует ArrayList точек.   -  person Babbara    schedule 14.02.2020


Ответы (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;

(Я представил некоторые классы вместо ваших 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;
}

Точка расстояния–сегмент

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

person pH 74    schedule 18.02.2020

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

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

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

Вычислить середину каждой части. рис.1

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

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

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

удачи

person Alexander Prisadkov    schedule 19.02.2020