Помощь - Поиск - Пользователи - Календарь
Полная версия: Площадь фигуры,образованная окружностями.
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Vardes
Рассматриваются n лучей,проведённых в плоскости из точки О.Углы между соседними лучами равны 2pi/n.На лучах выбраны точки A1,А2..An и из этих точек как из центров проведены окружности,проходящие через точку O.Необходимо вычислить площадь фигуры,образованную всеми окружностями.
В этом как раз вся и проблема.
Все идеи свои я исчерпал.Если у вас есть свои размышления,прошу напишите их.

Вот рисунок:

М
Сообщения объеденены ... а на следюющий раз знай, что есть кнопака "правка"
klem4

klem4
Цитата
.Необходимо вычислить площадь фигуры,образованную всеми окружностями.


А можешь показать где такое есть на твоем рисунке ? Я например не вижу пересечения левой окружности и правой или верхней с нижней ... да и вообще помойму данных маловато для решения...
volvo
To: klem4
А кто тебе сказал "площадь, образованную пересечением всех окружностей"? Найти нужно:
Цитата
площадь фигуры, образованную всеми окружностями.
, а это не одно и то же. Нужна площадь самой фигуры, образованной окружностями...
klem4
Так точно, теперь вижу ... прошу прощения за невнимателность.
Vardes
Ну вот в принципе площадь чего надо найти:
volvo
По-моему, классическая задача для метода Монте-Карло... cool.gif
Vardes
А можно как-то этот метод Монте-Карло пояснить?
volvo
Можно... Допустим, у тебя есть прямоугольник, в который полностью помещается твоя фигура, и ты точно знаешь его площадь. Тогда ты генерируешь большое количество случайных точек (чем больше точек - тем точнее результат), точно находящихся внутри прямоугольника, и проверяешь, сколько из них попадают в твою фигуру (зная координаты центров всех окружностей и их радиусы, несложно вычислить, попадает ли заданная точка в фигуру)...

Естественно, что чем больше точек попадут внутрь твоей фигуры, тем ее площадь больше yes2.gif А саму площадь вычисляешь так:
Цитата
S фигуры = S прямоугольника * ({Число попаданий} / {Общее число сгенерированных точек})


(бери число испытаний в районе 500 тыс - 1 млн, и в течении 5-7 секунд получай ответ...)
Vardes
Тогда у меня возникают такие вопросы,как же мне задать мой прямоугольник,ведь количество лучей у меня не ограничено,и может доходить до 10,15 и т.д.
И ещё,бывет так,что окружности накладывается др. на др.,следовательно точка попадёт и в ту и в др. окружность.
volvo
Цитата
как же мне задать мой прямоугольник, ведь количество лучей у меня не ограничено, и может доходить до 10,15 и т.д.
это совершенно безразлично... В любом случае ты ВСЕГДА можешь вычислить самую верхнюю/нижнюю и левую/правую точки фигуры... По ним и строй прямоугольник...
Цитата
И ещё,бывет так,что окружности накладывается др. на др.,следовательно точка попадёт и в ту и в др. окружность.
Нет. Как только точка попала в какую-то окружность, вся дальнейшая работа с этой точкой прекращается, ведь она УЖЕ внутри фигуры, и ты переходишь к следующей точке...

Вот тебе пример (по твоему же рисунку), как выбрать прямоугольник...
Vardes
Тогда получается,что мне надо вводить оси координат,если речь уже заходит о координатах,а как я могу их воодить,если все точки имеют положительное значение.
volvo
To: Vardes
Ну вот скажи мне, что именно тебе не понятно? Какие точки имеют положительное значение? Ты что, не умеешь генерировать отрицательные случайные числа? Кто тебе запрещает их генерировать?

Это первое. А второе, я не говорю о глобальных координатах. Ты вполне можешь принять свою систему координат, в которой точка пересечения осей будет не (0, 0) а, скажем, (100, 100)... Это ничего не меняет. Если ВЕСЬ график начерчен в одной системе координат, результат будет правильным...

Кстати, программа, вычисляющая площадь твоей фигуры (вместе с графическим представлением) занимает меньше 150 строк... blum.gif
Vardes
Ну вот введу я систему координат,мне необходимо чтобы все лучи выходили из одной точки(это ладно),но и углы между лучами должны быть равными.И ещё,мой препод будет вводить только радиусы этих окружностей(2,3,4 и т.д) и всё,а не координаты центров окружностей.
И генерировать числа я пока тоже не умею,т.к. опыта у меня немного.Ещё пробовал решать эту задачу через центральный угол,найдя его можно пощитать площадь кругового сектора.Рассчитав площадди всех секторов,можно найти площадь и всей фигуры.Вот.
Но тут есть загвоздка,дело в том,что если окружностей много,то происходит большое количество наложений,чуть ли одна не вписывается в др.,поэтому условия все предусмотреть очень сложно. mega_chok.gif
volvo
To: Vardes
Полярную систему координат еще никто не отменял rolleyes.gif Там как раз очень просто реализовать то, что ВСЕ лучи выходят их одной точки (r = 0), и углы между лучами равны: (Phi изменяется с шагом 360 div n, где n - количество лучей)...

Для того, чтобы узнать координаты центра окружности в полярной СК достаточно на соответствующем луче поставить точку, для которой удаление от центра координат r = {нужный тебе радиус}...

А уже потом, когда у тебя есть все координаты в полярной CK, переводишь их в декартову и делаешь то, что я тебе написал в посте №8.

Кстати, для генерации случайного числа X в интервале -100 .. 100 достаточно сделать
X := Random(201) - 100;
Vardes
Значит я так понимаю,что радиусы окружности и лучи можно задать таким образом.Где L-это полярная ось,P-центр окружности,и углы.
Вот рисунок:
Vardes
А декартовы координаты тогда можно будет выразить так:x=p*cos угла 360/n;
y=p*sin угла 360/n.
volvo
yes2.gif Правильно понимаешь... Еще какие-то затруднения?
Vardes
Да,необходимо определить принадлежит ли точка к плоскости какой-то из наших окружностей,чтобы её нам запомнить и разделить потом на общее количество таких точек.
Ещё хотел по-больше узнать о генерации случайного числа x и y:нам надо брать те границы чисел,которыми у нас ограничен прямоугольник.НАпример он у нас ограничен следущими координатами 4 точекsad.gif6,0);(-5,0);(0,4);(0,-7),как тогда нам сгенерировать числа по x и y.
Vardes
Цитата
Да,необходимо определить принадлежит ли точка к плоскости какой-то из наших окружностей,чтобы её нам запомнить и разделить потом на общее количество таких точек.

Есть такая идея проверять ту или иную точку,образует ли она радиус вписанной окружности в нашу(конечно же,центр у них должен быть одинаковым)если образует,то мы её запоминаем.
volvo
To: Vardes
Ты что, издеваешься? Геометрию учил? У тебя есть координаты центра каждой окружности, так? Их радиусы тоже есть, так? Допустим, сгенерировал точку с координатами (point_x, point_y). Дальше - вот так:
i := 1; found := false;
while (i <= n) and not found do begin
if sqrt(sqr(x[i] - point_x) + sqr(y[i] - point_y)) < radius[i] then found := true;
inc(i)
end;
{
если found = true, точка (point_x, point_y) находится
внутри хотя бы одной окружности, иначе - не попадает ни в одну
}

вот и все...
Vardes
Блин,точно...
Просто у меня уже голова кипит от этой задачи,но цель уже поставлена,поэтому и пытаюсь всякими извращёнными способами достигнуть её.НУ всё же остаётся поставленный вопрос про генерирование точки в посте №18.
volvo
Значит, у тебя прямоугольник ограничен -5 <= x <= 6 и -7 <= y <= 4?
randomize;
point_x := random(12) - 5;
point_y := random(12) - 7


Общий случай: чтобы сгенерировать случайное число в интервале [a .. b]:
X := random(b - a + 1) + a;
Vardes
Вот реализация части програмного кода,до нахождения max и min значения x и y.
Код


const
pi=3.14159;
var
n,i:integer;
miny,maxy,minx,maxx,r,x,y:real;
mas:array[1..50] of real;
begin
Writeln('‚Введите кол-во окружнростей-');
readln(n);
Writeln('‚Введите радиус окружностей-');
minx:=0;maxx:=0;
miny:=0;maxy:=0;
for i:=1 to n do
readln(mas[i]);
  for i:=1 to n do begin

x:=mas[i]*(cos(2*pi/n*(i-1)));{нахождение декартовых координат}
y:=mas[i]*(sin(2*pi/n*(i-1)));
writeln(x:2:2,'   ',y:2:2);
{нахождение min и max значения x и y}

if x-mas[i]<=minx then minx:=x-mas[i];  
if x+mas[i]>=maxx then maxx:=x+mas[i];
  if y-mas[i]<=miny then miny:=y-mas[i];
    if y+mas[i]>=maxy then maxy:=y+mas[i];
end;
writeln(minx:2:2,'  ',maxx:2:2,'  ',miny:2:2,'  ',maxy:2:2)
end.

volvo
To: Vardes
Ну, и что нам делать с этим кодом? Если уж выкладываешь, то или выкладывай полный код (когда закончишь), или задавай вопросы (если что-то не получается...)
Vardes
Правилен ли будет код для генерации случайных точек и их проверки(ссылаясь на код выше),так как у меня идёт зацикливание.
Код

var
found:boolean;
point_x,point_y:integer;
begin
randomize;
point_x:=random(round((maxx-minx+1)+minx));
point_y:=random(round((maxy-miny+1)+miny));
Sum:=0;
For i:=1 to n do
While not found do begin
If Sqrt(sqr(point_x-x)+sqr(point_y-y))<=mas[i] then found:=true;
Inc(Sum);
end;
volvo
point_x:=random(round(maxx-minx+1))+minx;
point_y:=random(round(maxy-miny+1))+miny;
Vardes
Всё исправил,но всё равно идёт зацикливание. не пойму в чём дело.
Код
const
pi=3.14159;
var
found:boolean;
sum,n,i:integer;
point_x,point_y,miny,maxy,minx,maxx,r,x,y:real;
mas:array[1..50] of real;
begin
Writeln('‚Введите кол-во окружнростей-');
readln(n);
Writeln('‚Введите радиус окружностей-');
minx:=0;maxx:=0;
miny:=0;maxy:=0;
for i:=1 to n do
readln(mas[i]);
 for i:=1 to n do begin

x:=mas[i]*(cos(2*pi/n*(i-1)));{нахождение декартовых координат}
y:=mas[i]*(sin(2*pi/n*(i-1)));
writeln(x:2:2,'   ',y:2:2);
{нахождение min и max значения x и y}

if x-mas[i]<=minx then minx:=x-mas[i];  
if x+mas[i]>=maxx then maxx:=x+mas[i];
 if y-mas[i]<=miny then miny:=y-mas[i];
   if y+mas[i]>=maxy then maxy:=y+mas[i];
end;
writeln(minx:2:2,'  ',maxx:2:2,'  ',miny:2:2,'  ',maxy:2:2)
begin
randomize;
point_x:=random(round(maxx-minx+1))+minx;
point_y:=random(round(maxy-miny+1))+miny;
Sum:=0;
For i:=1 to n do
While not found do begin
If Sqrt(sqr(point_x-x)+sqr(point_y-y))<=mas[i] then found:=true;
Inc(Sum);
end;
writeln(sum);
end.
volvo
Данные, которые вводишь, приведи... И объясни, что значит "зацикливание"...

Ну, я же тебе не так говорил делать !!! Внимательно читай пост №20.
Условие под последним While может и не закончиться. Вот так перепиши его (нужно же ограничивать перебор числом окружностей):
While (i <= n) and (not found) do begin


Кстати, а с каким именно X и Y ты производишь операции? Ты их сохранил куда-то (в массив), когда преобразовал из полярной СК? Я у тебя в коде этого не увидел... Более того, у тебя даже массива для этого не описано...
Vardes
Провожу такой ввод данных:
n- кол-во окружностей и ввожу радиус окружности,переводя его в массив
mas[1..n].Вот и все данные.
Проблема в том,что постоянно работает цикл while как взял i=1,так постоянно и гоняет себя не переходя на др. значения i.Переделал и всё равно гоняет.
volvo
Я тебе уже написал почему... Вот НЕзацикливающийся вариант. Я не проверял все формулы, если там все правильно, то тебе осталось только зациклить генерацию точки, сделать это несколько сот тысяч раз (не меньше 200000-250000, лучше - несколько миллионов), посчитать количество попаданий, и вычислить площадь (как - см. пост №8)...
Vardes
значит генерация происходит по одной точке,если я правильно понимаю.Как же тогда можно генерировать несколько тысяч раз,если у нас промежуток по x[-4:5],а по у [-3;9].Принцип не могу понять.
volvo
var amount: longint;
...
for amount := 1 to 200000 do begin
randomize;
point_x:=random(round(maxx-minx+1))+minx;
point_y:=random(round(maxy-miny+1))+miny;

i := 1; found := False;
While (i <= n) and not found do begin
If Sqrt(sqr(point_x-x[i])+sqr(point_y-y[i]))<=mas[i] then found:=true
else inc(i);
end;
write(point_x:3:3, ', ', point_y:3:3);
if found then writeln(' is inside circle #', i)
else writeln(' is outside');
end;

у тебя сгенерируется 200000 точек и каждая проверится на попадание в фигуру. Только надо организовать подсчет (вместо Writeln)
Vardes
так это всё понятно,я про принцип спрашивал,откуда берётся такое большое кол-во точек,если у нас промежуток маленький.
volvo
To: Vardes
А тебе все равно, какой у тебя промежуток. Если у тебя прямоугольник (граничные точки) размером 5*5, а сама фигура - размером 3*3, я что, не могу сгенерировать 5 миллионов точек, КАЖДАЯ из которых будет находиться в прямоугольнике? И проверить, сколько попадет в фигуру? Пускай из них будет по полмиллиона точек повторяться, это НЕ твоя проблема. Это и есть Monte-Carlo (Метод Рулетки)
Vardes
Ну ведь каждая сгенерированная точка имеет свои координаты,для вещественного типа их можно сколько угодно сгенерировать,а если у нас генерирование идёт целых чисел, да и промежуток небольшой,то как тогда поступать.
volvo
Ну, так генерируй с точностью до сотых:
  randomize;
point_x:=(random(100*round(maxx-minx))+100*minx)/100;
point_y:=(random(100*round(maxy-miny))+100*miny)/100;

blush.gif Теперь более ясно? Можно увеличить множитель до 1000, только не перестарайся, макс. число допустимое как параметр для Random должно быть 65535 ...
Altair
Vardes, итоговую программу, выложи пожалуйста здесь. Спасибо. (думаю как метериал для FAQ использовать )
Vardes
А почему тогда одно и то же значение он по 100 раз просматривает.
И ещё вопрос,идёт генерация точек,анализируется например 2 пересекаемые окружности,тогда точки попавшие в область пересечения окружностей будут
суммироваться относительно первой и второй,или только относительно одной из них(в которую они попадут первыми).Что предусматривает метод Монте-Карло?
volvo
To: Vardes
Ты ответы мои ВНИМАТЕЛЬНО читал? Я кому это все пишу?
Цитата(Пост №10)
Как только точка попала в какую-то окружность, вся дальнейшая работа с этой точкой прекращается, ведь она УЖЕ внутри фигуры, и ты переходишь к следующей точке...


Цитата
А почему тогда одно и то же значение он по 100 раз просматривает.

Это ты к чему? КАКОЕ значение "он" (кстати, кто это ОН?) просматривает по 100 раз. Можно более четко выражать свои мысли?
Vardes
Код

write(point_x:3:3, ', ', point_y:3:3);

Если приостановить процесс,то увидишь,что значения сгенерированных точек повторяются.Это как объяснить?
volvo
Ну, во-первых, они СЛУЧАЙНЫЕ, то есть могут и повторяться. А во вторых - посмотри лог работы программы, генерирующей 1000 точек (так, как я показал в посте №36). Что-то я не вижу тут явных повторений nea.gif
Vardes
Вот программа,но почему-то слишком долго она генерирует точки,и большая очень погрешность(если взять только одну окружность).
volvo
To: Vardes
Я устал уже писать одно и то же. Ты не хочешь замечать того, что я делаю? Это нужно не мне, а тебе прежде всего !!! Какой точности ты хочешь добиться, если у тебя точки генерируются с точностью до целых? Сколько раз я должен писАть, КАК генерировать точки с точностью до сотых? Больше не буду повторять. Да и 50000 точек маловато. У меня после небольшого исправления твоей программы полмиллиона точек отработало за 4 секунды и дало для одной окружности радиусом 6 результат 113.091
Это первое.

А второе - ты сначала отладь сам алгоритм, а уж увеличением быстродействия займешься потом. А его можно ОЧЕНЬ сильно ускорить:
1) выносишь из цикла то, что можно вынести (в цикле постояноо вычисляется одно и то же)
2) тип с Real меняешь на Double - быстродействие РЕЗКО увеличивается (причины - смотри в FAQ-е)
Vardes
Ну у меня совсем небольшой опыт по программированию,чтобы легко отрабатывать алгоритм.
А говорить о том,что я невнимательно читаю ваши посты не надо,как генерировать точки с точностью до сотых,я понял.До этого проблема у меня была в том,что если генерировать около 200 тыс. точек,то приходиться ждать около 20 сек.,и результат ещё отрицательный получается.
volvo
Цитата
и результат ещё отрицательный получается.

А чтобы не было отрицательного результата, объяви переменную Sum не как Integer, а как LongInt... В Integer нельзя хранить числа больше 32767, и у тебя просто происходит переполнение, число "уходит" в минус... LongInt может хранить числа больше 2 миллиардов...
Vardes
Ошибку в своём алгоритме я так найти и не могу,а то,что в нём есть ошибка-это точно,делал генерацию в полмиллиона,получил совсем др. значение площади окружности радиуса 6. mega_chok.gif
volvo
Смотри, есть такое предложение: если у тебя не выходит с методом Монте-Карло, сделай почти Монте-Карло rolleyes.gif Просто перебирай с маленьким шагом все точки, лежащие внутри прямоугольника, и проверяй, какие из них попадают внутрь фигуры:
{
добавляешь эти описания:
}
const
divider = 500;
delta = 1/ divider;
var
sum, none: longint;
{
... и все остальные
}

begin
{
Здесь - все, что касается нахождения minx, miny, maxx, maxy,
как и было раньше... А вот дальше:
}
sum:=0; none := 0;
tm_s:= MemL[$0040:$006c]; { контроль времени - начали отсчет }

point_x := minx;
while point_x <= maxx do begin

point_y := miny;
while point_y <= maxy do begin

i := 1; found := False;
While (i <= n) and not found do begin
If Sqrt(sqr(point_x-x[i])+sqr(point_y-y[i]))<=mas[i] then found:=true
else inc(i);
end;
if found then sum:=sum+1 else none := none+1;

point_y := point_y + delta;
end;

point_x := point_x + delta;
end;

tm_f:= MemL[$0040:$006c]; { отсчет окончен }
tm_f:=tm_f - tm_s; { замеряем время }

writeln('time: ', tm_f);
writeln('Внутри: ', sum, ' снаружи: ', none);
S2:=S1*(sum/(sum+none));
writeln('Площадь фигуры = ',S2:2:2);
end.

Программа полностью: Нажмите для просмотра прикрепленного файла

Это уже будет работать быстрее алгоритма со случайными числами, т.к. "тяжелая" операция генерации чисел просто отсутствует, и заменена на гораздо более простую - перебор в цикле.

Но и это еще не предел... Как я уже писал выше, оптимизируем программу.
1) заменяем Real на Double
2) вместо того, чтобы в цикле выполнять Sqrt, можно ДО цикла возвести все mas[i] в квадрат, и потом сравнивать квадраты
3) целочисленные X := X + 1 заменяем на Inc(X). Вот что имеем:

  sum:=0; none := 0;
tm_s:= MemL[$0040:$006c]; { контроль времени }

for i := 1 to n do
mas[i] := sqr(mas[i]);

point_x := minx;
while point_x <= maxx do begin

point_y := miny;
while point_y <= maxy do begin

i := 1; found := False;
While (i <= n) and not found do begin
If (sqr(point_x-x[i])+sqr(point_y-y[i])) <= mas[i] then found:=true
else inc(i);
end;
if found then inc(sum) else inc(none);

point_y := point_y + delta;
end;

point_x := point_x + delta;
end;

tm_f:= MemL[$0040:$006c];
tm_f:=tm_f - tm_s;


Программа полностью: Нажмите для просмотра прикрепленного файла

Вторая программа выполняется быстрее первой почти в 25 раз !!!
Vardes
Значит если я понимаю правильно,то мы сгенерированным точкам присваиваем min значения,а потом используя
Код
     
point_y := point_y + delta;
point_x := point_x + delta

постепеннот доходим до max и на этом у нас циклы заканчиваются. good.gif
А старый метод Монте-Карло уже никак нельзя изменить?
volvo
Послушай, Vardes...
Тебе не нравится, что Метод Монте-Карло (МК) работает МЕДЛЕННО, как я тебе его ускорю? А он ведь именно со случайными данными работает, так что придется Random использовать. Кроме того, ты не знаешь, сколько точек перебирается в моей последней программе? Я тебе скажу, больше 35 миллионов (для окружности радиусом 6), попробуй это число поставить в программку по методу MK, сколько часов ты будешь ждать? А если тебе нужно еще точнее, то замени Divider на 1000, и получишь более 140 миллионов точек... Будешь сравнивать время выполнения?

Так что ты для себя реши, тебе нужен ИМЕННО метод Монте-Карло, или БЫСТРОЕ решение. А смешивать их не надо, не получится...
Vardes
Нет,что ВЫ,мне нравятся оба метода,второй даже больше,т.к я его хорошо понял.
И ещё я хотел сказать,что после общения с вами я узнал столько много нового,что просто вам очень сильно благодарен, give_rose.gif т.к сам по себе я ещё чайник в программировании.

*Наверно рекорд у вас поставил по кол-ву сообщений*
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.