Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Площадь фигуры,образованная окружностями.

Автор: Vardes 11.11.2005 1:03

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

Вот рисунок:

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




Эскизы прикрепленных изображений
Прикрепленное изображение

Автор: klem4 11.11.2005 2:42

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


А можешь показать где такое есть на твоем рисунке ? Я например не вижу пересечения левой окружности и правой или верхней с нижней ... да и вообще помойму данных маловато для решения...

Автор: volvo 11.11.2005 2:45

To: klem4
А кто тебе сказал "площадь, образованную пересечением всех окружностей"? Найти нужно:

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

Автор: klem4 11.11.2005 2:49

Так точно, теперь вижу ... прошу прощения за невнимателность.

Автор: Vardes 11.11.2005 3:51

Ну вот в принципе площадь чего надо найти:


Эскизы прикрепленных изображений
Прикрепленное изображение

Автор: volvo 11.11.2005 21:56

По-моему, классическая задача для метода Монте-Карло... cool.gif

Автор: Vardes 12.11.2005 1:04

А можно как-то этот метод Монте-Карло пояснить?

Автор: volvo 12.11.2005 1:18

Можно... Допустим, у тебя есть прямоугольник, в который полностью помещается твоя фигура, и ты точно знаешь его площадь. Тогда ты генерируешь большое количество случайных точек (чем больше точек - тем точнее результат), точно находящихся внутри прямоугольника, и проверяешь, сколько из них попадают в твою фигуру (зная координаты центров всех окружностей и их радиусы, несложно вычислить, попадает ли заданная точка в фигуру)...

Естественно, что чем больше точек попадут внутрь твоей фигуры, тем ее площадь больше yes2.gif А саму площадь вычисляешь так:

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


(бери число испытаний в районе 500 тыс - 1 млн, и в течении 5-7 секунд получай ответ...)

Автор: Vardes 12.11.2005 2:23

Тогда у меня возникают такие вопросы,как же мне задать мой прямоугольник,ведь количество лучей у меня не ограничено,и может доходить до 10,15 и т.д.
И ещё,бывет так,что окружности накладывается др. на др.,следовательно точка попадёт и в ту и в др. окружность.

Автор: volvo 12.11.2005 2:42

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

Вот тебе пример (по твоему же рисунку), как выбрать прямоугольник...


Эскизы прикрепленных изображений
Прикрепленное изображение

Автор: Vardes 12.11.2005 4:20

Тогда получается,что мне надо вводить оси координат,если речь уже заходит о координатах,а как я могу их воодить,если все точки имеют положительное значение.

Автор: volvo 12.11.2005 4:52

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

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

Кстати, программа, вычисляющая площадь твоей фигуры (вместе с графическим представлением) занимает меньше 150 строк... blum.gif

Автор: Vardes 12.11.2005 22:29

Ну вот введу я систему координат,мне необходимо чтобы все лучи выходили из одной точки(это ладно),но и углы между лучами должны быть равными.И ещё,мой препод будет вводить только радиусы этих окружностей(2,3,4 и т.д) и всё,а не координаты центров окружностей.
И генерировать числа я пока тоже не умею,т.к. опыта у меня немного.Ещё пробовал решать эту задачу через центральный угол,найдя его можно пощитать площадь кругового сектора.Рассчитав площадди всех секторов,можно найти площадь и всей фигуры.Вот.
Но тут есть загвоздка,дело в том,что если окружностей много,то происходит большое количество наложений,чуть ли одна не вписывается в др.,поэтому условия все предусмотреть очень сложно. mega_chok.gif

Автор: volvo 12.11.2005 22:40

To: Vardes
Полярную систему координат еще никто не отменял rolleyes.gif Там как раз очень просто реализовать то, что ВСЕ лучи выходят их одной точки (r = 0), и углы между лучами равны: (Phi изменяется с шагом 360 div n, где n - количество лучей)...

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

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

Кстати, для генерации случайного числа X в интервале -100 .. 100 достаточно сделать

X := Random(201) - 100;

Автор: Vardes 13.11.2005 0:12

Значит я так понимаю,что радиусы окружности и лучи можно задать таким образом.Где L-это полярная ось,P-центр окружности,и углы.
Вот рисунок:


Эскизы прикрепленных изображений
Прикрепленное изображение

Автор: Vardes 13.11.2005 0:16

А декартовы координаты тогда можно будет выразить так:x=p*cos угла 360/n;
y=p*sin угла 360/n.

Автор: volvo 13.11.2005 0:22

yes2.gif Правильно понимаешь... Еще какие-то затруднения?

Автор: Vardes 13.11.2005 0:53

Да,необходимо определить принадлежит ли точка к плоскости какой-то из наших окружностей,чтобы её нам запомнить и разделить потом на общее количество таких точек.
Ещё хотел по-больше узнать о генерации случайного числа x и y:нам надо брать те границы чисел,которыми у нас ограничен прямоугольник.НАпример он у нас ограничен следущими координатами 4 точекsad.gif6,0);(-5,0);(0,4);(0,-7),как тогда нам сгенерировать числа по x и y.

Автор: Vardes 13.11.2005 1:13

Цитата
Да,необходимо определить принадлежит ли точка к плоскости какой-то из наших окружностей,чтобы её нам запомнить и разделить потом на общее количество таких точек.

Есть такая идея проверять ту или иную точку,образует ли она радиус вписанной окружности в нашу(конечно же,центр у них должен быть одинаковым)если образует,то мы её запоминаем.


Эскизы прикрепленных изображений
Прикрепленное изображение

Автор: volvo 13.11.2005 1:26

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 13.11.2005 1:42

Блин,точно...
Просто у меня уже голова кипит от этой задачи,но цель уже поставлена,поэтому и пытаюсь всякими извращёнными способами достигнуть её.НУ всё же остаётся поставленный вопрос про генерирование точки в посте №18.

Автор: volvo 13.11.2005 2:23

Значит, у тебя прямоугольник ограничен -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 13.11.2005 16:46

Вот реализация части програмного кода,до нахождения 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 13.11.2005 16:52

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

Автор: Vardes 13.11.2005 18:16

Правилен ли будет код для генерации случайных точек и их проверки(ссылаясь на код выше),так как у меня идёт зацикливание.

Код

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 13.11.2005 19:26

point_x:=random(round(maxx-minx+1))+minx;
point_y:=random(round(maxy-miny+1))+miny;

Автор: Vardes 13.11.2005 20:09

Всё исправил,но всё равно идёт зацикливание. не пойму в чём дело.

Код
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 13.11.2005 20:10

Данные, которые вводишь, приведи... И объясни, что значит "зацикливание"...

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

While (i <= n) and (not found) do begin


Кстати, а с каким именно X и Y ты производишь операции? Ты их сохранил куда-то (в массив), когда преобразовал из полярной СК? Я у тебя в коде этого не увидел... Более того, у тебя даже массива для этого не описано...

Автор: Vardes 13.11.2005 20:27

Провожу такой ввод данных:
n- кол-во окружностей и ввожу радиус окружности,переводя его в массив
mas[1..n].Вот и все данные.
Проблема в том,что постоянно работает цикл while как взял i=1,так постоянно и гоняет себя не переходя на др. значения i.Переделал и всё равно гоняет.

Автор: volvo 13.11.2005 20:38

Я тебе уже написал почему... Вот НЕзацикливающийся вариант. Я не проверял все формулы, если там все правильно, то тебе осталось только зациклить генерацию точки, сделать это несколько сот тысяч раз (не меньше 200000-250000, лучше - несколько миллионов), посчитать количество попаданий, и вычислить площадь (как - см. пост №8)...


Прикрепленные файлы
Прикрепленный файл  __circle.pas ( 1.22 килобайт ) Кол-во скачиваний: 353

Автор: Vardes 13.11.2005 21:17

значит генерация происходит по одной точке,если я правильно понимаю.Как же тогда можно генерировать несколько тысяч раз,если у нас промежуток по x[-4:5],а по у [-3;9].Принцип не могу понять.

Автор: volvo 13.11.2005 21:20

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 13.11.2005 21:45

так это всё понятно,я про принцип спрашивал,откуда берётся такое большое кол-во точек,если у нас промежуток маленький.

Автор: volvo 13.11.2005 21:58

To: Vardes
А тебе все равно, какой у тебя промежуток. Если у тебя прямоугольник (граничные точки) размером 5*5, а сама фигура - размером 3*3, я что, не могу сгенерировать 5 миллионов точек, КАЖДАЯ из которых будет находиться в прямоугольнике? И проверить, сколько попадет в фигуру? Пускай из них будет по полмиллиона точек повторяться, это НЕ твоя проблема. Это и есть Monte-Carlo (Метод Рулетки)

Автор: Vardes 13.11.2005 22:12

Ну ведь каждая сгенерированная точка имеет свои координаты,для вещественного типа их можно сколько угодно сгенерировать,а если у нас генерирование идёт целых чисел, да и промежуток небольшой,то как тогда поступать.

Автор: volvo 13.11.2005 22:27

Ну, так генерируй с точностью до сотых:

  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 13.11.2005 22:29

Vardes, итоговую программу, выложи пожалуйста здесь. Спасибо. (думаю как метериал для FAQ использовать )

Автор: Vardes 13.11.2005 22:54

А почему тогда одно и то же значение он по 100 раз просматривает.
И ещё вопрос,идёт генерация точек,анализируется например 2 пересекаемые окружности,тогда точки попавшие в область пересечения окружностей будут
суммироваться относительно первой и второй,или только относительно одной из них(в которую они попадут первыми).Что предусматривает метод Монте-Карло?

Автор: volvo 13.11.2005 22:58

To: Vardes
Ты ответы мои ВНИМАТЕЛЬНО читал? Я кому это все пишу?

Цитата(Пост №10)
Как только точка попала в какую-то окружность, вся дальнейшая работа с этой точкой прекращается, ведь она УЖЕ внутри фигуры, и ты переходишь к следующей точке...


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

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

Автор: Vardes 13.11.2005 23:06

Код

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

Если приостановить процесс,то увидишь,что значения сгенерированных точек повторяются.Это как объяснить?

Автор: volvo 13.11.2005 23:34

Ну, во-первых, они СЛУЧАЙНЫЕ, то есть могут и повторяться. А во вторых - посмотри лог работы программы, генерирующей 1000 точек (так, как я показал в посте №36). Что-то я не вижу тут явных повторений nea.gif


Прикрепленные файлы
Прикрепленный файл  results.txt ( 15.38 килобайт ) Кол-во скачиваний: 267

Автор: Vardes 14.11.2005 0:17

Вот программа,но почему-то слишком долго она генерирует точки,и большая очень погрешность(если взять только одну окружность).


Прикрепленные файлы
Прикрепленный файл  _______.PAS ( 1.41 килобайт ) Кол-во скачиваний: 292

Автор: volvo 14.11.2005 0:58

To: Vardes
Я устал уже писать одно и то же. Ты не хочешь замечать того, что я делаю? Это нужно не мне, а тебе прежде всего !!! Какой точности ты хочешь добиться, если у тебя точки генерируются с точностью до целых? Сколько раз я должен писАть, КАК генерировать точки с точностью до сотых? Больше не буду повторять. Да и 50000 точек маловато. У меня после небольшого исправления твоей программы полмиллиона точек отработало за 4 секунды и дало для одной окружности радиусом 6 результат 113.091
Это первое.

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

Автор: Vardes 14.11.2005 1:15

Ну у меня совсем небольшой опыт по программированию,чтобы легко отрабатывать алгоритм.
А говорить о том,что я невнимательно читаю ваши посты не надо,как генерировать точки с точностью до сотых,я понял.До этого проблема у меня была в том,что если генерировать около 200 тыс. точек,то приходиться ждать около 20 сек.,и результат ещё отрицательный получается.

Автор: volvo 14.11.2005 2:31

Цитата
и результат ещё отрицательный получается.

А чтобы не было отрицательного результата, объяви переменную Sum не как Integer, а как LongInt... В Integer нельзя хранить числа больше 32767, и у тебя просто происходит переполнение, число "уходит" в минус... LongInt может хранить числа больше 2 миллиардов...

Автор: Vardes 14.11.2005 3:24

Ошибку в своём алгоритме я так найти и не могу,а то,что в нём есть ошибка-это точно,делал генерацию в полмиллиона,получил совсем др. значение площади окружности радиуса 6. mega_chok.gif

Автор: volvo 14.11.2005 15:42

Смотри, есть такое предложение: если у тебя не выходит с методом Монте-Карло, сделай почти Монте-Карло 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.

Программа полностью: Прикрепленный файл  __VARD_1.PAS ( 1.61 килобайт ) Кол-во скачиваний: 562


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

Но и это еще не предел... Как я уже писал выше, оптимизируем программу.
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;


Программа полностью: Прикрепленный файл  __VARD_2.PAS ( 1.66 килобайт ) Кол-во скачиваний: 590


Вторая программа выполняется быстрее первой почти в 25 раз !!!

Автор: Vardes 14.11.2005 16:33

Значит если я понимаю правильно,то мы сгенерированным точкам присваиваем min значения,а потом используя

Код
     
point_y := point_y + delta;
point_x := point_x + delta

постепеннот доходим до max и на этом у нас циклы заканчиваются. good.gif
А старый метод Монте-Карло уже никак нельзя изменить?

Автор: volvo 14.11.2005 17:55

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

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

Автор: Vardes 14.11.2005 18:32

Нет,что ВЫ,мне нравятся оба метода,второй даже больше,т.к я его хорошо понял.
И ещё я хотел сказать,что после общения с вами я узнал столько много нового,что просто вам очень сильно благодарен, give_rose.gif т.к сам по себе я ещё чайник в программировании.

*Наверно рекорд у вас поставил по кол-ву сообщений*