Определить форму на основе произвольного количества точек - PullRequest
2 голосов
/ 03 марта 2011

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

По сути, через сенсорный интерфейс пользователь «рисует» фигуру (и это отслеживается через определенное количество точек касания), и у меня остается количество точек на 2-й поверхности.

Исходя из этих точек, мне нужно приблизительно определить, является ли обведенная фигура треугольником, квадратом или кругом. Что было бы самым простым способом сделать это? Есть идеи?

Ответы [ 2 ]

2 голосов
/ 03 марта 2011

Хорошим первым шагом было бы уменьшить количество точек, чтобы найти, где пользователь пытается нарисовать прямые линии - для этого подходит алгоритм Ramer – Douglas – Peucker .

1 голос
/ 03 марта 2011

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

Охарактеризуйте круг как центральную точку и радиус.Найдите точку и радиус, которые минимизируют дисперсию.Дисперсию в этом случае легко рассчитать для данной точки и радиуса.Быстрый поиск в Google находит бумагу под названием Поиск круга, который наилучшим образом соответствует набору точек с необходимой математикой.

Квадрат имеет центральную точку, длину стороны и угол поворота (0до 90 градусов).Дисперсию немного сложнее вычислить, потому что вам нужно либо определить квадрант, чтобы найти ближайшую сторону, до которой нужно минимизировать расстояние, либо рассчитать расстояние до всех четырех сторон и оставить только наименьшую.Тот же принцип, но у вас есть три переменные вместо двух.

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...