Tiling the faces of a polygon/polytope [Archive]

cr34m3

Apr 20th, 2010, 06:49 AM

(This topic is related to computational geometry - I hope this is the correct forum :) )

What I would like to achieve is the generation of a mesh of data points (of some resolution) on the faces of a polygon/polytope. I specifically need points ON the faces as I would like to do a transformation of the initial shape through some equation.

The problem is closer to linear programming than geometry, per say, as the initial shapes are defined by inequalities. I'll use a simple example of what I want to achieve:
For the inequalities;
x,y,z > 0
x,y,z < 1
x+y+z < 2
a unit-cube is generated from which the one corner is 'cut off'.
The vertices of this shape are;
(0 1 0), (0 0 0), (1 0 0), (0 0 1), (0 1 1), (1 0 1), (1 1 0)
and its clear that it has 7 faces (4 triangular- and 3 square-shaped). It is on these faces that I would like to generate extra data points (seeing that I only have the 7 vertices at the moment).

My example uses just 3 dimensions, but eventually I'll go up to even more, so my approach needs to be rather generic.

At the moment I am stumped, as all the routines/algorithms I've looked at are very data-driven and focus little on extra data generation. Any suggestions, ideas or pointers to other sources will be greatly appreciated.

Ideally I'd be looking for Python modules, but if writing a wrapper for some C/C++ code gets me what I want then so be it.

Thanks

André

jemidiah

Apr 20th, 2010, 09:05 PM

That's a very complicated question. I'd be surprised if you got a terribly satisfactory answer to it here, especially since you're asking for advice that's not related to Visual Basic. However, I can give my own thoughts on your problem, for whatever they're worth.

You have several steps:
1. Specify the polytope.
2. Determine equations for the hyperplanes forming the polytope's sides (e.g. specify normal and x-intercept)
3. Determine bounds for the hyperplanes, that is, determine the shape of the face of the object bounded by a particular hyperplane
4. Create a mesh for each face

Each step is difficult. You've asked specifically about creating a mesh, so I'll assume you can magically do 1-3 and somehow specify a face of your polytope. I'll guess that this comes in the form of a cyclic, connected, undirected graph, where adjacent vertexes in the face are connected in the graph.

There are many ways to do this, I'm sure, some being better than others. First off, you could simply create a bounding n-1-dimensional hypercube for the face without too much difficulty: the bounding box is made up of intervals [xi_min, xi_max]_i for i = 1 to n, n being the number of dimensions you're working in. You could then blanket this bounding hypercube with evenly spaced points, taking only those that lie inside the face. Checking if they lie on the face could be done by seeing if they satisfy the linear equations (note: they must satisfy one of the equations exactly, so that they're in fact on the polytope and not simply inside it) bounding the polytope. Each check would require evaluating (at least) n linear equations, each of which would require (at most) O(n) multiplications and additions. For an evenly spaced mesh inside a box which gives D points per side, this would then require O(D^(n-1) n^2) multiplications and additions. In 10 dimensions, with D even very small, say, 5, you would perform hundreds of millions of arithmetic operations.

This could be significantly optimized by trying to stay within the face instead of just bounding it. D would effectively be reduced, and the n^2 checks would also disappear. If you can assume the faces will be convex (which is implied by the OP, though you haven't been specific so I haven't assumed it), you could instead use a convex hull (http://en.wikipedia.org/wiki/Convex_hull) approach to create a mesh. In particular, you could create a mesh using convex combinations of the vertexes vi, i=1 to k, of the face: create points p = Sum[ti*vi, i=1 to k] where Sum[ti, i=1 to k] = 1, and each ti >= 0. Varying the ti within the given constraints would generate a mesh. There are many ways to choose which ti to use. I have various ideas on performing such a choice if you're interested. Any decent way should take constant (possibly amortized) time to generate a new set of ti's from an existing set, which can be done. This reduces the order of generating a mesh for a given face to be akin to O(D_reduced ^(n-1)), where D_reduced is at most D, and most likely quite a bit smaller (unless the face happens to be a hypercube oriented along the standard basis, in which case D_reduced is exactly D, though even then you've gotten rid of an n^2 term).

So, abstractly at least, there's a couple of methods to do what you want off the top of my head. I have to say, I wonder a little at how useful creating these meshes will be. The number of points you'll generate will get *very* large, very quickly, at least in high dimensions. The 3D example remains pretty sane, but at the very least the number of points you generate, and therefore a lower bound on the order of your algorithm, grows as (quite roughly) C^n for some constant C which depends on your polytope's geometry and your mesh spacing. Considering how inefficient such an operation is in general, I'm unsure if anyone has written code which, say, takes in a series of linear inequalities and generates a huge mesh on that n-dimensional (convex, one may hope) polytope--the output could easily be gigabytes of data, or take the lifetime of the universe to compute.