Определить процедуру вычисления площади треугольника по координатам его вершин

@Hamelion))) · Регистрация: 16.11.2010

Author24 — интернет-сервис помощи студентам

Даны натуральное число n, действительные числа x1, y1, x2, y2,…, xn,yn. Найти площадь
n-угольника,вершины которого при некотором последовательном обходе имеют координаты (x1, y1), (x2, y2),…, (xn, yn). (Определить процедуру вычисления площади треугольника по координатам его вершин.)

@Deviaphan · 23.03.2011, 11:06

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

@Alex1234 · 23.03.2011, 11:21

Не простая задача. http://www.opita.net/node/12

@Deviaphan · 23.03.2011, 11:29

Возможность триангуляции плоского многоугольника математически доказана и, соответственно, реализуема.

Если не издеваться, то:
Разбить произвольный многоугольник на множество выпуклых многоугольников. О минимизации количества выпуклых многоугольников ведь речи нет, так что задача простая.
Разбить каждый выпуклый многоугольник на треугольники (веером).
Считать площади.
Сложить.

@Mayonez · 23.03.2011, 16:44

C++

#include <iostream>
#include <vector>
 
using namespace std;
 
float sq (vector <pair <int, int> > &dil)
{
    float res = 0;                  
    for (unsigned i = 0; i < dil.size(); i++)
    {
       pair <int, int> one, two;     
        one = i ? dil[i-1] : dil.back();
        two = dil[i];               
        res += (one.first - two.first) * (one.second + two.second)                      
    }
    return fabs (res) / 2;            
}
 
int main()
{
   vector <pair <int, int> > dil;     
   int N;                 
   cin >> N;                       
   while (N)
   {
      int x, y;
      cin >> x >> y;
      dil.push_back(make_pair(x, y)); 
      N--;
   }
    cout << sq(dil) << endl;
   return 0;
}

@Alex1234 · 23.03.2011, 18:11

Сообщение от Deviaphan

Возможность триангуляции плоского многоугольника математически доказана и, соответственно, реализуема.
Разбить произвольный многоугольник на множество выпуклых многоугольников. О минимизации количества выпуклых многоугольников ведь речи нет, так что задача простая.
Разбить каждый выпуклый многоугольник на треугольники (веером).
Считать площади.
Сложить.

Это кому как, мне на эту тему даже думать показалось сложно.

@Deviaphan · 23.03.2011, 18:19

Mayonez, я не вчитывался, но похоже, что только для выпуклых многоугольников метод работает.

@Ma3a · 23.03.2011, 18:21

Если многоугольник простой, то вполне можно воспользоваться формулой, приведенной здесь: Площадь простого n-угольника Жаль, что про эту формулу почти везде уже забыли.

@Deviaphan · 23.03.2011, 18:23

А если многоугольник - квадрат, то...

@Ma3a · 23.03.2011, 18:38

То значит, что квадрат - тоже простой многоугольник, а значит формула работает. Или вы о чём-то ином?

@Deviaphan · 23.03.2011, 18:41

О сложности вычисления площади квадрата...

@Ma3a · 23.03.2011, 18:42

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

@Mayonez · 23.03.2011, 18:42

Deviaphan, для невыпуклых тоже за счет отрицательной площади

@Deviaphan · 23.03.2011, 18:46

Круто! Не знал.) Сохраню алгоритмик, на всякий пожарный.)

@Mayonez · 23.03.2011, 18:48

главное - без самопересечений т.е. простой. Порядок обхода тоже неважен

@Ma3a · 23.03.2011, 18:49

Deviaphan, кстати, поглядел код Mayonez, как раз этот метод, о котором я говорил,ведь и используется

@Mayonez · 23.03.2011, 18:51

Сообщение от Deviaphan

Возможность триангуляции плоского многоугольника математически доказана и, соответственно, реализуема.

Не нужно делать триангуляцию.
Выбираем любую точку.
Переберем все ребра, прибавляя ориентированную площадь треугольника - получаем ответ

Добавлено через 57 секунд
Ma3a, да, именно

@Deviaphan · 23.03.2011, 18:51

Я уже алгоритм себе скопировал, прозапас.
Но триангулировать веселее.) И муторнее.

@Mayonez 392 / 284 / 53 Регистрация: 26.12.2009 Сообщений: 874
	23.03.2011, 18:42	13
	Deviaphan, для невыпуклых тоже за счет отрицательной площади 1

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	23.03.2011, 18:46	14
	Круто! Не знал.) Сохраню алгоритмик, на всякий пожарный.) 0

@Mayonez 392 / 284 / 53 Регистрация: 26.12.2009 Сообщений: 874
	23.03.2011, 18:48	15
	главное - без самопересечений т.е. простой. Порядок обхода тоже неважен 0

@Mayonez 392 / 284 / 53 Регистрация: 26.12.2009 Сообщений: 874
	23.03.2011, 18:51	17
	Сообщение от Deviaphan Возможность триангуляции плоского многоугольника математически доказана и, соответственно, реализуема. Не нужно делать триангуляцию. Выбираем любую точку. Переберем все ребра, прибавляя ориентированную площадь треугольника - получаем ответ Добавлено через 57 секунд Ma3a, да, именно 0

@Hamelion))) 2 / 2 / 0 Регистрация: 16.11.2010 Сообщений: 24
		1
	Определить процедуру вычисления площади треугольника по координатам его вершин 23.03.2011, 11:01. Показов 7531. Ответов 17 Метки нет (Все метки) Даны натуральное число n, действительные числа x1, y1, x2, y2,…, xn,yn. Найти площадь n-угольника,вершины которого при некотором последовательном обходе имеют координаты (x1, y1), (x2, y2),…, (xn, yn). (Определить процедуру вычисления площади треугольника по координатам его вершин.) 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	23.03.2011, 11:06	2
	Решение содержится в постановке задачи: Разбиваешь многоугольник на треугольники, считаешь их площади и суммируешь. (Вычисление площади треугольника выносишь в функцию.) 0

@Alex1234 13 / 13 / 2 Регистрация: 11.02.2011 Сообщений: 55
	23.03.2011, 11:21	3
	Не простая задача. http://www.opita.net/node/12 1

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	23.03.2011, 11:29	4
	Возможность триангуляции плоского многоугольника математически доказана и, соответственно, реализуема. Если не издеваться, то: Разбить произвольный многоугольник на множество выпуклых многоугольников. О минимизации количества выпуклых многоугольников ведь речи нет, так что задача простая. Разбить каждый выпуклый многоугольник на треугольники (веером). Считать площади. Сложить. 0

@Alex1234 13 / 13 / 2 Регистрация: 11.02.2011 Сообщений: 55
	23.03.2011, 18:11	6
	Сообщение от Deviaphan Возможность триангуляции плоского многоугольника математически доказана и, соответственно, реализуема. Разбить произвольный многоугольник на множество выпуклых многоугольников. О минимизации количества выпуклых многоугольников ведь речи нет, так что задача простая. Разбить каждый выпуклый многоугольник на треугольники (веером). Считать площади. Сложить. Это кому как, мне на эту тему даже думать показалось сложно. 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	23.03.2011, 18:19	7
	Mayonez, я не вчитывался, но похоже, что только для выпуклых многоугольников метод работает. 0

@Ma3a 623 / 467 / 57 Регистрация: 28.01.2011 Сообщений: 605
	23.03.2011, 18:21	8
	Если многоугольник простой, то вполне можно воспользоваться формулой, приведенной здесь: Площадь простого n-угольника Жаль, что про эту формулу почти везде уже забыли. 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	23.03.2011, 18:23	9
	А если многоугольник - квадрат, то... 0

@Ma3a 623 / 467 / 57 Регистрация: 28.01.2011 Сообщений: 605
	23.03.2011, 18:38	10
	То значит, что квадрат - тоже простой многоугольник, а значит формула работает. Или вы о чём-то ином? 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	23.03.2011, 18:41	11
	О сложности вычисления площади квадрата... 0

Опции темы

@Ma3a 623 / 467 / 57 Регистрация: 28.01.2011 Сообщений: 605
	23.03.2011, 18:49	16
	Deviaphan, кстати, поглядел код Mayonez, как раз этот метод, о котором я говорил,ведь и используется 0