tomilov / quickhull Goto Github PK
View Code? Open in Web Editor NEWHeader-only single-class implementation of Quickhull algorithm for convex hulls finding in arbitrary dimension (>1) space.
Header-only single-class implementation of Quickhull algorithm for convex hulls finding in arbitrary dimension (>1) space.
Add support for number type that allows to represent algebraic numbers of degree 2.
I'm wondering whether this algorithm support integer types or not.
So I ran a test.
Input set: [(19,2),(38,2),(19,7),(38,7),(0,2),(20,2),(0,7),(20,7),(9,7),(38,7),(9,12),(38,12)]
Output set: [(0,2),(38,7),(38,12)]
not so good...
I made a diagram here, https://www.desmos.com/calculator/yvrmis0nwx for your reference.
Red dots are the input set, blue dots are the output set.
Thanks.
Hi there!! I am trying to look at how the code actually works but i'm facing issues as it is getting difficult without instructions on how to run the code or what input it expects.
Can anyone provide the inputs on the same.
Elegant codes!
In 3D cases, are facets triangular facets?
Hello,
The folks at the opensuse forum have been helping me to build this app in the hope of running it on this high dimensional data.
This is the thread at opensuse
https://forums.opensuse.org/showthread.php/519164-need-cmake-3-1-or-higher-in-opensuse-13-2-yast-only-has-3-0
As you can see, there were some opensuse configuration issues to address before getting the app built. There are segfault events from both quickhull and qh.
From quickhull
(gdb) run < PCA_46-inputs.txt
Starting program: /usr/bin/quickhull < PCA_46-inputs.txt
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib64/libthread_db.so.1".
input file: stdin
dimensionality of input is 46
rbox command line:
input points count = 1955
epsilon = 0
simplex time = 423152us
Program received signal SIGSEGV, Segmentation fault.
0x000000000041e2c5 in std::__1::__split_buffer<quick_hull<std::__1::__forward_list_iterator<std::__1::__forward_list_node<std::__1::forward_list<double, std::_1::allocator >, void>>, double>::facet, std::__1::allocator<quick_hull<std::__1::__forward_list_iterator<std::__1::__forward_list_node<std::__1::forward_list<double, std::_1::allocator >, void>>, double>::facet> >::push_back(quick_hull<std::__1::__forward_list_iterator<std::__1::__forward_list_node<std::__1::forward_list<double, std::_1::allocator >, void>_>, double>::facet*&&) (this=0x7fffffffdd50,
__x=<unknown type in /usr/lib/debug/usr/bin/quickhull.debug, CU 0x15b, DIE 0x54748>) at /usr/include/c++/v1/__split_buffer:565
565 if (_end == __end_cap())
and from qh
(gdb) run < PCA_46-inputs.txt
Starting program: /usr/bin/qh < PCA_46-inputs.txt
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib64/libthread_db.so.1".
dimensionality of input is 46
rbox command line:
input points count = 1955
epsilon = 2.22045e-16
simplex time = 416578us
Program received signal SIGSEGV, Segmentation fault.
0x000000000042dd8f in std::__1::__hash_table<unsigned long,
std::__1::hash, std::__1::equal_to,
std::__1::allocator >::__construct_node (this=<error
reading variable: Cannot access memory at address 0x7fffff7fecf8>,
__v=<error reading variable: Cannot access memory at address
0x7fffff7fecf0>, __hash=<error reading variable: Cannot access memory
0x7fffff7fecf0>at address 0x7fffff7fece8>)
0x7fffff7fecf0>at /usr/include/c++/v1/__hash_table:2088 2088
Sorry for not using code tags on the above output but I can't seem to get github to format my message correctly with the code tage inserted.
There appears to be a trap for the number of input dimensions being beyond the supported range, so this would appear to be a bug. I have attached the input file here in case that is of use. The thread at opensuse has the output from running cmake. Please let me know if there is anything else you need to know.
This was built on opensuse 13.2 x86_64 and I believe that others at opensuse have tried with Leap 42.1 and Tumbleweed.
Thanks.
PCA_46-inputs.txt.zip
Hi! It seems only the facets are readily available as outputs. Is there a way to use facets to compute the centroid of the convex hull?
Thanks for sharing this code!
I was wondering if it's possible to use your implementation without clang/libc++ (just using gnu stuff).
Thanks!
Hello!
In your example, the line "qh.facets_; // use as result" can be found at the bottom.
How can I get all triangles and their points from this?
There are many iterators behind the code, but nothing immediately recognizable that can be accessed immediately.
HI Anatoliy,
The question you asked about internal ray facet intersections on the stack exchange a while ago is something I've been referencing in conjunction with MATLAB's implementation of the quickhull algorithm (convhulln) in order to find the facet in which a unit vector on a hypersphere intersects. The curse of dimensionality comes into play, as once I have the 8D coordinates of various points on a "quadrant" of a hypersphere with coarse discretization (see 3D analogue), the code is unlikely to complete (stuck in infinite loop, or just taking a really long time, e.g. 10+ hrs before I quit) or is unable to find an appropriate intersecting facet (probably an issue with precision of the inversion of the "P" matrix to get barycentric coordinates). I can get reasonable resolution, behavior, & performance up to 7D with a 6D hypersphere quadrant, but run into the issues mentioned above as soon as I'm in 8D (too coarse, can't find intersecting facet, or algorithm hangs/takes too long).
Given that, I'm wondering how this algorithm might perform using 8D points and if you have other general suggestions. What I mainly want is to know, given a random point on the hypersphere, the vertices of a facet that contains (the projection) of that datapoint so that I can perform interpolation (either through weighted averages using a distance metric, barycentric coordinates, generalized barycentric coordinates, etc.). I'll probably be posting a related stackexchange question as well.
Sterling
Hello,
First of all, thank you very much for your library, I find it quick and easy to work with.
I am using it to measure the volume occupied by particles in configurations generated with a molecular dynamics code. I noticed that, as soon as the number of particles increases above a certain threshold (a few tens of thousands on my machine) the code segfaults. I'm pretty positive that the issue lies with the way the library estimates the maximum number of faces (unsigned int nfaces = nvertices * (nvertices - 1);
). If nvertices is too big then nfaces can become enormous and the system cannot allocate enough memory, generating issues down the road.
Since I don't fill skilled enough and my use case is most likely very different from what this library was built for I do not feel comfortable preparing a PR. However, I think that there are ways of mitigating the issue. One would be to check whether malloc returns NULL or not. In the former case, one could either quit with an error or decrease the value of nfaces and issue a warning. There could also be some sort of hard limit for nfaces which could be set with a macro.
It would be nice to have an example that was not 200 lines long. Its pretty hard to follow the example code
Thanks for all your work and for making this convex hull library available. I am evaluating it for use in my program.
My data sets will often contain a bunch of co-planar points. In my first tests with your tool, these cause if ( !qh.check() )
to fail. In your example, this test is accompanied with the comment // resulted structure is not convex (generally due to precision errors)
.
If I go ahead and try to make use of the resulting mesh, I get something messy like the following:
Is convhull expected to work in cases like this? Does convhull use robust geometric predicates for things like the 3D orientation test?
I have attached a points file corresponding to this test case.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.