Changes between Version 1 and Version 2 of BoundingRegionTransformation

09/04/10 18:44:31 (7 years ago)
byorgey (IP:



  • BoundingRegionTransformation

    v1 v2  
    11= The problem = 
     3We've chosen to represent bounding regions for diagrams in a 
     4functional style.  A bounding region for a vector space V with 
     5scalar type S is a function h : V -> S such that h(v)v is the 
     6shortest vector in the direction of v whose perpendicular 
     7hyperplane completely contains the region. 
     9For example, to represent a circular region of radius 2, we use 
     10h(v) = 2/|v|, since multiplying any vector v by 2/|v| gives a 
     11vector in the direction of v of length 2, which brings us to the 
     12edge of the circle. 
     14The problem is how to transform h along with a diagram when 
     15applying some sort of transformation.  It is not hard to 
     16transform h when applying a transformation T ''which preserves 
     17angles''.  Then we have (Th)(v) = h(T^-1^ v).  However, this 
     18does not work for transformations which do not preserve angles 
     19(such as shears and non-uniform scalings). 
     21(Illustration of the problem goes here.) 
    323= Options = 
    5 = Possible solutions = 
     25As [ discussed in this thread]: 
     27  1. Buckle down and work really hard and figure out how to do it. 
     28     Pros: this would be awesome.   
     29     Cons: we don't even know if it's possible. 
     31  2. Only allow angle-preserving transformations.   
     32     Pros: this option is simplest. 
     33     Cons: might be too restrictive. 
     35  3. Switch to a different representation of bounding regions that 
     36     will integrate better with general transformations. 
     37     Pros: ability to do general transformations. 
     38     Cons: probably a lot of work, and the current representation 
     39     seems so elegant and functional, it would be a shame to give it 
     40     up. 
     42For the moment, at least, the consensus seems to be that we should keep pushing on (1). 
     44= Explorations and possible solutions = 
     46== Other representations of bounding regions == 
     48There 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 
     50  e(v) = min,,v' in V,, { (h(v')v').v / (v.v) } 
     52or 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. 
     54== Transforming hyperplanes == 
     56If 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): 
     58  1. Compute some appropriate representation of the hyperplane containing the endpoint of v and perpendicular to v, call it H. 
     59  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. 
     60  3. Find v' perpendicular to, with its endpoint contained in, H', and compute s = h(v'). 
     61  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. 
     63The 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]. 
     65The outstanding issues seem to be: 
     67  1. How to compute step (1)?  What is an appropriate representation of a hyperplane in general? 
     68  2. Work out the details of step (4).  Does it really work?