Форум: "Потрепаться";
Текущий архив: 2002.06.03;
Скачать: [xml.tar.bz2];
ВнизЧуть более сложно Найти похожие ветки
← →
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 метода, ну и еще один, вероятностный.
методы собственно следуют из условий существования триангуляции этого самого дяди Делоне
>Институт Гэллапа, что ли, представляешь?
Если бы!!! :)
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2002.06.03;
Скачать: [xml.tar.bz2];
Память: 0.5 MB
Время: 0.006 c