qhull 库 - C++ 接口

问题描述 投票：0回答：4

qhull 库 (qhull.org) 在他的网站上有几个示例，但所有有关 C++ 的信息对我来说并不是很有用。

我正在尝试制作一个从文件中读取的 3D 点的简单凸包，我无法使用调用 qhull.exe 作为外部应用程序的网站中建议的技术，因为我需要制作几个凸包船体来自我对数据点所做的一些修改。

我找不到执行此操作的简单示例，有人可以在这项任务中为我提供一些帮助吗？任何信息都会有用。

谢谢

c++ convex-hull qhull
4个回答
21
投票

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

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

所以，首先，从这里下载 qhull 源文件后 在 VS 中打开一个项目，您需要添加的唯一文件是以下 2 个目录：

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));
        }
    }
}

请注意，我从项目中复制了此代码，并对其进行了一些修改以提供更多信息，但尚未编译此示例。

1
投票

这是一个使用 c++ 中的可重入 qhull 的简单示例。我想这可能有用。

#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();
    }
}
1
投票

这篇文章是我能找到的 qHull 的唯一示例，因此我想添加这段代码，了解如何使用 qhull 获取 2D 点集的凸包。

#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，但它与一些遗留代码冲突太多。这可能不是最有效的实现，但它比我之前的实现要好得多。

0
投票

以下步骤帮助我在我的 ubuntu 机器上 -

  1. 正如 github 自述文件中提到的，

    • 下载并解压 Qhull（GitHub、.tgz 文件或 .zip 文件）
    • 制作
    • 进行安装
    • 进行测试

  2. 示例代码

    qhull_vol.cpp
    对随机分布在半径为1的球体上的点进行德劳内三角剖分。它还检查几何形状是否是凸的。 （以下示例中的一些部分使用了互联网资源）

#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;
}
  1. Makefile 来编译代码（确保 
    QHULL_INCLUDE
    和 
    QHULL_LIB
    路径在第一步安装后具有适用于 qhull 的适当文件，否则请更改路径。如果需要，请从 qhull 文件夹使用 
    export LD_LIBRARY_PATH=$PWD/lib:$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)
  1. 从终端执行
    ./qhull_vol
    代码
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.