3. Визначення опуклої оболонки
Нехай задано деяка множина точок на площині. Опукла оболонка - найменший випуклий многокутник, який містить дані точки.
Уявимо, що площина - це дерев’яна дошка з гвіздками в кожній точці з даної множини. Тепер натягнемо навколо гвіздків резинове кільце. Воно стягнеться і утворить опуклу оболонку, як показано на малюнку вище.
Алгоритм містить наступні операції:
- визначення лівої нижньої точки;
- належність всіх точок одній півплощині відносно прямої проведеної через дві точки;
- визначення точок опуклої оболонки.
Цей алгоритм обводить точки лінією, «завертаючи» в опуклу оболонку. На малюнку дана детальна ілюстрація його дії.
Знаходимо нижню-ліву точку.
Проводимо прямі через дану точку і всі інші точки. Перевіряємо належність всіх точок одній півплощині відносно даної прямої. Якщо це справджується, то знайдена точка є вершиною многокутника і з неї шукаємо аналогічно наступну точку.
В масиві T під номером MIN відмічаємо, знайдену точку як 1.
І координати занести в масиви XN,YN під номером 1.
Повторюємо поки пошук наступної точки дає результат :
- Для кожної точки крім відмічених точок в масиві T[i],
шукаємо наступну точку, провівши через яку пряму всі інші точки лежать в одній півплощині;
для цього перевіряємо, чи є хоча б одна точка лежить в правій площині, якщо немає то дана точка є вершиною опуклої оболонки;
якщо є точки, то перевіряємо аналогічно для лівої півплощини;
- знайдену точку заносимо в масиви XN,YN під номером k+1;
- в масиві T під номером І відмічаємо, знайдену точку як k+1;
відмічаємо дану точку як першу і шукаємо наступну;
Виводимо послідовно точки з XN,YN.
Програмний код:
PROGRAM OBOLONKA;
VAR X,Y,XN,YN,T:ARRAY[1..100] OF INTEGER;
N,I,J,K,MIN,MAX,LICH:INTEGER;
X1,Y1,X2,Y2,XMIN,XMAX,YMIN:INTEGER;
POISK,PT:BOOLEAN;
BEGIN
WRITE('N=');
readln(n);
FOR I:=1 TO N DO READLN(X[I],Y[I]);
FOR I:=1 TO N DO T[I]:=0;
MIN:=1;
FOR I:=2 TO N DO IF X[I]<X[MIN] THEN MIN:=I;
XMIN:=X[MIN];
K:=1;
X1:=X[MIN]; Y1:=Y[MIN];
XN[K]:=X1; YN[K]:=Y1;
T[MIN]:=K;
POISK:=TRUE;
WHILE POISK DO BEGIN
POISK:=FALSE;
FOR I:=1 TO N DO
IF T[I]=0 THEN BEGIN
X2:=X[I];
Y2:=Y[I];
PT:=TRUE;
{}
FOR J:=1 TO N DO
IF (X[J]-X1)*(Y2-Y1)-(Y[J]-Y1)*(X2-X1)<0 THEN
PT:=FALSE;
IF NOT (PT) THEN
FOR J:=1 TO N DO
IF (X[J]-X1)*(Y2-Y1)-(Y[J]-Y1)*(X2-X1)>0 THEN
PT:=FALSE;
IF PT THEN BEGIN K:=K+1;
X1:=X2;
Y1:=Y2;
T[I]:=K;
XN[K]:=X1;
YN[K]:=Y1;
POISK:=TRUE;
END;
END;
END;
WRITELN;
FOR I:=1 TO K DO WRITELN(XN[I],' ',YN[I]);
END.