# Changes between Version 1 and Version 2 of BoundingRegionTransformation

Show
Ignore:
Timestamp:
09/04/10 18:44:31 (7 years ago)
Comment:

--

Unmodified
Removed
Modified
• ## BoundingRegionTransformation

v1 v2
11= The problem =
2
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.
8
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.
13
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).
20
21(Illustration of the problem goes here.)
222
323= Options =
424
5 = Possible solutions =
26
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.
30
31  2. Only allow angle-preserving transformations.
32     Pros: this option is simplest.
33     Cons: might be too restrictive.
34
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.
41
42For the moment, at least, the consensus seems to be that we should keep pushing on (1).
43
44= Explorations and possible solutions =
45
46== Other representations of bounding regions ==
47
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
49
50  e(v) = min,,v' in V,, { (h(v')v').v / (v.v) }
51
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.
53
54== Transforming hyperplanes ==
55
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):
57
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.
62
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 [http://projects.haskell.org/pipermail/diagrams/2010-June/000005.html based on an idea of Ryan Yates].
64
65The outstanding issues seem to be:
66
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?
69