По моему, то, что у вас точки соединены линиями всех только запутывает.
На мой взгляд задачу следовало бы сформулировать так: Имеется множество точек на плоскости, необходимо
построить замкнутую ломаную таким образом, чтобы ни одна из точек не осталась за границей области, очерченной этой ломаной. Ломаная при этом будет соединять некоторые, но не все, имеющиеся точки. Потом уже, при необходимости от полученной кривой можно бдет сделать отступ, чтоб был запас, как на приведенных рисунках.
Простейший способ решения здесь уже указывался, про треугольники, надо только брать треугольники не только из близлежащих точек, а вообще из всех возможных комбинаций из трех точек.
Т. е. берем три точки, проверяем, находится ли какая-либо точка внутри полученного треугольника, и, если находится - исключаем ее из множества точек, по которым будет проведена граница. Перебираем таким образом все возможные треугольники. В результате у нас останутся только те точки, по которым нужно провести границу. Соединяем их ломаной (каждую точку с двумя ближайшими) и получаем то, что, как я понимаю, требовалось найти.
Решение довольно громоздкое, и если результат работы алгоритма будет давать удовлетворяющие вас результаты, то можно будет думать, как его упростить.
З.Ы. Придумал еще алгоритм
. Соединить имеющиеся точки все со всеми, а потом исключить все линии, которые пересекаются. Останется только внешний контур.
Вопрос по алгоритму определения границы кривой, Возник сложный вопрос и нигде не могу найти ответ!
Mar 20 2009, 09:54
