Нахождение центра окружности, описанной возле произв. многоугольника Опции

[Altair]

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

[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<SQRT(SQR(a[i].X-TX)+SQR(a[i].y-ty)) then
	  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)<TRR then begin
		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 , получаем окружность. После отрисовки окружности не рекомендуется добавлять точки и запускать алгоритм снова - лучше перезапустить программу...