Как найти ребра и вершины рисованного многоугольника

Question

Я хотел бы создать программу распознавания формы, которая будет отслеживать мышь и записывать ее местоположение каждые полсекунды.Как я могу использовать эти точки, чтобы найти грубый многоугольник?Другими словами, если вы просто нарисуете фигуру, напоминающую треугольник или квадрат, это будет более вероятно, 50-100-гон, как я могу упростить ее, чтобы получить форму, которую я пытался нарисовать?Я знаю, что вы могли бы создать генетический алгоритм, но не знаю точно, как это будет работать, и я хотел бы знать любые альтернативы.

edit: выпуклые оболочки не будут работать, вогнутость необходима для сохранения

Answer 1

Я сделаю снимок.

1. позволяет вызвать позицию, когда происходит событие щелчка мыши, точка START
2. каждый интервал занимает другую позицию CURR
3. Позволяет вызвать предыдущий CURR, PREV
4. вычислить наклон (дельта y / дельта x) между CURR и PREV,
5. рассчитать наклон линии между CURR и START
6. определить некоторый порог для разности между двумя наклонами
7. , если наклон пересекает порог,
   1. сохранить линию между START и CURR как СТОРОНУ
   2. определить CURR как новый START
8. повторять до тех пор, пока CURR не окажется в пределах определенного радиуса исходного START или не пересечет один изпредыдущие стороны

Вы можете определить форму, просто посчитав стороны.

Answer 2

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