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

Question

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

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

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

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

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

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

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

Answer 1

Посмотрите на Region Growing алгоритмы. Это в основном то же самое, что алгоритм заполнения потока, описанный выше tokland в базовом случае.

Answer 2

Вы можете использовать алгоритм обнаружения краев (EDA).

В Javascript вы можете использовать Pixastic или свернуть свой собственный.

После обработки EDA ваше изображение получает:

После этого просто перебросьте любую линию в любом направлении от вашей внутренней точки к первойбелый пиксель и следуйте контуру.

Answer 3

Это кажется сложной проблемой (кстати, я не знаю о конкретном алгоритме для этого). Мои 2 цента:

1. Используйте алгоритм flood-fill , но вместо получения всей поверхности получите только периметр.

2. Взять начальную точку периметра и идти в одну сторону; когда вы обнаружите, что накопленная квадратичная ошибка между виртуальным сегментом (текущая точка - начальная точка) и реальным периметром превышает пороговое значение, поставьте точку и начните снова, пока не достигнете начальной точки.

Первый шаг кажется довольно легким, а второй - сложнее.