Boost :: Geometry — Найти область 2-го многоугольника в 3D-пространстве?
Я пытаюсь получить область 2-го многоугольника в 3D-пространстве. Есть ли способ сделать это с помощью Boost :: Geometry? Вот моя реализация, но она все время возвращает 0:
#include <iostream>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/io/wkt/wkt.hpp>
namespace bg = boost::geometry;
typedef bg::model::point<double, 3, bg::cs::cartesian> point3d;
int main()
{
bg::model::multi_point<point3d> square;
bg::read_wkt("MULTIPOINT((0 0 0), (0 2 0), (0 2 2), (0 0 2), (0 0 0))", square);
double area = bg::area(square);
std::cout << "Area: " << area << std::endl;
return 0;
}
UPDНа самом деле, у меня та же проблема с простым 2d многоточечным квадратом:
#include <iostream>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/io/wkt/wkt.hpp>
namespace bg = boost::geometry;
typedef bg::model::point<double, 2, bg::cs::cartesian> point2d;
int main()
{
bg::model::multi_point<point2d> square;
bg::read_wkt("MULTIPOINT((0 0), (2 0), (2 2), (0 2))", square);
double area = bg::area(square);
std::cout << "Area: " << area << std::endl;
return 0;
}
Вот результат:
$ ./test_area
Area: 0
UPD: Похоже на вычисление площади в boost::geometry Доступно только для двухмерных полигонов.
Решение
Я не ожидал бы, что у коллекции пунктов будет область. Вам понадобится эквивалент model::polygon<poind3d> но это, кажется, не поддерживается в настоящее время.
Если точки гарантированно копланарны, а отрезки не пересекаются друг с другом, вы можете разложить многоугольники как серии треугольников и вычислить площадь с помощью немного линейной алгебры, основываясь на следующей формуле для области треугольника:
В случае невыпуклых многоугольников сумму площадей необходимо адаптировать для вычитания площадей вне многоугольника. Самый простой способ добиться этого — использовать подписанные области для треугольников, в том числе положительные вклады от правых треугольников и отрицательные вклады от левых треугольников:
Обратите внимание, что, похоже, есть некоторые планы по включению cross_product реализация в Boost, но она не включена в версию 1.56. Следующая замена должна помочь вашему варианту использования:
point3d cross_product(const point3d& p1, const point3d& p2)
{
double x = bg::get<0>(p1);
double y = bg::get<1>(p1);
double z = bg::get<2>(p1);
double u = bg::get<0>(p2);
double v = bg::get<1>(p2);
double w = bg::get<2>(p2);
return point3d(y*w-z*v, z*u-x*w, x*v-y*u);
}
point3d cross_product(const bg::model::segment<point3d>& p1
, const bg::model::segment<point3d>& p2)
{
point3d v1(p1.second);
point3d v2(p2.second);
bg::subtract_point(v1, p1.first);
bg::subtract_point(v2, p2.first);
return cross_product(v1, v2);
}
Затем можно вычислить площадь с помощью чего-либо, например:
// compute the are of a collection of 3D points interpreted as a 3D polygon
// Note that there are no checks as to whether or not the points are
// indeed co-planar.
double area(bg::model::multi_point<point3d>& polygon)
{
if (polygon.size()<3) return 0;
bg::model::segment<point3d> v1(polygon[1], polygon[0]);
bg::model::segment<point3d> v2(polygon[2], polygon[0]);
// Compute the cross product for the first pair of points, to handle
// shapes that are not convex.
point3d n1 = cross_product(v1, v2);
double normSquared = bg::dot_product(n1, n1);
if (normSquared > 0)
{
bg::multiply_value(n1, 1.0/sqrt(normSquared));
}
// sum signed areas of triangles
double result = 0.0;
for (size_t i=1; i<polygon.size(); ++i)
{
bg::model::segment<point3d> v1(polygon[0], polygon[i-1]);
bg::model::segment<point3d> v2(polygon[0], polygon[i]);
result += bg::dot_product(cross_product(v1, v2), n1);
}
result *= 0.5;
return abs(result);
}
Другие решения
Я не знаком с разделом геометрии наддува, но с моими знаниями геометрии я могу сказать, что в 3D он не будет сильно отличаться от 2D. Хотя уже может быть что-то повышенное, вы можете написать свой собственный метод, который делает это довольно легко.
РЕДАКТИРОВАТЬ:
да код обезьяны указал, что формула шнурка будет более эффективным в этом смысле, потому что это менее сложно и быстрее.
Оригинальная идея ниже:
Чтобы вычислить это, я сначала рассортирую многоугольник на треугольники, потому что любой многоугольник может быть разбит на несколько треугольников. Я бы взял каждый из этих треугольников и вычислил площадь каждого из них. Для этого в трехмерном пространстве применяются те же понятия. Чтобы получить базу, вы берете △ ABC и произвольно назначаете -AB в качестве базы, -BC в качестве высоты и -CA в качестве гипотенузы. Просто сделайте (-AB * -BC) / 2. Просто сложите области каждого треугольника.
Я не знаю, есть ли в boost встроенный метод tessellate, и это будет довольно сложно реализовать в c ++, но вы, вероятно, захотите создать какой-нибудь треугольник веера. (ПРИМЕЧАНИЕ: это относится только к выпуклым полигонам). Если у вас есть вогнутый многоугольник, вы должны посмотреть на это: http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html Я оставлю это в качестве упражнения, но этот процесс довольно прост.