Алгоритм определения точек, ограничивающих границы фигуры - с помощью javascript

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

Сначала давайте посмотрим, что мы делаем на данный момент. Пользователь хочет нанести на карту область A. Он должен несколько раз щелкнуть по каждой точке, чтобы определить границы фигуры.

possible death by a thousand clicks here

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

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

Конечно, у этого подхода есть некоторые ограничения, но вот что я могу предположить

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

Если кто-то из вас знает о таком алгоритме, это было бы очень здорово.

7
задан samy 21 October 2011 в 15:11
поделиться