Задача на нахождение площади, площадь произвольного многоугольника Опции

[Иван]

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

[volvo]

Определить, находится ли произвольно выбранная на плоскости точка внутри твоего многоугольника, сможешь? Тогда ищи на форуме про "Метод Монте-Карло"...

[Гость]

Не могу. В этом и заключается одна из основных проблем.

[volvo]

Не думаю, что ЭТО является неразрешимой проблемой: В сети есть достаточно алгоритмов, проверяющих принадлежность точки многоугольнику... Вот тут, например: Determining if a point lies on the interior of a polygon

Ну а это - реализация первого алгоритма на Паскале:

function min(a, b: double): double;
begin
  min := a;
  if b < a then min := b;
end;

function max(a, b: double): double;
begin
  max := a;
  if b > a then max := b;
end;

type
  point = record
    x, y: double;
  end;


function InsidePolygon(var polygon: array of point;
         const n: integer; p: point): boolean;
var
  i, counter: integer;
  xinters: double;
  p1, p2: point;
begin
  counter := 0;

  p1 := polygon[0];
  for i := 1 to n do begin
    p2 := polygon[i mod n];
    if p.y > min(p1.y, p2.y) then begin

      if p.y <= max(p1.y, p2.y) then begin
        if p.x <= max(p1.x, p2.x) then begin
          if p1.y <> p2.y then begin
            xinters := (p.y - p1.y)*(p2.x - p1.x) / (p2.y-p1.y) + p1.x;
            if (p1.x = p2.x) or (p.x <= xinters) then inc(counter);
          end;
        end;
      end;

    end;
    p1 := p2;
  end;

  if (counter mod 2) = 0 then InsidePolygon := false
  else InsidePolygon := true;
end;

Проверено для невыпуклого многоугольника... У меня работает.