Version 2 (modified by byorgey, 4 years ago)

--

The problem

We've chosen to represent bounding regions for diagrams in a functional style. A bounding region for a vector space V with scalar type S is a function h : V -> S such that h(v)v is the shortest vector in the direction of v whose perpendicular hyperplane completely contains the region.

For example, to represent a circular region of radius 2, we use h(v) = 2/|v|, since multiplying any vector v by 2/|v| gives a vector in the direction of v of length 2, which brings us to the edge of the circle.

The problem is how to transform h along with a diagram when applying some sort of transformation. It is not hard to transform h when applying a transformation T which preserves angles. Then we have (Th)(v) = h(T-1 v). However, this does not work for transformations which do not preserve angles (such as shears and non-uniform scalings).

(Illustration of the problem goes here.)

Options

As discussed in this thread:

  1. Buckle down and work really hard and figure out how to do it. Pros: this would be awesome. Cons: we don't even know if it's possible.
  1. Only allow angle-preserving transformations. Pros: this option is simplest. Cons: might be too restrictive.
  1. Switch to a different representation of bounding regions that will integrate better with general transformations. Pros: ability to do general transformations. Cons: probably a lot of work, and the current representation seems so elegant and functional, it would be a shame to give it up.

For the moment, at least, the consensus seems to be that we should keep pushing on (1).

Explorations and possible solutions

Other representations of bounding regions

There is another possibility for representing bounding regions functionally. Instead of giving the distance to the nearest enclosing hyperplane (h), we could give the distance (again as a multiple of the length of the input vector) to the boundary itself. Call this function e : V -> S. For circles, h(v) = e(v), but it should be clear that they are not the same for more complicated shapes. It seems that e(v) should be much simpler to transform than h(v). e(v) and h(v) are also dual in a sense: we have

e(v) = minv' in V { (h(v')v').v / (v.v) }

or something like that (basically, the minimum over all other vectors of the projection of h onto v), whereas h(v) can be defined in exactly the same way in terms of e(v) but using max instead of min. Unfortunately this doesn't seem very practical from a computational point of view.

Transforming hyperplanes

If we restrict ourselves to transformations that preserve parallel lines (which includes all affine transformations but not projective transformations in general) then we may proceed as follows to compute (Th)(v):

  1. Compute some appropriate representation of the hyperplane containing the endpoint of v and perpendicular to v, call it H.
  2. Compute T-1(H), call it H'. The important point is that due to our insistence that T preserves parallelism, any hyperplane parallel to H' is sent by T to a hyperplane parallel to H.
  3. Find v' perpendicular to, with its endpoint contained in, H', and compute s = h(v').
  4. Compute T(v') and scale s according to (a) how much T shrinks or expands v' and (b) by projecting T(v') back onto v.

The above ought to be worked out in a bit more detail but this is the basic idea. I think this will work as long as we are willing to restrict ourselves to affine transformations, which is probably just fine. This is based on an idea of Ryan Yates.

The outstanding issues seem to be:

  1. How to compute step (1)? What is an appropriate representation of a hyperplane in general?
  2. Work out the details of step (4). Does it really work?