Построение выпуклой оболочки методом Джарвиса

[noname00.pas]

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

1. Находим пару точек A(x1, y1) и B(x2, y2)таких, что все другие точки лежат по одну сторону от прямой, на которой лежит отрезок AB. Эти две точки будут включены в выпуклую оболочку

Это можно сделать например полным перебором всех вариантов. А можно и не полным перебором. Например можно найти точку с наименьшей абсциссой и перебором найти для неё пару.

2. Для одной из точек (ну пусть будет B) находим точку C (не совпадающую с A) такую, что все другие точки лежат по одну сторону от прямой, на которой лежит отрезок BС.
Включаем точку C в нашу выпуклую оболочку.

3. По аналогии со 2-м пунктом находим для каждой новой точки такую точку, что все другие точки по одну сторону от прямой...
И так до тех пор, пока новая найденная нами точка не совпадёт с точкой A.

Я понятно объяснил, или может стоит запостить пример програмки?

ПС Я слышал такое странное название для этого метода - "Метод заворачивания подарков"

[vasketsov]

можно просто пройти по всем вершинам в одном направлении и для трех соседних вершин проверять целесообразность соединения 1-й и 3-й (включить 2-ю в ВО).
И так крутиться пока не будет отсутствие изменений.

Если вообще понятно, что я написал.

[noname00.pas]

vasketsov
А если у тебя не прямоугольник в порядке обхода по часовой стрелке, а просто множество точек?

ПС Мы кстати о методе Джарвиса. Кстати этот медод самый простой в реализации из всех известных мне...

[noname00.pas]

vasketsov
Кстати что ты называешь "целесообразностью" и как ты собираешься её проверять?

[vasketsov]

Это если дан многоугольник и порядок его обхода.

Берешь <=4 точки (с максимальной и минимальной абсциссой и ординатой). Получаешь 4 (или 3)-угольник. Если совсем вырожденный случай - 2-хугольник :)) получишь. Пусть N углов.

Дальше проходишь цикл по всем точкам и выкидываешь все внутренние точки.
Посте этого выбираешь одну любую точку (внешнюю) и добавляешь ее к ВО (исходя из ее абсциссы и ординаты). Для треугольника, который она добавила, опять выкидываешь все внутренние точки.

И так далее, пока множество внешних точек не будет пустым.

Хотя, я так подумал, по числу операций тоже O(N*N), как и метод Джарвиса.

[noname00.pas]

vasketsov
Да, только метод Джарвиса пишется буквально в несколько строк...
Я всегда им пользуюсь

[Guest]

Пожалуйста, вставте исходнике, ещ просьба чтобы они были на Паскале.
Заранее спасибо!

[karina20]

для студента:
Уважаемый, если вы так хорошо разбираетесь в методе Джарвиса,не могли бы вы поместить программную реализацию данного метода(на Delphi али на Pascal-у).А то,что-то у меня не получается.Заранее большое-прибольшое СПАСИБО!!!!!!!

[hasherfrog]

Э-хе-хе :( Посмотрите на дату создания темы и её последнего поста от noname00.pas

См.: решения (http://www.google.ru/search?hl=ru&client=firefox-a&rls=org.mozilla%3Aen-US%3Aofficial&q=Algorithm+Jarvis+March&btnG=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA&lr=).

[karina20]

hasherfrog,благодарю! :4u: