Как найти фигуру в серии щелчков мышью?

Мне было интересно, как (если вообще) можно было бы определить форму, учитывая набор координат X, Y щелчков мыши?

Здесь мы имеем дело с рядом проблем, могут быть щелчки (координаты), которые не имеют отношения к форме. Вот пример: http://tinypic.com/view.php?pic=286tlkx&s=6 Зеленые точки обозначают щелчки мышью, и выполняется поиск квадрата не менее x в высоту/ширину, не более y в высоту/ширину и скомпрометированного четырех точек, красные линии указывают на найденную форму. Я хотел бы иметь возможность найти несколько основных форм, таких как квадраты, прямоугольники, треугольники и, в идеале, круги.

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


.net c# shapes c#-4.0 shape
person Faraday    schedule 24.10.2012    source источник
comment
Есть ли ограничение на нерелевантные точки? Например. должна быть только одна нерелевантная точка между двумя релевантными? В противном случае, вероятно, очень сложно и долго будет обнаруживать все возможные формы.   -  person Nico Schertler    schedule 24.10.2012
comment
Хорошо, а как насчет отсутствия нерелевантных точек в пределах x единиц (расстояния) формы? Так ничего внутри и ничего снаружи на определенном расстоянии?   -  person Faraday    schedule 24.10.2012
comment
хорошо, я надеялся на что-то относительно последовательности кликов. Просто для ясности: у вас есть последовательность кликов или только результат? Вы хотите вычислять фигуры после каждого клика или один раз в конце?   -  person Nico Schertler    schedule 24.10.2012
comment
@NicoSchertler У нас просто есть клики в конце, мы просто хотим искать формы в конце.   -  person Faraday    schedule 25.10.2012
comment
Ну а если использовать последовательные нажатия в конце, то это похоже на те системы распознавания жестов, что и в Опере. Если жест соответствует квадратному жесту, то форма квадратная.   -  person Pierre-Alain Vigeant    schedule 25.10.2012

Ответы (1)


arrow_upward
0
arrow_downward

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

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

  • for each point
    • find the closest neighbour point
    • вычислить внутренний угол
    • вычислить расстояние до соседей
  • если все внутренние углы равны 90° +- некоторый порог -> хорошо
  • если все расстояния равны +- некоторый порог (в процентах) -> ок
  • иначе это не четверка.

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

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

Это лишь некоторые мысли, которые могут помочь вам в дальнейшем. Я могу представить, что в ИИ есть алгоритмы, которые могут решить эту проблему более прагматично, может быть, нейронные сети.

person Nico Schertler    schedule 24.10.2012