logo标签列表

qhull库 - C++接口

c++convex-hullqhull
18

qhull库（qhull.org）在其网站中有几个示例可供使用，但与C ++相关的所有信息对我来说都不太有用。

我正在尝试制作一个简单的三维点的凸包，这些点是我从文件中读取的，我不能使用网站上建议的调用qhull.exe作为外部应用程序的技术，因为我需要对数据点进行一些修改以制作几个凸包。

我找不到一个简单的例子来做到这一点，有人能给我一些帮助吗？任何信息都将是有用的。

谢谢

我正在使用Windows。 - Nuno Pessanha Santos
2
哦，天啊，那个库太复杂了。我只想查找一堆用于计算凸包的函数，但是它就像俄语一样难懂。 - thang
4个回答
21

因为我自己使用c++和Qhull遇到了困难，并在网络上找不到任何有用的示例，所以在终于成功获得有效结果后，我将我的代码发布在这里供以后使用。

这个答案适用于Windows，使用Visual Studio 2012/3。我不知道它如何或是否适用于其他平台。

那么，首先，在从这里下载qhull源文件并在VS中打开项目后，唯一需要添加的文件是以下两个目录:

libqhull/
libqhullcpp/

在将这些文件添加到项目后，添加以下代码（这是我的方法，显然您可以使用自己的方式）：

Qhull.h

namespace orgQhull{
//...
private:
    PointCoordinates *m_externalPoints;
//...
public:
    void runQhull3D(const std::vector<vec3> &points, const char* args);
    void runQhull(const PointCoordinates &points, const char *qhullCommand2);
//...
}

Qhull.cpp

void Qhull::runQhull3D(const std::vector<vec3> &points, const char* args)
{
    m_externalPoints = new PointCoordinates(3);  //3 = dimension
    vector<double> allPoints;
    for each (vec3 p in points)
    {
        allPoints.push_back(p.x());
        allPoints.push_back(p.y());
        allPoints.push_back(p.z());
    }

    m_externalPoints->append(allPoints); //convert to vector<double>
    runQhull(*m_externalPoints, args);
}

void Qhull::runQhull(const PointCoordinates &points, const char *qhullCommand2)
{
    runQhull(points.comment().c_str(), points.dimension(), points.count(), &*points.coordinates(), qhullCommand2);
}

最后，这是如何使用代码：

//not sure all these includes are needed
#include "RboxPoints.h"
#include "QhullError.h"
#include "Qhull.h"
#include "QhullQh.h"
#include "QhullFacet.h"
#include "QhullFacetList.h"
#include "QhullLinkedList.h"
#include "QhullVertex.h"
#include "QhullSet.h"
#include "QhullVertexSet.h"
#include <vector>

int main()
{
    orgQhull::Qhull qhull;
    std::vector<vec3> vertices;
    qhull.runQhull3D(vertices, "Qt");

    QhullFacetList facets = qhull.facetList();
    for (QhullFacetList::iterator it = facets.begin(); it != facets.end(); ++it)
    {
        if (!(*it).isGood()) continue;
        QhullFacet f = *it;
        QhullVertexSet vSet = f.vertices();
        for (QhullVertexSet::iterator vIt = vSet.begin(); vIt != vSet.end(); ++vIt)
        {
            QhullVertex v = *vIt;
            QhullPoint p = v.point();
            double * coords = p.coordinates();
            vec3 aPoint = vec3(coords[0], coords[1], coords[2]);
            // ...Do what ever you want
        }
    }
    
    // Another way to iterate (c++11), and the way the get the normals
    std::vector<std::pair<vec3, double> > facetsNormals;
    for each (QhullFacet facet : qhull.facetList().toStdVector())
    {
        if (facet.hyperplane().isDefined())
        {
            auto coord = facet.hyperplane().coordinates();
            vec3 normal(coord[0], coord[1], coord[2]);
            double offset = facet.hyperplane().offset();
            facetsNormals.push_back(std::pair<vec3, double>(normal, offset));
        }
    }
}

注意，我从我的项目中复制了这段代码，并进行了一些修改，以使其更加信息丰富，但我没有编译此示例。

@Raaj，感谢您指出了这个问题。如果您愿意用一个线程安全的代码来编辑我的答案，我将会仔细检查它并接受它。 - ZivS
没有。我已经查遍了整个互联网/github/codeproject等所有资源，没有C/C++凸包/凹包算法的示例。 - Raaj
如果我没记错的话，qhull推出了这个新的可重入qhull，它是线程安全的。我还没有找到使用该代码的任何示例。 - Raaj
1
qhull 2015是可重入的，但不是线程安全的：请参见http://www.qhull.org/html/qh-code.htm#reentrant和http://www.qhull.org/html/qh-code.htm#cpp。 - Gnat
1
谢谢，这篇文章真的很有用。 - stephanmg
很好的回答！你知道为什么法线（在三维中）可能是(nan，nan，nan)吗？我猜这就是函数facet.hyperplane.isDefined()所指的吧？ - katherinejohnson
1

这篇文章里是我能找到的关于qHull的唯一示例，所以我想添加一段代码片段来展示如何使用qhull获取二维点集的凸包。

#include <vector>

#include "my_point.h"
#include "libqhullcpp/Qhull.h"
#include "libqhullcpp/QhullVertex.h"
#include "libqhullcpp/QhullVertexSet.h"
#include "libqhullcpp/QhullPoint.h"

std::vector<my_point> getConvexHull2D(const std::vector<my_point> &scatteredPoints)
{
  std::vector<my_point> cHull;
  if(scatteredPoints.size() < 3) return cHull;

  std::vector<double> inputVertices;
  for(int i = 0; i < (int)scatteredPoints.size(); i++)
  {
    const my_point &pt = scatteredPoints[i];
    inputVertices.push_back(pt.x);
    inputVertices.push_back(pt.y);
  }

  orgQhull::Qhull qhull;

  int ndim = 2;
  int num_points = inputVertices.size() / ndim;
  const char *inputComments = "";
  const char *qHullCommands = "";

  qhull.runQhull(inputComments, ndim, num_points, inputVertices.data(), qHullCommands);

  for(const orgQhull::QhullVertex &v: qhull.vertexList())
  {
    const orgQhull::QhullPoint &qhullPt = v.point();
    auto coords = qhullPt.coordinates(); // list of doubles
    cHull.push_back(my_point(coords[0], coords[1]));
  }

  // the vertices are not sorted?
  CCWSort(cHull.data(), cHull.size());
  return cHull;
}

我还需要构建库并链接qhullcpp.lib和qhullstatic_r.lib，同时将qhull/src添加到包含路径中。你可以打开一个Qt项目进行构建，这将为你构建库。
我最初尝试使用boost，但它与一些旧代码产生了太多冲突。这可能不是最有效的实现方式，但比我之前的做法要好得多。
1

这是一个使用可重入qhull的简单示例，使用c++编写。我认为它可能会有用。

#include <iostream>
#include <vector>
#include <string>

#include "Qhull.h"

int main(int argc, char const *argv[])
{

    std::vector<double> points_3D = {0, 0, 0,
                                     0, 1, 0,
                                     1, 1, 0,
                                     1, 0, 0,
                                     0, 0, 1,
                                     0, 1, 1,
                                     1, 1, 1,
                                     1, 0, 1};

    int ndim = 3;
    int num_points = points_3D.size() / ndim;

    std::string comment = ""; // rbox commands, see http://www.qhull.org/html/rbox.htm
    std::string qhull_command = ""; // For qhull commands, see http://www.qhull.org/html/qhull.htm

    try
    {
        orgQhull::Qhull qhull = orgQhull::Qhull(comment.c_str(), ndim, num_points, points_3D.data(), qhull_command.c_str());
        std::cout << "qhull.hullDimension(): " << qhull.hullDimension() << "\n";
        std::cout << "qhull.volume(): " << qhull.volume() << "\n";
        std::cout << "qhull.area(): " << qhull.area() << "\n";
    }
    catch (orgQhull::QhullError &e)
    {
        std::cerr << e.what() << std::endl;
        return e.errorCode();
    }
}
0
以下步骤在我的Ubuntu机器上帮助了我：
1. 如GitHub的自述文件中所述， - 下载并解压Qhull（可以是GitHub、.tgz文件或.zip文件） - 运行make命令 - 运行make install命令 - 运行make test命令
2. 示例代码qhull_vol.cpp对随机分布在半径为1的球上的点进行Delaunay三角剖分。它还检查几何形状是否为凸形。（以下示例中的部分内容来自互联网资源）
#include "libqhullcpp/RboxPoints.h"
#include "libqhullcpp/QhullError.h"
#include "libqhullcpp/Qhull.h"
#include "libqhullcpp/QhullQh.h"
#include "libqhullcpp/QhullFacet.h"
#include "libqhullcpp/QhullFacetList.h"
#include "libqhullcpp/QhullLinkedList.h"
#include "libqhullcpp/QhullVertex.h"
#include "libqhullcpp/QhullSet.h"
#include "libqhullcpp/QhullVertexSet.h"
#include <vector>
#include <cmath>
#include <random>
#include <libqhull/qhull_a.h>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

using orgQhull::Qhull;
using orgQhull::QhullError;
using orgQhull::QhullFacet;
using orgQhull::QhullFacetList;
using orgQhull::QhullFacetListIterator;
using orgQhull::QhullFacetSet;
using orgQhull::QhullPoint;
using orgQhull::QhullPoints;
using orgQhull::QhullPointsIterator;
using orgQhull::QhullQh;
using orgQhull::QhullVertex;
using orgQhull::QhullVertexList;
using orgQhull::QhullVertexListIterator;
using orgQhull::QhullVertexSet;
using orgQhull::QhullVertexSetIterator;
using orgQhull::RboxPoints;


double tetrahedronVolume(const orgQhull::QhullPoint &a, const orgQhull::QhullPoint &b,
                         const orgQhull::QhullPoint &c, const orgQhull::QhullPoint &d) 
{
    // Compute vectors
    std::vector<double> ad = {d[0]-a[0], d[1]-a[1], d[2]-a[2]};
    std::vector<double> ab = {b[0]-a[0], b[1]-a[1], b[2]-a[2]};
    std::vector<double> ac = {c[0]-a[0], c[1]-a[1], c[2]-a[2]};
    
    // Compute the cross product of ab and ac
    std::vector<double> cross_ab_ac = {
        ab[1]*ac[2] - ab[2]*ac[1],
        ab[2]*ac[0] - ab[0]*ac[2],
        ab[0]*ac[1] - ab[1]*ac[0]
    };
    
    // Compute the dot product of ad and the cross product
    double dot = ad[0]*cross_ab_ac[0] + ad[1]*cross_ab_ac[1] + ad[2]*cross_ab_ac[2];
    
    return std::abs(dot) / 6.0;
}

int main()
{
    std::vector<double> vertices;
    int ndim = 3;

    orgQhull::Qhull qhull;
    const int N = 500;
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<> dist_theta(0.0, 2 * M_PI);
    std::uniform_real_distribution<> dist_phi(0.0, M_PI);

    // generate random points on spherical surface r=1
    for (int i = 0; i < N; ++i) {
        double theta = dist_theta(gen);
        double phi = dist_phi(gen);
        double x = sin(phi) * cos(theta);
        double y = sin(phi) * sin(theta);
        double z = cos(phi);
        vertices.push_back(x);
        vertices.push_back(y);
        vertices.push_back(z);

    }
    // if following centre point is included then geometry would not be convex
    /*vertices.push_back(0);
    vertices.push_back(0);
    vertices.push_back(0);
    */

    qhull.runQhull("", ndim, vertices.size()/ndim, vertices.data(), "d QJ");  
    // "d" for Delaunay triangulation
    // QJ for jiggle of for cospherical points
    
    
    double totalVolume = 0;
    orgQhull::QhullFacetList facets = qhull.facetList();
    for(orgQhull::QhullFacetList::iterator it = facets.begin(); it != facets.end(); ++it) {
        if(!(*it).isUpperDelaunay()) {
            orgQhull::QhullVertexSet vertices = (*it).vertices();
            if(vertices.size() != 4) continue;  // Only process tetrahedra
            auto vertIter = vertices.begin();
            orgQhull::QhullPoint a = (*vertIter++).point();
            orgQhull::QhullPoint b = (*vertIter++).point();
            orgQhull::QhullPoint c = (*vertIter++).point();
            orgQhull::QhullPoint d = (*vertIter).point();
            totalVolume += tetrahedronVolume(a, b, c, d);
        }
    }
    std::cout << "Volume from delaunay triangulation : " << totalVolume << "\n";
    std::cout << "Volume of sphere r=1 : " << 4./3.*M_PI*(1.0*1.0*1.0) << "\n";

    // check if all points are on convex geometry
    orgQhull::Qhull qhullc;
    qhullc.runQhull("", ndim, vertices.size()/ndim, vertices.data(), "Qt");
    orgQhull::QhullVertexList es = qhullc.vertexList();
    if(es.size() == vertices.size()/ndim) {
        std::cout << "The geometry is convex." << std::endl;
    } else {
        std::cout << "The geometry is not convex." << std::endl;
    }

    return 0;
}

3. 使用Makefile编译代码（确保在第一步安装后，QHULL_INCLUDE和QHULL_LIB路径中有适当的qhull文件，否则请更改路径。如果需要，可以使用export LD_LIBRARY_PATH=$PWD/lib:$LD_LIBRARY_PATH从qhull文件夹中导出LD_LIBRARY_PATH）
# Compiler to use
CXX = g++

# Qhull include and library paths, adjust if necessary
QHULL_INCLUDE = /usr/local/include/
QHULL_LIB = /usr/local/lib/

# Compiler and linker flags
CXXFLAGS = -I$(QHULL_INCLUDE) -Wall -std=c++11 
LDFLAGS = -L$(QHULL_LIB) -lqhullcpp -lqhull_r

# Target executable name
TARGET = qhull_vol

# Source file name
SOURCE = qhull_vol.cpp

# Rule to build the target
$(TARGET): $(SOURCE)
    $(CXX) $(CXXFLAGS) $< -o $@ $(LDFLAGS)

# Rule to clean intermediate files and target
clean:
    rm -f $(TARGET)

# Default rule to be executed when calling 'make' without arguments
all: $(TARGET)

从终端执行代码，使用./qhull_vol命令。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接