Чуть более сложно

← →
Lord Warlock (2002-04-22 14:17) [0]

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

← →
Виктор Щербаков (2002-04-22 14:25) [1]

Угу. И еще чтоб многоугольник самопересекающийся был.
Основная проблема здесь - разбить многоугольник на несамопересекающиеся многоугольники. Дальше площадь можно искать по стандартным формулам.

← →
Lord Warlock (2002-04-22 14:28) [2]

Виктор Щербаков ©:
на самом деле все не так сложно, и самопересекающийся многоугольник или нет, не важно

← →
Виктор Щербаков (2002-04-22 14:29) [3]

> самопересекающийся многоугольник или нет, не важно

???

← →
Lord Warlock (2002-04-22 14:33) [4]

Виктор Щербаков © нет

← →
Виктор Щербаков (2002-04-22 15:12) [5]

Выпуклый или нет - действительно не важно. Есть общая формула.
С исключениями тоже вроде просто. Их площадь можно брать со знаком минус.
Но я всё-таки не пойму почему не важно, самопересекающийся многоугольник или нет?
Если считать площадь по формуле
S = 1/2 * sum((X[i] + X[i+1]) * (Y[i] - Y[i+1])),
то результат будет неверный!

← →
Alx2 (2002-04-22 15:21) [6]

>Lord Warlock © (22.04.02 14:17)
Клейн: "Элементарная математика с точки зрения высшей". II-й том.
Выбираем направление обхода и суммируем "плоскостные элементы" 1/6*det(M), где M - матрица, в строках которой координаты предыдущей и текущей точек.

← →
Alx2 (2002-04-22 15:24) [7]

Сорри, 1/2*det(M) :)

← →
Виктор Щербаков (2002-04-22 15:27) [8]

Alx2 © (22.04.02 15:24)
По-моему совпадает с формулой в Виктор Щербаков © (22.04.02 15:12). Но я же говорю, это не верно для самопересекающихся :(

← →
MBo (2002-04-22 15:32) [9]

>Alx2
это как раз, то, что Виктор написал.
для невыпуклого подходит, а для самопересек. нет ;(

← →
Alx2 (2002-04-22 15:39) [10]

Сорри, ребята!
Где мои глаза :)

Для самопересекающегося тоже катит. Типа, обобщенная площадь, которая может быть и отрицательной.

← →
MBo (2002-04-22 16:03) [11]

вот пример
заложен квадрат.
если заменить x[3] на 2, получим самопересек., и площадь будет 0
procedure TForm1.Button1Click(Sender: TObject);
var x,y:array[0..3] of double;
i:integer;
s:double;
begin
s:=0;
x[0]:=0;y[0]:=0;
x[1]:=1;y[1]:=0;
x[2]:=1;y[2]:=1;
x[3]:=0;y[3]:=1;
//*******
//x[3]:=2;y[3]:=1;

for i:=0 to 3 do
// это напрямую детерминант
// s:=s+x[i]*y[(i+1) mod 4] - y[i]*x[(i+1)mod 4];
//исключено 1 умножение
s:=s+(x[i]+x[(i+1) mod 4])*(y[(i+1) mod 4]-y[i]);
s:=s/2;
label1.caption:=floattostr(s);
end;

← →
PVOzerski (2002-04-22 16:16) [12]

А я вот каким методом "решал": рисовал фигуру по координатам Polygon"ом заданного
цвета на "чистом белом" Bitmap"е, а потом считал число точек данного цвета.

← →
MBo (2002-04-22 16:18) [13]

>PVOzerski
ну тогда и Монте-Карло можно ;)

← →
Alx2 (2002-04-22 16:23) [14]

>MBo © (22.04.02 16:03)
После самопересечения меняется направление обхода. Площади кусков компенсируют друг друга.

← →
MBo (2002-04-22 16:27) [15]

а как учесть? ;(((

← →
Alx2 (2002-04-22 16:30) [16]

Так она на самом деле нулю равна. Или как надо понимать площадь самопересекающегося многоугольника?

← →
MBo (2002-04-22 16:34) [17]

Как количество краски на ее покрытие >PVOzerski

← →
Alx2 (2002-04-22 16:38) [18]

Тогда это не самопересекающийся многоугольник. А "обычный" ;) С дополнительной точкой.

← →
handra (2002-04-22 17:18) [19]

Монте-Карло + ф-я определения принадлежности точки к полигону (есть реализация)

← →
Alx2 (2002-04-22 17:23) [20]

Проще (экономичнее по ресурсам) "развести" самопересекающиеся.

← →
Виктор Щербаков (2002-04-23 10:12) [21]

> Тогда это не самопересекающийся многоугольник. А "обычный"
> ;) С дополнительной точкой.

Во! Наконец-то!
А теперь собственно проблема:
Найти эти точки самопересечения (ну это вроде просто) и вставить между нужными точками исходного многоугольника.
В общем случае это не тривиально. Стоит взять бумагу, карандаш и попробовть нарисовть несколько таких "фигур"...
Т.е. задача всё равно сводится к разбиению на несамопересекающиеся.
Если кто нибудь сможет предложить работающий общий алгоритм, буду весьма благодарен. Меня этот вопрос давно мучает.

← →
Run (2002-04-23 11:27) [22]

I>
> Lord Warlock © (22.04.02 14:17)
> Найти плоощадь какого-нибудь многоугольника любой формы
> (а не только выпуклой), и возможно с исключениями внутри
> (т.е. могут быть "пустые" области произвольной конфигурации)

можно нарисовать ентот многоугольник и посчитать пиксели :=))))<

← →
Lord Warlock (2002-04-25 09:32) [23]

to Run: Насчет пикселей, тяжело и долго все это, и неуниверсально, тем более, чему у тебя будет равняться площадь 1 пикселя, интересно, и как получишь нормальную площадь в метрах

to Всем остальным: Слышали когда нибудь про метод Делоне?

← →
MBo (2002-04-25 12:11) [24]

>Lord Warlock
>про метод Делоне
триангуляцию имеешь в виду?

← →
Lord Warlock (2002-04-25 14:15) [25]

to MBo: Ее родимую и имею в виду, вообще-то она не предназначена для расчета площадей, но можно использовать и так, причем результат будет точнее любого из методов приближения.

← →
Lord Warlock (2002-04-25 14:17) [26]

А теперь самое интересное, сколько по Вашему мнению существует методов реализации триангуляции, в чем их отличие?

← →
MBo (2002-04-25 14:28) [27]

>по Вашему мнению
Институт Гэллапа, что ли, представляешь?

поиск по triangulation voronoi delanauy пробовал?
не видел пока реализации на Паскале трианг. с оптимизацией, чтобы не было маленьких углов треугольников.

← →
Lord Warlock (2002-04-26 09:17) [28]

to MBo ©:m я пока тоже не видел, все делал сам, применял 2 метода, ну и еще один, вероятностный.

методы собственно следуют из условий существования триангуляции этого самого дяди Делоне

>Институт Гэллапа, что ли, представляешь?
Если бы!!! :)

Чуть более сложно Найти похожие ветки