Обнаружение "вогнутого корпуса" на карте

Question

Я разрабатываю плагин JavaScript с открытым исходным кодом для Waze - широко известного бесплатного навигатора GPS - специально для онлайн-редактора. Идея этого пользовательского сценария состоит в том, чтобы сделать возможным быстро выбрать большие однородные цветные области карты, чтобы преобразовать их в ориентиры.

До сих пор я успешно реализовал инструмент, который вы бы назвали "Волшебная палочка" в графических редакторах, таких как Photoshop: пользователь щелкает мышью где-нибудь на карте (скажем, на озере или в лесу), и скрипт выбирает всю область, покрытую тем же цветом, и создает многоугольник. для ориентира.

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

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

Я искал Google для подходящего алгоритма и копался в математических работах, но мне все еще не повезло найти его. Самый популярный вопрос о вогнутых корпусах здесь, на Stackru, относится к альфа-форме вместе с треугольниками Делоне. Хотя я не понимаю, как использовать это в случае: все точки соединены друг с другом, образуя непрерывную ломаную линию, поэтому мне кажется, что я не могу найти подходящий альфа-радиус, так как четная окружность с радиусом, равным 1 пикселю, будет подвергаться альфа-экспозиции.

Будем очень благодарны за любые идеи как архивировать цель строительства вогнутого корпуса! Может быть, я двигаюсь в неправильном направлении и мне нужно взглянуть на алгоритмы векторизации растровых изображений?

Answer 1

Вы можете прочитать, как реализовать алгоритм вогнутой оболочки в этой статье. Основная идея состоит в том, чтобы построить выпуклый корпус и изогнуть (вогнутые) края внутрь. Есть реализация JavaScript этого алгоритма: hull.js.

Answer 2

Формы альфа определяются путем нахождения триангуляции Делоне для набора точек, а затем удаляются ребра, которые превышают альфа. Вам нужна триангуляция Делоне, но не круги. Это также работает с линиями. Чтобы вычислить форму с помощью JS, вы можете использовать TopoJSON или попробовать этот ответ: Рассчитать ограничивающий многоугольник альфа-формы из триангуляции Делоне. Вы также можете попробовать мой пакет php http://concavehull.codeplex.com/.