Площадь невыпуклого многоугольника
Здравствуйте, подскажите алгоритм для на хождения площади невыпуклого многоугольника. Его нужно дробить на треугольники или можно проще?
Aswed ★★★★★
10.12.12 12:38:13 MSK
Пользоваться поисковиками уже не модно?
trex6 ★★★★★
( 10.12.12 12:50:21 MSK )
Ответ на: комментарий от trex6 10.12.12 12:50:21 MSK
Пример из статьи не работает. Для многоугольника (1,0) (0,1) (1,2) (2,1) (1,1) выдает 4.5 вместо 1.5
Aswed ★★★★★
( 10.12.12 20:58:23 MSK ) автор топика
Обходишь его по кругу по направленым векторам — его сторонам. Суммируешь площади трапеций со знаком, у которых основы — перпендикуляры на какую-то ось, одна боковая сторона часть этой оси, а вторая сам вектор. Знак площади нужно брать в зависимости от того точка в какую сторону направлена проекция вектора на выбраную ось
vertexua ★★★★★
( 10.12.12 21:02:27 MSK )
Теорема Гаусса-Остроградского в помощь. Уже не помню, какой там это курс матана.
yvv ★★☆
( 10.12.12 21:18:20 MSK )
Ответ на: комментарий от vertexua 10.12.12 21:02:27 MSK
Можете написать пример реализации?
Aswed ★★★★★
( 10.12.12 21:23:20 MSK ) автор топика
Ответ на: комментарий от Aswed 10.12.12 21:23:20 MSK
Скиньте входные данные чтобы я проверил. Вершины в порядке обхода
vertexua ★★★★★
( 10.12.12 21:24:18 MSK )
Последнее исправление: vertexua 10.12.12 21:24:39 MSK (всего исправлений: 1)
Ответ на: комментарий от yvv 10.12.12 21:18:20 MSK
Пардон, для площади фигуры формула Стокса нужна. Всё время их путаю.
yvv ★★☆
( 10.12.12 21:25:01 MSK )
Ответ на: комментарий от vertexua 10.12.12 21:02:27 MSK
А трапеции то зачем? Можно просто считать площади треугольников, образованных стороной и вектором из нач. координат к началу стороны. Площадь треугольника брать как посл. элемент векторного произведения, со знаком ес-но.
AIv ★★★★★
( 10.12.12 21:25:04 MSK )
Последнее исправление: AIv 10.12.12 21:25:24 MSK (всего исправлений: 1)
Ответ на: комментарий от AIv 10.12.12 21:25:04 MSK
Ну там формула проста, мне как то не приходит в голову формула в этом случае для треугольника удобная
vertexua ★★★★★
( 10.12.12 21:27:27 MSK )
Ответ на: комментарий от vertexua 10.12.12 21:24:18 MSK
ну например (1,0) (0,1) (1,2) (2,1) (1,1)
Aswed ★★★★★
( 10.12.12 21:31:19 MSK ) автор топика
Ответ на: комментарий от vertexua 10.12.12 21:27:27 MSK
Что может быть проще векторного произведения? x1*y2-x2*y1
AIv ★★★★★
( 10.12.12 21:35:47 MSK )
Ответ на: комментарий от AIv 10.12.12 21:35:47 MSK
Ну да, логично, вылетело с головы
vertexua ★★★★★
( 10.12.12 21:44:45 MSK )
Ответ на: комментарий от vertexua 10.12.12 21:27:27 MSK
только там пополам ес-но, векторное произведение дает площадь параллелограмма
L = [(1,0), (0,1), (1,2), (2,1), (1,1)] .5*abs(sum([ a[0]*(b[1]-a[1])-a[1]*(b[0]-a[0]) for a, b in zip(L, L[-1:]+L[:-1]) ])) AIv ★★★★★
( 10.12.12 21:46:11 MSK )
Ответ на: комментарий от AIv 10.12.12 21:46:11 MSK
Aswed ★★★★★
( 10.12.12 22:11:37 MSK ) автор топика
Ответ на: комментарий от AIv 10.12.12 21:46:11 MSK
def area(points:List[Point]) = 0.5*abs((points.last::points).sliding(2).foldLeft(0.0) acc + pair(0).x*pair(1).y - pair(1).x*pair(0).y >)
vertexua ★★★★★
( 10.12.12 22:58:59 MSK )
Ответ на: комментарий от vertexua 10.12.12 22:58:59 MSK
Aswed ★★★★★
( 11.12.12 00:01:15 MSK ) автор топика
Ответ на: комментарий от yvv 10.12.12 21:25:01 MSK
Пардон, для площади фигуры формула Стокса нужна. Всё время их путаю.
два чая этому господину.
dikiy ★★☆☆☆
( 11.12.12 00:59:48 MSK )
Ответ на: комментарий от vertexua 10.12.12 22:58:59 MSK
Это хаскель что ли? У меня было 1.5
AIv ★★★★★
( 11.12.12 12:14:48 MSK )
Ответ на: комментарий от AIv 11.12.12 12:14:48 MSK
vertexua ★★★★★
( 11.12.12 12:24:17 MSK )
Ответ на: комментарий от AIv 11.12.12 12:14:48 MSK
s l = 0.5 * sum $ zipWith (\(a0,a1) (b0,b1) -> a0*(b1-a1)-a1*(b0-a0)) l (last l:l) qnikst ★★★★★
( 11.12.12 12:36:53 MSK )
Ответ на: комментарий от qnikst 11.12.12 12:36:53 MSK
s/0\.5 \*/(0.5 *) ./exlevan
( 11.12.12 18:47:00 MSK )
Ответ на: комментарий от exlevan 11.12.12 18:47:00 MSK
Prelude> let s l = 0.5 * sum $ zipWith (\(a0,a1) (b0,b1) -> a0*(b1-a1)-a1*(b0-a0)) l (last l:l) Prelude> let s l = (0. 5 *) . sum $ zipWith (\(a0,a1) (b0,b1) -> a0*(b1-a1)-a1*(b0-a0)) l (last l:l) :4:5: Could not deduce (Num (a -> b0)) arising from the ambiguity check for `s' да и в point-free оно убодо не переписывается
qnikst ★★★★★
( 11.12.12 19:03:42 MSK )
Ответ на: комментарий от qnikst 11.12.12 19:03:42 MSK
Я разве советовал поставить пробел в середине числа?
Оригинальная s неприменима к списку пар чисел из-за приоритета ($): сначала вычислится (0.5 * sum), где sum — не число:
Prelude> let s l = 0.5 * sum $ zipWith (\(a0,a1) (b0,b1) -> a0*(b1-a1)-a1*(b0-a0)) l (last l:l) Prelude> s [(1,0), (0,1), (1,2), (2,1), (1,1)] :29:1: No instance for (Fractional ([a0] -> a0)) arising from a use of `s' Possible fix: add an instance declaration for (Fractional ([a0] -> a0)) In the expression: s [(1, 0), (0, 1), (1, 2), (2, 1), . ] In an equation for `it': it = s [(1, 0), (0, 1), (1, 2), . ]Поэтому нужны скобки или композиция:
Prelude> let s l = (0.5 *) . sum $ zipWith (\(a0,a1) (b0,b1) -> a0*(b1-a1)-a1*(b0-a0)) l (last l:l) Prelude> s [(1,0), (0,1), (1,2), (2,1), (1,1)] 1.5 Prelude> let s l = 0.5 * (sum $ zipWith (\(a0,a1) (b0,b1) -> a0*(b1-a1)-a1*(b0-a0)) l (last l:l)) Prelude> s [(1,0), (0,1), (1,2), (2,1), (1,1)] 1.5Основы программирования
Вычисление площади невыпуклого многоугольника
- Задачи
- Вычислительная геометрия
- C/CPP
Многоугольник (не обязательно выпуклый) задан на плоскости перечислением координат вершин в порядке обхода его границ. Определить площадь многоугольника.
Входные данные:
— Число вершин в многоугольнике
— Координаты вершин, заданные в порядке обхода его границы по часовой стрелке
Выходные данные:
— Площадь заданного многоугольника
#include #include #include #include int x[100]; int y[100]; // массив вершин многоугольника (не более 100 точек) int main() { clrscr(); int i, n; long s, res = 0, sq = 0; cout "Enter the number of vertices:" endl; cin >> n; cout "Enter coordinates:" endl; for (i = 0; i n; i++) { cin >> x[i]; // координата x cin >> y[i]; // координата y } int gd, gm; gd = DETECT; initgraph (&gd, &gm, "c:\\temp"); // построение на экране многоугольника for (i = 0; i n; i++) { circle (x[i] + 150, y[i] + 150, 2); if (i == n - 1) { i = 0; line (x[i] + 150, y[i] + 150, x[n-1] + 150, y[n-1] + 150); break; } line (x[i] + 150, y[i] + 150, x[i+1] + 150, y[i+1] + 150); } // Расчет площади многоугольника через сумму площадей трапеций for (i = 0; i n; i++) { if (i == 0) { s = x[i]*(y[n-1] - y[i+1]); //если i == 0, то y[i-1] заменяем на y[n-1] res += s; } else if (i == n-1) { s = x[i]*(y[i-1] - y[0]); // если i == n-1, то y[i+1] заменяем на y[0] res += s; } else { s = x[i]*(y[i-1] - y[i+1]); res += s; } } sq = abs(res/2); cout "-------------" endl; cout "Square:" endl; cout sq; getch(); return 0; }
Ключевые слова:
многоугольник, полигон, площадь, трапеция, вычисление площади
- Войдите или зарегистрируйтесь, чтобы комментировать
Как найти площадь невыпуклого многоугольника
Nickolay.info. Алгоритмы. Площади выпуклого и невыпуклого многоугольников
Дано натуральное число N и действительные числа i,Yi>, i=1,2. N , описывающие координаты вершин многоугольника на плоскости. Найти площадь выпуклого N-угольника, вершины которого при последовательном обходе имеют координаты 1,Y1>, . N,YN> .
Алгоритм сводится к разбиению многоугольника на треугольники с общей вершиной в точке 1,Y1> и последующим вычислением их площадей по форумле Герона.
Проверка того, действительно ли можно из введённых координат получить выпуклый многоугольник, не делается.
const nmax=10; var x,y:array [1..nmax] of real; n,i:integer; s,r1,r2,r3,p,p2:real; begin repeat write ('Число вершин (от 3 до ',nmax,'): '); read (n); if IoResult<>0 then continue; until (n>2) and (n<=nmax); for i:=1 to n do repeat write ('Координаты вершины ',i,': '); read (x[i],y[i]); until IoResult=0; s:=0; r1:=sqrt(sqr(x[1]-x[2])+sqr(y[1]-y[2])); for i:=3 to n do begin p:=r1; r2:=sqrt(sqr(x[i]-x[i-1])+sqr(y[i]-y[i-1])); p:=p+r2; r3:=sqrt(sqr(x[i]-x[1])+sqr(y[i]-y[1])); p:=p+r3; p2:=p/2; s:=s+sqrt(p2*(p2-r1)*(p2-r2)*(p2-r3)); r1:=r3; end; writeln ('Площадь ',n,'-угольника=',s:8:2); write ('Нажмите Enter для выхода'); reset (input); readln; end.
Можно всё упростить, вычисляя площади треугольников через координаты их вершин.
const nmax=10; var x,y:array [1..nmax] of real; n,i:integer; s:real; begin repeat write ('Число вершин (от 3 до ',nmax,'): '); read (n); if IoResult<>0 then continue; until (n>2) and (n<=nmax); for i:=1 to n do repeat write ('Координаты вершины ',i,': '); read (x[i],y[i]); until IoResult=0; s:=0; for i:=1 to n-2 do s:=s+1/2*abs((x[i+1]-x[1])*(y[i+2]-y[1])-(x[i+2]-x[1])*(y[i+1]-y[1])); writeln ('Площадь ',n,'-угольника=',s:8:2); write ('Нажмите Enter для выхода'); reset (input); readln; end.
Теперь рассмотрим случай невыпуклого многоугольника, для которого столь простые алгоритмы неприменимы.
Примем, что многоугольник находится в области Y>0 . Если это не так, его всегда можно переместить в положительную зону оси Y путём вычитания из всех координат Yi значения mini>=Ymin . Общая площадь многоугольника будет равна сумме площадей прямоугольных трапеций, боковыми сторонами которых являются ось X и отрезок прямой, проведённый через 2 соседние вершины в порядке обхода. При этом в общей сумме площадь очередной трапеции учитывается со знаком " + ", если значение Xi в последующей точке больше предыдущего в порядке обхода (наклонная штриховка на рисунке) или со знаком " - " в противном случае (вертикальная штриховка).
const nmax=10; var x,y:array [1..nmax] of real; n,i:integer; s,min:real; begin repeat write ('Число вершин (от 3 до ',nmax,'): '); read (n); if IoResult<>0 then continue; until (n>2) and (n<=nmax); for i:=1 to n do repeat write ('Координаты вершины ',i,': '); read (x[i],y[i]); until IoResult=0; min:=y[1]; for i:=2 to n do if y[i] writeln ('Площадь ',n,'-угольника=',s:8:2); write ('Нажмите Enter для выхода'); reset (input); readln; end.
Площадь невыпуклого многоугольника
Задача: Многоугольник (необязательно выпуклый) задан на плоскости перечислением координат вершин в порядке обхода его границы. Определить площадь многоугольника. Написал код для вычисления площади выпуклого многоугольника (да, с выделением памяти в куче). Как его можно переделать под вычисление площади невыпуклого многоугольника и вообще алгоритм определения: введенный многоугольник является выпуклым или нет? (Если без разбивания многоугольника на фигуры никак, то напишите, пожалуйста, как его разбить и вычислить каждую фигуру отдельно)
#include "stdafx.h" #include using namespace System; using namespace std; int main() < setlocale(0, ""); int y, x, c, i = 0; cout > c; int(*coor)[2]; coor = new int[c][2]; while (i != c) < for (int j = 0; j < 2; j++) < cout > x; cout > y; coor[i][j] = x; j = 1; coor[i][j] = y; j = 2; > i++; >; i = 0; int t = i + 1; double sum, pl = 0; for (i; t!= c; i++) < sum = ((coor[i][0] + coor[t][0])*(coor[i][1] - coor[t][1])) / 2; pl = pl + sum; t++; >cout
Так выглядит эта же прога без массивов. Здесь все работает верно. Видимо неправильно интегрировал сюда динамический массив. Помогите, пожалуйста
int n, x, y, x1, x2, y1, y2; double sum = 0; cout > n; cout > x >> y; x1 = x; y1 = y; for (int i = 0; i < (n - 1); i++) < cout > x2 >> y2; sum = sum + (x1 + x2)*(y2 - y1); x1 = x2; y1 = y2; > sum = sum + (x + x2)*(y - y2); sum = abs(sum) / 2; cout