Здравствуйте, gok, Вы писали:

gok>Конечно не подходит. Эта цитата – слишком общее утверждение. Как если бы автор советовал взять машину если нам надо на речку за городом. Эту машину мы еще строим! По-моему, для невыпуклой оболочки перспективны два подхода: графический (сканировать изображение) или сжимать convex hull. В моем случае число точек измеряется 1.0е+6, перебирать каждый лучик из контрольной точки очень дорого!

Почему не подходит? Нам надо составить ненаправленный граф из имеющихся вершин плюс всех точек пересечения. При этом мы просто обязаны добавить в этот граф все точки пересечения — в наихудших случаях эта операция может быть O(N^2) и от этого никуда не деться. Но на практике — близко к O(N). Далее мы находим точку, гарантированно лежащую на границе и шагаем от этой точки по нашему графу в любом направлении (для определенности — против часовой стрелки). А в узлах с разветвлениями мы шагаем на ту вершину, которая у нас "правее всего" от предыдущего направления. Вот и всех делов...