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

Отредактировано whird (2008-06-30 12:15:06)

а не проще ли ЗК считать по крайним точкам . провести через них прямые а внутренние точки в расчет не брать

Ето не выпуклый многоугольник!!!
Точка (1,1), лежит внутри многоугольника (0,0);(2,0);(2,2);(0,2)!!!

Если для ЗК то нуна вычислять какие точки лежат внутри и выкидать из ращота!!!
Есть два варианта:
1. Вычислять ненужные точки!
2. Вычислять площадь ломаного треугольника, ну тогда зк будет меньше!
Жду ответ

Предлагаеш придумать алгоритм который будет откидать лишние точки е делать многоугольник  выпуклым?
Если можеш, напиши код который уже используется, может что то придумаю упростить!

Да винду переустановил и бока с сеткой и нетом были, раза 4 писал сообшение и бред написал!

НУ тогда заколонил свою систему всю и ЗК должна увеличится? Каким макаром?
ЗК должна зависеть от расположения поселения, а не от количества!

Отредактировано whitenight (2008-07-01 11:26:56)

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

нашли n_j точек образующих выпуклую фигуру.
далее разделяем ее на треугольники:

от одной точки проводим прямые y=k x +b
где к = (y1-y2)(x1-x2), сортируем по к точки (акуратно работаем с делением на ноль, там может получится + и - бесконечность, можно ручками исправить)
начинаем строить треугольники
1 - выбраная точка + 1 и 2 с минимальным к
2 - выбраная точка + 2 и 3
....
j-2 выбраная точка + j-2 и j-1

сумируем пложади треугольников

это будет площадь фигуры

Отредактировано vvv (2008-07-02 19:49:18)

Формула для вычисления площади сложной фигуры по координатам точек выглядит следующим образом:
S=0.5[(X2Y1-X1Y2) + (X3Y2-X2Y3) + (X4Y3-X3Y4) +.....+ (X{n}Y{n-1}-X{n-1}Y{n}) + (X1Yn-XnY1)

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

вроде бы и не сложно

Я выместил архив по адресу http://rapidshare.com/files/127093284/alg.7z   В архиве Borland C 3.1 и исходник программы. Можешь поэксперементировать с программой и проверить точность вычислений. Алгоритм работает для любого количества точек более 2. Остается только перевести на нужный язык и пользоваться. Если непонятно по программе как алгоритм работает отпишись и я представлю алгоритм в более понятной форме.

1: S=4.000000
2: S=4.000000
3: S=4.000000

Скачай архив с прогой и протести для более сложных значений и для большего числа точек

напишу код:

функции:

In({x1,y1, ... xn,yn}, X,Y) // выдает true/false на принадлежность точки X Y  многоугольнику x1,y1, ... xn,yn. в {} передаются его координаты, чтоб было понятнее

задан некоторый многоурольник (x1,y1, ... xn,yn), n - число вершин, его координаты задать в массив
X[i]
Y[i]

//находим выпклый многоугольник

flag=true
until flag do{

for i=1 to n do
{
for j=1 to n do {
clear[X1,Y1];
If i!=j then {X1[j]=X[j];Y1[j]=Y[j];}}; // X1 Y1 - координаты многоугольника без 1 точки

if In({X1,Y1}, X[i],Y[i]) then {X=X1;Y=Y1; n=n-1;  break;// ушли из for начали заново};
                                  else {if i==n then flag=false};
}//for
}//until

//фукция нахождения коэффицента к от 2 точек

find_k(x1,y1,x2,y2):=
{
if x1==x2 then k=(y1-y2)*10000000 //чтоб избежать бесконечности
else к = (y1-y2)/(x1-x2)
}

//строим линии
for i=1 to n-1 do
{
k[i]=find_k(X[1],Y[1],X[i+1],Y[i+1]) 
}

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

for i=1 to n-1 do
{
for j=i+1 to n-1 do
{
if k[j]>k[i] then //меняем точки местами, равенство быть не должно
{temp=X[i+1]; X[i+1]=X[j+1];X[j+1]=temp;temp=Y[i+1]; Y[i+1]=Y[j+1];Y[j+1]=temp;temp=k[i]; k[i]=k[j];k[j]=temp;}
}
}

//теперь треугольники
F_3( x1 y1 x2 y2 x3 y3) //нахождение площади треугольника, было выше. не прописываю

S=0;
for i=1 to n-2 do
{
S=S+F_3(X[1],Y[1], X[i+1],Y[i+1],  X[i+2],Y[i+2]);
}

ps. синтаксис не проверял, по памяти

Отредактировано vvv (2008-07-05 23:13:15)