2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 площадь выпуклого многоугольника
Сообщение22.10.2013, 10:58 
Аватара пользователя
Имеется массив точек на плоскости, заданный своими координатами $(x_i,y_i)$. Необходимо найти площадь выпуклого многоугольника, который покрывает все эти точки (Вершинами многоугольника являются данные точки. Часть точек может не являться вершинами, а лежать внутри многоугольника.).

Я реализовал алгоритм, решающий данную задачу, следующим образом (опуская подробности алгоритма): нашел точки - вершины многоугольника и триангулировал.
Поиск точек-вершин не очень сложный, но несколько более громоздкий, чем хотелось бы.
Отсюда вопрос: можно ли сразу посчитать, например, площади всех возможных треугольников и из них получить площадь многоугольника, учтя каким-то образом (каким?) перекрытие этих треугольников?

 
 
 
 Re: площадь выпуклого многоугольника
Сообщение22.10.2013, 11:13 
В Maple насколько помню есть команда выпуклая оболочка точек, в качестве результата дает некий минимальный набор точек из исходных
А у почти всех команд можно посмотреть код

 
 
 
 Re: площадь выпуклого многоугольника
Сообщение22.10.2013, 11:24 
Аватара пользователя
У меня сейчас нет возможности посмотреть содержимое команд коммерческого софта, да и с установкой free софта несколько проблемно.

 
 
 
 Re: площадь выпуклого многоугольника
Сообщение22.10.2013, 11:24 
Известны алгоритмы нахождения выпуклой оболочки, имеющие сложность $O(n\log h)$, где $n$ - общее число точек, а $h$ - число точек в выпуклой оболочке. Далее площадь ищется за $O(h)$. Если же считать площадь всех треугольников, это уже $O(n^3)$. Кроме того, триангулировать вовсе не обязательно, есть же известная формула для площади многоугольника.

 
 
 
 Re: площадь выпуклого многоугольника
Сообщение22.10.2013, 11:42 
Аватара пользователя
За алгоритм вычисления площади без триангуляции спасибо, а вот площадь через площади всех треугольников меня всё равно интересует - не взирая на сложность алгоритма

 
 
 
 Re: площадь выпуклого многоугольника
Сообщение22.10.2013, 16:27 
Аватара пользователя
photon в сообщении #778451 писал(а):
У меня сейчас нет возможности посмотреть содержимое команд коммерческого софта, да и с установкой free софта несколько проблемно.

Площадь выпуклой оболочки — довольно стандартная задача олимпиадного программирования. Если вам надо, то я могу вам быстро написать exe-шник, который по .txt файлу с координатами точек выводит площадь выпуклой оболочки.

 
 
 
 Re: площадь выпуклого многоугольника
Сообщение22.10.2013, 17:06 
Аватара пользователя
Urnwestek в сообщении #778605 писал(а):
Площадь выпуклой оболочки — довольно стандартная задача олимпиадного программирования. Если вам надо, то я могу вам быстро написать exe-шник, который по .txt файлу с координатами точек выводит площадь выпуклой оболочки.


Да я уже написал, и оно работает. Мне просто интересно, можно ли реализовать не через поиск вершин, а в лоб, через площади фигур.

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group