Построение оболочек: выпуклой и невыпуклой

Принципы создания

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

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

Где может она понадобиться? Приведу два примера.

Если проводится геодезическая съемка узких трасс, то границы района работ определяются невыпуклой оболочкой.

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

Конечно, если попытаться построить оболочку с минимальной площадью, то получим явно неудовлетворительный результат – оболочка будет сильно изрезанной и будет проходить через ВСЕ точки исходной совокупности. Для получения приемлемых для практики результатов следует ввести критерий остановки процесса построения оболочки. Одним из самых простых и наглядных критериев является введение характеристического расстояния. Оно характеризует расстояние между соседними точками невыпуклой оболочки. Если между какими-либо точками оболочки расстояние больше характеристического, то продолжается процесс поиска еще одной промежуточной точки оболочки.

Вот и все посылки для создания ПО.

Реализация

Примеры

Приведу результаты, которые проиллюстрированы на некоторой случайно сгенерированной совокупности точек.

Рис1	Рис2
Рис3	Рис4

На рис.1 приведена выпуклая оболочка, которая изменяется (Рис.2 - Рис.4) по мере изменения в меньшую сторону задаваемого пользователем характеристического расстояния. Таким образом, подобрав оптимальное характеристическое расстояние можно получить требуемую невыпуклую оболочку. Единственный недостаток – пользователь сам должен определить какая из форм оболочки ему подходит лучше всего.