Originally Posted by

**std10093**
That's seems to be interesting. Very interesting! I have written the program in C++, but I do not think is a problem, is it? Moreover, I have no idea what this is, so would it be hard to try it? What should I do?

No problem at all! Consider this small example program. It creates a small binary tree, and then spits out the definition in dot (language) to standard output. I'm using the pointers (node addresses) as the identifiers:

Code:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>
struct node {
struct node *left; /* Less than or equal to */
struct node *right; /* Greater than */
int value;
};
struct node *tree_add(struct node **const rootptr, int value)
{
struct node *newnode, *curr, **pptr;
/* Tree not specified? */
if (!rootptr) {
errno = EINVAL;
return NULL;
}
/* Create node. */
newnode = malloc(sizeof *newnode);
if (!newnode) {
errno = ENOMEM;
return NULL;
}
/* Initialize node. */
newnode->left = NULL;
newnode->right = NULL;
newnode->value = value;
/* Descend into the tree. */
pptr = rootptr; /* Pointer to pointer used to get to curr. */
curr = *rootptr; /* Current node. */
while (curr)
if (curr->value >= value) {
pptr = &curr->left;
curr = curr->left;
} else {
pptr = &curr->right;
curr = curr->right;
}
/* Add node to where we dropped off the tree. */
*pptr = newnode;
/* Done! */
return newnode;
}
/* Recursively describe the nodes of the tree in DOT.
*/
void fdot_node(FILE *const out, const struct node *const node)
{
fprintf(out, "\t\"%p\" [ label=\"%d\", shape=oval ]\n", node, node->value);
if (node->left) {
fdot_node(out, node->left);
fprintf(out, "\t\"%p\" -> \"%p\" [ taillabel=\"≤\" ]\n", node, node->left);
}
if (node->right) {
fdot_node(out, node->right);
fprintf(out, "\t\"%p\" -> \"%p\" [ taillabel=\">\" ]\n", node, node->right);
}
return;
}
/* Write the structure of the tree in DOT language.
* Returns 0 if success, errno error code otherwise.
*/
int fdot(FILE *const out, const struct node *const tree)
{
/* Invalid parameters? */
if (!out || !tree)
return errno = EINVAL;
/* I/O error? Paranoid check, really.. */
if (ferror(out))
return errno = EIO;
/* Start by describing the entire graph. */
fprintf(out, "digraph {\n");
/* Describe nodes recursively. */
fdot_node(out, tree);
/* Finish the graph. */
fprintf(out, "}\n\n");
/* Still everything OK in out? */
if (ferror(out))
return errno = EIO;
/* Success! */
return errno = 0;
}
int main(void)
{
struct node *tree = NULL;
tree_add(&tree, 5);
tree_add(&tree, 3);
tree_add(&tree, 7);
tree_add(&tree, 2);
tree_add(&tree, 4);
tree_add(&tree, 6);
tree_add(&tree, 8);
tree_add(&tree, 1);
tree_add(&tree, 9);
fdot(stdout, tree);
return 0;
}

If you compile and run it, it generates something like

Code:

digraph {
"0x22b9010" [ label="5", shape=oval ]
"0x22b9030" [ label="3", shape=oval ]
"0x22b9070" [ label="2", shape=oval ]
"0x22b90f0" [ label="1", shape=oval ]
"0x22b9070" -> "0x22b90f0" [ taillabel="≤" ]
"0x22b9030" -> "0x22b9070" [ taillabel="≤" ]
"0x22b9090" [ label="4", shape=oval ]
"0x22b9030" -> "0x22b9090" [ taillabel=">" ]
"0x22b9010" -> "0x22b9030" [ taillabel="≤" ]
"0x22b9050" [ label="7", shape=oval ]
"0x22b90b0" [ label="6", shape=oval ]
"0x22b9050" -> "0x22b90b0" [ taillabel="≤" ]
"0x22b90d0" [ label="8", shape=oval ]
"0x22b9110" [ label="9", shape=oval ]
"0x22b90d0" -> "0x22b9110" [ taillabel=">" ]
"0x22b9050" -> "0x22b90d0" [ taillabel=">" ]
"0x22b9010" -> "0x22b9050" [ taillabel=">" ]
}

except that the pointer labels ("0x...") will vary, of course. If you save that as say *example.dot*, and then run

Code:

dot -Tpng example.dot > example.png

the end result will look like this:

Attachment 12845

Note that *dot* does reorder the edges as it sees best; in particular, any edge starting from the left side from an oval is not necessarily the left child. That's why I added the tail labels to the arrows.

Using

Code:

neato -Tpng example.dot > neato.png

from the same data will generate an image like

Attachment 12844

If you generate SVG (*-Tsvg*) images, you can edit them in e.g. Inkscape, letting you fine-tune the images for e.g. your documentation.

Originally Posted by

**std10093**
So, let's say I split the original polytope somehow, the question I have, is why to divide based on the halfspaces? Why not to split, based on the vertices of the polytope?

Consider a half-sphere in three or more dimensions. It is convex, and perfectly suitable for this algorithm. The flat side is obviously only one halfspace.

If you split more than once, none of the vertices defining the flat face will be inside your boxes. However, some of the boxes will still intersect with the flat face, and thus *must* be limited by the flat face halfspace.

Because of this, you cannot consider only those vertices that lie within current box, but must consider all vertices that take part in the faces that intersect with the current box. Because halfspace == face, it's just more efficient to use the halfspaces.

If you want to use the vertices, you can, but then you must somehow keep all the necessary vertices along when you recursively generate the tree. You cannot just drop any vertex that happens to be outside the current box, because such vertices can still participate in the faces that intersect the current box.

Originally Posted by

**std10093**
The leaves contain the halfspaces of the subpolytopes.

Note that in my method, I did not construct subpolytopes. My logic was more like:

- Start with the halfspaces forming the original convex polytope,

and with the bounding box of the original convex polytope. - If the current box intersects with not more than
*T* halfspace planes (face hyperplanes), then this node in the tree is a leaf, and specifies these halfspaces.

Otherwise:

Split the current box into 2^{D} sub-boxes, and repeat this step for each of them.

Theoretically, it is possible that the current box is completely inside or completely outside the polytope. So, in my program I also checked for that, and used *NULL* for completely outside, and a special "all inside" leaf node for completely inside.

This procedure means that within each box, *we only consider those halfspaces of the original polytope that affect points within each box*. Those halfspaces do not form a polytope, they are open to infinity in some directions. I don't know how to explain this well, but it is clear if you look at the nodes.

Perhaps it would be best if I clean up my implementation and post it here?

I'm pretty sure at this point that it won't affect you unduly, because you're certainly thinking about this at least as much as I have; but, it would allow us to look at my implementation and make it easier to discuss the choices I made, and why I made them. In particular, I'm not at all certain I fully followed the article, so relying on anything I've said or have done is not necessarily correct.