I think it's time to get a look at your code.

I had implemented GRAHAM-SCAN algorithm for finding convex hulls, that runs in O(nlogn).

This is a discussion on *Quadtrees* within the **Tech Board** forums, part of the Community Boards category; I think it's time to get a look at your code.
I had implemented GRAHAM-SCAN algorithm for finding convex hulls, ...

- 08-27-2013 #76
I think it's time to get a look at your code.

I had implemented GRAHAM-SCAN algorithm for finding convex hulls, that runs in O(nlogn).Code - functions and small libraries I use

It’s 2014 and I still use printf() for debugging.

"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

- 08-28-2013 #77
Recall that the index of the child for descending into the tree is:

Code:child = 1 * (testpoint.x >= split.x) + 2 * (testpoint.y >= split.y) + 4 * (testpoint.z >= split.z);

But, we should probably first check if the test point is inside the bounding box.

This seems to do the trick:

Code:/** * Checks if a point lies inside the bounding box of the polytope. * @param box - the bounding box of the polytope (of the root) * @param p - test point * @return - result */ bool Quadtree::insidePolytopeBox(const BoundingBox* box, const Point3d& p) { for(int i = 0 ; i < D ; ++i) // Check all coordinates if(box->getMinBox()[i] > p[i] || box->getMaxBox()[i] < p[i]) return false;; return true; }

Last edited by std10093; 08-28-2013 at 06:09 AM.

Code - functions and small libraries I use

It’s 2014 and I still use printf() for debugging.

"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

- 08-28-2013 #78

- Join Date
- Oct 2011
- Posts
- 823

No; you are forgetting that the halfspaces retained for inclusion tests in each node (or its child nodes)

*are only relevant to points within the bounding box of that node*.

Remember, we specifically store*only*the information relevant to that bounding box. So, descending into the tree with a point outside the original bounding box yields*undefined*results.

In practice, it should not matter, as every direction from inside the halfspace should be bounded by a halfspace.

Our implementations don't do that, though, because of the way we define "interesting halfspace": we ignore halfspaces that are perpendicular to the X, Y, or Z axes, on the lower-coordinate side of the polytope (the*inside*==0,*outside*==0 case; i.e. one or more corners of the box are on the halfspace plane, but no corner is clearly inside or outside the halfspace). This does not mean there should be any possibility of infinite recursion or stuff like that; it just means the tree constructed is only valid for points inside the original bounding box.

Take the (0,0,0),(1,0,0),(0,1,0),(0,0,1) tetrahedron as an example. If you test point (-1,-1,-1), ignoring the original bounding box, you get result*inside*. That is because the three axis-perpendicular faces are coplanar with the bounding box, and found "uninteresting" -- as they don't do any further limiting to point inclusion compared to the bounding box alone. The tree is really just one leaf with the diagonal halfspace, as the bounding box coincides with the other sides. So, negative coordinates will always yield "inside", because they are "inside" if you only consider the diagonal halfspace.

If you were to consider the halfspaces that are coplanar with a bounding box corner, edge, or side interesting, then the initial bounding box does not matter, and it would be correct to descend into child five in the case you showed.

- 08-28-2013 #79
Ok, but having like the one I posted above ( insidePolytopeBox ), has a really low cost, so I think I am gonna use it.

I got rid of the BoundingBox and I am calculating the boxes locally.. The problem is that my tree gets very very big and that is because I find many interesting halfspaces, until I have created many levels...Code - functions and small libraries I use

It’s 2014 and I still use printf() for debugging.

"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

- 09-04-2013 #80

- Join Date
- Oct 2011
- Posts
- 823

The any-dimensional code is way too spaghetti for me to post it; I cringe every time I look at it.

Besides, the algorithm does not truly scale to*"any"*number of dimensions*D*, because each inner node will need to contain 2^{D}child pointers. On 32-bit systems, a single 28-dimensional inner node takes a gigabyte!

The relationship between the number of dimensions*D*, and leaf nodes having up to*t*halfspaces, is such that on 64-bit systems where pointers and doubles are the same size, inner and leaf nodes are about the same size ifFor 20-dimensional data, an inner node is the same size as a leaf node with about 50,000 halfspaces.*t*≃ 2^{D}/ (*D*+ 1)

In other words, I strongly believe this algorithm is suitable for small number of dimensions only.

Also, I haven't had time to implement a nice convex hull algorithm, either; partly because the methods get pretty hairy (to fully grok) when there are more than three spatial dimensions. (I personally would need to take the time to develop the two and three dimensional cases in parallel first, then compare the two to develop the generic case.)

I think I'll just clean up my 3D convex hull case, post it here, and call it done.

- Exactly how to get started with C++ (or C) today
- C Tutorial
- C++ Tutorial
- 5 ways you can learn to program faster
- The 5 Most Common Problems New Programmers Face
- How to set up a compiler
- 8 Common programming Mistakes
- What is C++11?
- Creating a game, from start to finish

- How to create a shared library on Linux with GCC - December 30, 2011
- Enum classes and nullptr in C++11 - November 27, 2011
- Learn about The Hash Table - November 20, 2011
- Rvalue References and Move Semantics in C++11 - November 13, 2011
- C and C++ for Java Programmers - November 5, 2011
- A Gentle Introduction to C++ IO Streams - October 10, 2011