IPB
ЛогинПароль:

> Внимание! Действует предмодерация

Подраздел FAQ (ЧАВО, ЧАстые ВОпросы) предназначен для размещения готовых рабочих программ, реализаций алгоритмов. Это нечто вроде справочника, он наполнялся в течение 2000х годов. Ваши вопросы, особенно просьбы решить задачу, не пройдут предмодерацию. Те, кто наполнял раздел, уже не заходят на форум, а с теми, кто на форуме сейчас, лучше начинать общение в других разделах. В частности, решение задач — здесь.

 
 Ответить  Открыть новую тему 
> Нахождение центра окружности, описанной возле произв. многоугольника
сообщение
Сообщение #1


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


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


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


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.


Прикрепленные файлы
Прикрепленный файл  circle.rar ( 161.9 килобайт ) Кол-во скачиваний: 1985
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






2 решение.

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


Прикрепленные файлы
Прикрепленный файл  Okruj.zip ( 3.68 килобайт ) Кол-во скачиваний: 552
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 28.06.2017 2:05
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"