Библиотека qhull - интерфейс C++

Библиотека qhull ( qhull.org) имеет несколько примеров для запуска на своем веб-сайте, но вся информация, касающаяся C++, не очень полезна для меня.

Я пытаюсь создать простую выпуклую оболочку из трехмерных точек, которую я читаю из файла, я не могу использовать метод, предложенный на веб-сайте, для вызова qhull.exe как внешнего приложения, потому что мне нужно сделать несколько выпуклых оболочек от некоторых изменений, которые я сделал в точках данных.

Я не могу найти простой пример для этого, кто-то может мне помочь с этой задачей? Любая информация будет полезна.

Спасибо

Источник

4 ответа

Поскольку мне было трудно использовать 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 in 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));
        }
    }
}

Обратите внимание, что я скопировал этот код из своего проекта и немного изменил его, чтобы сделать его более информативным, но не скомпилировал этот пример.

Источник

Вот простой пример использования 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();
    }
}
Источник

В этом посте были единственные примеры qHull, которые я смог найти, поэтому я хотел добавить этот фрагмент кода для того, как получить выпуклую оболочку 2D-набора точек с помощью 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;
}

Мне также пришлось собрать библиотеки и связать а также в дополнение к добавлению к включенному пути. Включен проект Qt, который вы можете открыть и собрать, который создаст для вас библиотеки.

Сначала я попытался использовать boost, но он слишком сильно конфликтовал с некоторым устаревшим кодом. Возможно, это не самая эффективная реализация, но она намного лучше того, что у меня было раньше.

Источник

Следующие шаги помогли мне на моей машине с Ubuntu:

  1. Как упоминалось в файле readme на 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 после установки на 1-м этапе, в противном случае измените пути. Использоватьexport LD_LIBRARY_PATH=$PWD/lib:$LD_LIBRARY_PATHесли нужно из папки qhull)
      # 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из терминала
Источник
Другие вопросы по тегам