Площадь пересечения двух фигур

[Marsel737]

Всем доброго времени суток.

Задача такая: найти площадь пересечения двух фигур, первая фигура - это Циссоида_Диокла, а вторая это прямоугольник.

Я сделал программу, в которой могу рисовать эти фигуры и по разному их располагать, чтобы были разные случаи пересечения.

Собственно вопрос, правильный ли я написал алгоритм для такого случая:



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

procedure TfrmMain.GetSquare;
var
  I, J: integer;
  CurLength: integer;
  IsCross: boolean;
begin
  VSquare := 0;
  CurLength := 0;
  IsCross := false;
  for J := y1 to y2 do
  begin
    VSquare := VSquare + CurLength;
    CurLength := 0;
    IsCross := false;
    for I := x1 to x2 do
    begin
      Inc(CurLength);
      if imgCanvas.Canvas.Pixels[I, J] = clRed then
      begin
        Crossing := true;
        IsCross := true;
        Break;
      end;
    end;
    if IsCross = false then
    begin
      CurLength := 0;
    end;
  end;
  if Crossing = false then
    VSquare := 0;
  edtSquare.Text := IntToStr(VSquare);
end;

И как найти площадь для такого случая:



UPD:

От препода слышал мельком мол наверно придётся использовать библиотеку GDI(хотя может я его не так понял, но уточнить смогу только через полторы недели) или высчитывать вручную, поэтому вопрос можно ли для этой задачи использовать такую библиотеку?

[InternetStranger]

Хм... Не уверен, что правильно понял вопрос.
Библиотеками, скорее всего пользоваться не придется, площадь подсчитать можно и с помощью метода Монте-Карло. Он настолько простой в реализации и понимании, что просто ппц.

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

[Marsel737]

InternetStranger, не подскажеш как можно метод Монте-Карло применить для моей задачи? Хотя бы для первого примера

[InternetStranger]

Вкратце тебе нужно математически записать условие принадлежности данной точки (X,Y) заданной области (площадь которой вычисляем). Затем производим N "бросков" точки со случайными координатами (равномерно-распределенные координаты). И подсчитываем удачные броски, т.е. сколько раз было попадание в заштрихованную область.

//--- Функция подсчитывает площадь фигуры ( 0<x<1; 0<y<1 y<x - это треугольник ) методом Монте-Карло. Возвращает площадь фигуры.
//--- Параметры: Chart - это Чарт, в который выводят точки;   Nbroskov - Кол-во бросков по методу Монте-Карло;   Paint - выводить точки?

function  AreaMMK( Chart: TChart; Nbroskov: Integer; Paint: Boolean ) : Real;
var
   i       : Integer;
   x,y,eps : Real;
   Popadanie : Boolean;
begin
      //-- Набрасывание точек
      Randomize;                   // Обнуляем Датчик случайных чисел
      Result:=0;                      // Обнуляем кол-во попаданий в искомую область
      for i:=1 to Nbroskov do begin   // Повторяем цикл Nbroskov раз
          x:= RANDOM;   // Случайная координата от 0 до 1
          y:= RANDOM;   // Случайная координата от 0 до 1

          Popadanie := (x >= 0) and (x <= 1) and (y >= 0) and (y <= x);  // Выясняем, попала ли точка с искомую область?
          if Popadanie then Result := Result + 1;     // Если точка попала в искомую область, то увеличиваем "Кол-во удачных попаданий" на единицу

          //-- Рисуем точки (наиболее наглядно)
          if Paint then begin
             if Popadanie then Chart.Series[1].AddXY( x, y )       // Точки ВНЕ области рисуем в 1-ю серию (Красные точки)
             else              Chart.Series[0].AddXY( x, y );  	// Точки В области рисуем в 0-ю серию (Синие точки)
          end;
      end;

      //-- Вычисление площади
      Result := Result / Nbroskov;
end;


procedure TForm1.Button1Click(Sender: TObject);
var
   i, N, Nris       : Integer;
   Area, eps      : Real;
begin
     Chart1.Series[0].Clear; // Очистка диаграммы точек
     Chart1.Series[1].Clear;
     Chart2.Series[0].Clear; // Очистка графика погрешности


     Nris  :=  StrToInt( Edit1.Text );        		// Число точек бросания, при котором выводить точки на диаграмму
     N := 10;
     for i:=1 to 6 do begin
         //-- Вычисляем площадь и погрешность
         N:= N*10;                            		// Кол-во точек
         Area := AreaMMK( Chart1, N, Nris=N );        // Вычисляем площадь по методу Монте-Карло при заданном кол-ве точек N
         eps  := Abs( 0.5 - Area );            		// Вычисляем абс.погрешность (Площадь треугольная д/б равна 0.5)

         //-- Выводим результат
         SG.Cells[0,i]:= IntToStr ( N );                    	     // Выводим Число бросков N  (в таблицу - SG)
         SG.Cells[1,i]:= IntToStr ( Round( N*Area ) );      // Выводим Число удачных попаданий в заданную область (в таблицу - SG)
         SG.Cells[2,i]:= FloatToStr ( Area );              	     // Выводим значение площади  (в таблицу - SG)
         SG.Cells[3,i]:= FloatToStrF( eps, fffixed, 2,6 );   // Выводим значение погрешности (в таблицу - SG)
         Chart2.Series[0].AddXY( N, eps );                      // Выводим значение погрешности (на график - Chart2)
     end;
end;


procedure TForm1.FormCreate(Sender: TObject);
begin
     SG.Cells[0,0]:= 'Число бросков, N';
     SG.Cells[1,0]:= 'Число попаданий';
     SG.Cells[2,0]:= 'Площадь';
     SG.Cells[3,0]:= 'Погрешность';
end;

end.

Отношение числа удачных бросков к общему числу бросков - есть относительная частота появления события, и при больших N стремится к вероятности этого события. В случае равномерно-распределенных случ. величин вероятность совпадает с площадью соответствующей фигуры )
В данном случае подсчитывается площадь прямоугольного треугольника (синие точки - попавшие в заданную область).

Монте-Карло.jpg

[Marsel737]

Ого, подробный ответ. Спс за подсказку, буду разбираться