Есть ли какой-либо алгоритм для вычисления области формы, данной координаты, которые определяют форму?
Таким образом, у меня есть некоторая функция, которая получает N случайный 2D точки.
Там какой-либо алгоритм должен вычислить область формы, определенной точками ввода?
4 ответа
Вы хотите вычислить площадь многоугольника ?
(Взято из ссылки, преобразовано в C #)
class Point { double x, y; }
double PolygonArea(Point[] polygon)
{
int i,j;
double area = 0;
for (i=0; i < polygon.Length; i++) {
j = (i + 1) % polygon.Length;
area += polygon[i].x * polygon[j].y;
area -= polygon[i].y * polygon[j].x;
}
area /= 2;
return (area < 0 ? -area : area);
}
Определение «области» вашей коллекции очков может быть трудным, например если вы хотите получить наименьшую область с прямыми границами, которые охватывают ваш набор, я не уверен, что делать дальше. Вероятно, вы хотите вычислить площадь выпуклой оболочки вашего набора точек; это стандартная проблема, описание проблемы со ссылками на реализации решений дано Стивеном Скиеной в хранилище алгоритмов Stony Brook . Отсюда один из способов вычисления площади (мне кажется очевидным) - это триангуляция области и вычисление площади каждого отдельного треугольника.
Ваша задача напрямую не подразумевает наличие готового многоугольника (что предполагается этим ответом). Я бы рекомендовал использовать триангуляцию, например триангуляцию Делоне, а затем тривиально вычислить площадь каждого треугольника. OpenCV (я использовал его с большим количеством 2D точек и он очень эффективен) и CGAL обеспечивают отличную реализацию для определения триангуляции.
Вы можете использовать алгоритм Тимоти Чана для поиска выпуклой оболочки в nlogh, где n - количество точек, h - количество вершин выпуклой оболочки. Если вам нужен простой алгоритм, воспользуйтесь сканированием Грэма.
Кроме того, если вы знаете, что ваши данные упорядочены как простая цепочка, где точки не пересекаются друг с другом, вы можете использовать алгоритм Мелкмана для вычисления выпуклой оболочки за O (N).
Еще одним интересным свойством выпуклой оболочки является то, что она имеет минимальный периметр.