1

我正在制作一个小应用程序来分析几何。在我的程序的一部分中，我使用了一种算法，该算法必须有一个凸对象作为输入。幸运的是，我所有的对象最初都是凸的，但有些几乎没有（见图）。

在我应用一些转换之后，我的算法无法工作（它会产生“无限”长多边形等），我认为这是因为图像中的舍入错误；由于舍入误差（图像非常夸张），圆柱体中的顶部顶点被略微“推入”并且不再凸出。

变形前后的圆柱体

所以我的问题是：有谁知道“稍微凸化”一个物体的方法？这是我尝试实现的一种方法，但它似乎不起作用（或者我实现错误）：

1. Average all vertices together to create a vertex C inside the convex shape.
2. Let d[v] be the distance from C to vertex v.
3. Scale each vertex v from the center C with the scale factor 1 / (1+d[v] * CONVEXIFICATION_FACTOR)

谢谢！！我已经安装了 CGAL 和 Boost，所以我可以使用任何这些库函数（我已经这样做了）。

4

2 回答 2

3

您当然可以通过计算对象的凸包来使对象凸出。但这会“突出”任何事情。如果您确定您的输入仅略微偏离凸面，那么这应该不是问题。

CGAL 中似乎有一个 3D Quickhull 的实现，这将是第一个尝试的东西。有关文档和一些示例程序，请参见http://doc.cgal.org/latest/Convex_hull_3/ 。（我对 CGAL 不够熟悉，无法重现任何示例并声称它们是正确的。）

于 2015-05-29T14:23:36.740 回答
1

最后我发现这个问题的根源在于凸包包含很多三角形，而我的输入形状通常是立方体形状，使得每个四边形区域看起来像两个三角形，它们具有极其相似的平面方程，导致某种我正在使用的算法中的问题。

我使用这段代码通过“去三角化”多面体来解决它。如果有人能发现任何改进或问题，请告诉我！

#include <algorithm>
#include <cmath>
#include <vector>

#include <CGAL/convex_hull_traits_3.h>
#include <CGAL/convex_hull_3.h>

typedef Kernel::Point_3              Point;
typedef Kernel::Vector_3             Vector;
typedef Kernel::Aff_transformation_3 Transformation;
typedef CGAL::Polyhedron_3<Kernel>   Polyhedron;

struct Plane_from_facet {
  Polyhedron::Plane_3 operator()(Polyhedron::Facet& f) {
      Polyhedron::Halfedge_handle h = f.halfedge();
      return Polyhedron::Plane_3(h->vertex()->point(),
                                 h->next()->vertex()->point(),
                                 h->opposite()->vertex()->point());
  }
};

inline static double planeDistance(Plane &p, Plane &q) {
    double sc1 = max(abs(p.a()),
                 max(abs(p.b()),
                 max(abs(p.c()),
                     abs(p.d()))));
    double sc2 = max(abs(q.a()),
                 max(abs(q.b()),
                 max(abs(q.c()),
                     abs(q.d()))));
    Plane r(p.a() * sc2,
            p.b() * sc2,
            p.c() * sc2,
            p.d() * sc2);
    Plane s(q.a() * sc1,
            q.b() * sc1,
            q.c() * sc1,
            q.d() * sc1);
    return ((r.a() - s.a()) * (r.a() - s.a()) +
            (r.b() - s.b()) * (r.b() - s.b()) +
            (r.c() - s.c()) * (r.c() - s.c()) +
            (r.d() - s.d()) * (r.d() - s.d())) / (sc1 * sc2);
}

static void detriangulatePolyhedron(Polyhedron &poly) {
    vector<Polyhedron::Halfedge_handle> toJoin;
    for (auto edge = poly.edges_begin(); edge != poly.edges_end(); edge++) {
        auto f1 = edge->facet();
        auto f2 = edge->opposite()->facet();
        if (planeDistance(f1->plane(), f2->plane()) < 1E-5) {
            toJoin.push_back(edge);
        }
    }
    for (auto edge = toJoin.begin(); edge != toJoin.end(); edge++) {
        poly.join_facet(*edge);
    }
}

 ...

                    Polyhedron convexHull;

                    CGAL::convex_hull_3(shape.begin(),
                                        shape.end(),
                                        convexHull);

                    transform(convexHull.facets_begin(),
                              convexHull.facets_end(),
                              convexHull.planes_begin(),
                              Plane_from_facet());

                    detriangulatePolyhedron(convexHull);

                    Plane bounds[convexHull.size_of_facets()];
                    int boundCount = 0;

                    for (auto facet = convexHull.facets_begin(); facet != convexHull.facets_end(); facet++) {
                        bounds[boundCount++] = facet->plane();
                    }
...

这给出了预期的结果（之后和之前）：

在那之后

于 2015-06-03T00:44:07.717 回答