Визначення опуклої оболонки ⇐ ПредыдущаяСтр 3 из 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.
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|