Задача: Найти центр описанной окружности возле произвольного многоугольника.
Автор:
Разместил: Amro   Дата: 2006-06-01 21:26
Комментарии: (0)   Рейтинг:
Пока комментариев нет

Материал подготовил(и): Altair

Задача:
Найти центр описанной окружности возле произвольного многоугольника.
Дано:
Произвольный n-угольник.
Координаты вершин.
Требуется:
Координаты центра описанной окружности.
При:
Количество углов 2 Не указанно, что многоугольник выпуклый.
Указание:
Счиать описанной окружностью, окружность с наименьшим радиусом, в которую "поместиться" (наложением) многоугольник.

Материал подготовил(и): Altair

1 решение.

Суть алгоритма:
искомая точка обладает следующим свойством - максимальное расстояние от нее до вершин многоугольника минимально! Вот программа под FPC, запускаем, тыкаем мышью, где разместить точки, нажимаем ENTER когда все точки ввели, прога подумает с 2 секунды и нарисует окружность.

Вот код, а сама прога в присоединенном архиве
Код
{$MODE OBJFPC}
{$APPTYPE GUI}
{$E+}
{$E+}
Uses GraphiX, GXCRT, GXMouse, GX2D;
Type
Telem=record
X, Y:longint;
end;
ArrType = array[1..100] of telem;

Function MaxR(TX,TY:longint; A:arrType; n:word):Extended;
var
R:Extended;
i:longint;
Begin
r:=0;
for i:=1 to n do begin
If r r:=SQRT(SQR(a[i].X-TX)+SQR(a[i].y-ty));
end;
Result:=R;
end;

Var
Arr:ArrType;
Tx,Ty,n,i,j,TSuperX,SuperY:longint;
EnterB:boolean; NK:byte; TRR:Extended;
Begin
InitGraphix(ig_detect,ig_col16); {Инициализация графической системы}

{установка графического режима - 1024*768 16 битный цвет}
SetModeGraphix(1024,768,ig_col16);
Bar(0,0,1024,768,rgbcolorRgb(0,0,0)); {заливаем экран черной краской}

{инициализируем мышь и включаем отображение указателя}
InitMouse; MouseON;
EnterB:=false;
n:=0;

{пока не нажата клавиша ENTER}
While not EnterB do begin
Repeat {ждем нажатия клавиши или мыши}
Until (KeyPressed) or (IsMouseInArea(0,0,1024,768)>128);

If keypressed then begin
NK:=ord(readkey);
If NK=13 then EnterB:=true
end
else begin
inc(N);
MouseCoords(Tx,Ty); {получаем координаты курсора}
delay(100); {задержка что бы не было мерцания указателя}
MouseOFF; {выключаем указатель}
putPixel(Tx,Ty,rgbcolorrgb(255,255,255)); {рисуем белую точку}
MouseOn; {сключаем мышь}
arr[n].X:=Tx; {сохраняем в массви координаты точки}
arr[n].Y:=Ty;
end
end;
TRR:=MaxR(1,1,arr,n);

{поиск точки, максимальное расстояние до остальных в которой минимально}
For i:=1 to 1024 do
For j:=1 to 768 do begin
If MaxR(i,j,Arr,n) SuperX:=i; SuperY:=j; TRR:=MaxR(i,j,Arr,n)
end;
end;
MouseOff;
circle(SuperX,SuperY,Trunc(MaxR(SuperX,SuperY,Arr,N)),
rgbcolorrgb(1,118,156));
mouseon;
readkey; {ожидаем нажатия клавиши}
end.


Материал подготовил(и): volvo

2 решение.

Вот мое решение задачи (программа написана под Delphi), но по несколько другому алгоритму:
  1. Вначале по-прежнему ищем пару максимально удаленных друг от друга точек.
    ( назовем найденные точки А и В )
  2. А теперь находим точку, максимально удаленную от центра отрезка АВ (Естественно, сами точки А и В исключаются из поиска).
    Найденную точку назовем С.
  3. Тривиальная задача о построении окружности по трем точкам...
Запускаем ЕХЕ, мышкой выбираем положение точек (до 100), меню File -> Start , получаем окружность. После отрисовки окружности не рекомендуется добавлять точки и запускать алгоритм снова - лучше перезапустить программу...

Материал взят с сайта Всё о Паскале