Распознаем фигуры по массиву точек: эллипсы и не выпуклые фигуры

[csl]

Есть ли особая причина использовать index += 1 ? Находится под катом "Код сг расстояний и сглаживания"

Лучше ли будет применить ++index (обсуждение в 2015 году постфиксной и префиксной записи инкремента/декремента https://stackoverflow.com/a/4706225/214296 [хоть там и C++ в тегах])?

[SnakeSolid]

Возможно это имело значение встарых версиях java. Сейчас подобные конструкции компилируются в одинаковый байткод (ссылка на пример в godbolt), так что это скорее вопрос удобства восприятия, чем скорости работы. У меня в коде причина использования += чисто субъективная, связана она с тем, что я пишу не только на java.

Код класса с различными инкрементами

public class Test {
  public static void increment1() {
        for (int index = 0 ; index < 10; index += 1) {}
  }

  public static void increment2() {
        for (int index = 0 ; index < 10; index++) {}
  }

  public static void increment3() {
        for (int index = 0 ; index < 10; ++index) {}
  }
}

Полученный байт код

public static void increment1();
  Code:
     0: iconst_0
     1: istore_0
     2: iload_0
     3: bipush        10
     5: if_icmpge     14
     8: iinc          0, 1
    11: goto          2
    14: return

public static void increment2();
  Code:
     0: iconst_0
     1: istore_0
     2: iload_0
     3: bipush        10
     5: if_icmpge     14
     8: iinc          0, 1
    11: goto          2
    14: return

public static void increment3();
  Code:
     0: iconst_0
     1: istore_0
     2: iload_0
     3: bipush        10
     5: if_icmpge     14
     8: iinc          0, 1
    11: goto          2
    14: return

Версия java

$ java -version
openjdk version "11.0.13" 2021-10-19
OpenJDK Runtime Environment (build 11.0.13+8-post-Debian-1deb10u1)
OpenJDK 64-Bit Server VM (build 11.0.13+8-post-Debian-1deb10u1, mixed mode, sharing)

[FGV]

а в чем разница?

там же вывод приводится:

Because (1) and (4) are decoupled, either pre- or post-increment can be used.

т.е. до лампочки что пре, что пост, что выражение.

[nin-jin]

Насколкьо я понял тут получается квадратичная сложность. А это будет тормозить, когда пользователь нарисует огромную непрерывную фигуру с помощью устройства ввода высокой частоты (а это десятки тысяч точек). К тому же, это будет работать не корректно с такими фигурами как "полукруг".

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

[SnakeSolid]

Я старался чтобы ни один алгоритм не выполнялся с квадратичной сложностью. Если я правильно посчитал, то общая сложность для всех фигур — N * log(N), плюс несколько одиночных проходов по всем точкам, плюс константа зависящая от размера внутренного массива, сейчас это 1024, но его можно уменьшить.

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

Мой расчет сложности

Для всех фигур выполняется преобразование масива точек в массив из 1024 чисел. Преобразование состоит из следующих стадий:

• расчет центра фигуры (один проход по всем точкам);

• расчет расстояния до каждой точки фигуры (тоже один проход);

• сортировка точек по расстоянию (N * log(N) от числа точек);

• заполнение массива расстояний по углам с использованием двоичного поиска (1024 * log(N));

В общей сложности на подготовку нужно N * log(N). Далее для каждый алгоритм идет своим путем:

• эллипс — сглаживает данные (по фиксированному массиву из 1024 элемента, окно фиксированного размера) + один проход по массиву. Итого N * log(N) для эллипа;

• многоугольник — строит корреляцию с ядром (по фиксированному массиву из 1024 элемента, окно фиксированного размера) + один проход по массиву. Итого N * log(N) для эллипа;

• ломанная линия — единственный алгоритм проходящий по всем точкам несколько раз, максимальное число проходов равно максимальному точек в линии. Итого N * const.

В общем случае в худшем случае, сокращая константы будет N * log(N). Далее нужно посчитать отклонение от рисунка пользователя для каждой фигуры.

• эллипс — один проход по всем точкам пользователя. Итого - N;

• многоугольник и ломанная линия — проход по всем точкам, нарисованным пользователем. Итого - N.

В конечном счете, без сокращения, получается: N * log(N) + 5 N + 1024 log(N) + несколько проходов по фиксированному массиву с расстояниями.

[SnakeSolid]

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

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

С углами до следующей точки я не смог придумать ничего хорошо работающего. Если у вас есть идея как это реализовать, хотя бы общие шаги. Я могу попробовать реализовать ваш алгоритм.