Алгоритм нахождения минимального контура

Не понял, откуда контуры брать.

У тебя изначально есть множество контуров, и из них нужно выбрать минимальный? Или множество точек + множество отрезков с концами в этих точках, и из них нужно строить минимальный контур?

я, думаю, дана точка и набор многоугольников. необходимо найти минимальный многоугольник, содержащий данную точку.

P.S хотя нет видимо нужно действительно провести минимальный контур

На знаю как выразиться. Заданы как бы ребра графа. Линии контуров. Контур надо построить.

convex hull

причем тут выпуклая оболочка по точкам?

нет, многоугольники изначально не заданы

http://inis.jinr.ru/sl/vol1/CMC/Preparata,Sheimos,Vychislitelnaya geometriya,...

Шеймос, Препарата - «Вычислительная геометрия. Введение.»

Тебе нужна Глава 2 геометрический поиск. Если точнее, то 2.2.2 Локализация точки на планарном подразбиении.

минимальный контур

выпуклый

ты смотрел вообще примеры, что я выложил? Минимальный по площади.

Да, похоже, это то самое. Спасибо.

о! Вот эта книга! А я ее искал, никак вспомнить не мог. Спасибо, Waterlaz.

Кинуть луч вправо, найти первое пересечённое ребро. Далее идти по рёбрам, начав вверх по текущему ребру, в каждой вершине пути выбирая то, которое максимально отклоняется влево.

впуклый

Народ, а огибающую выпуклую оболочку вообще реально хотя бы за O(ln(N)) построить или таки O(N³) — минимум?

LMGTFY

http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Mo...

O(N*ln(N))

За O(ln(N)) вряд ли.

Весьма признателен!