http://www.haskell.org/haskellwiki/index.php?title=Diagrams/Dev/Bounds&feed=atom&action=historyDiagrams/Dev/Bounds - Revision history2014-10-20T10:04:04ZRevision history for this page on the wikiMediaWiki 1.19.5-1+deb7u1http://www.haskell.org/haskellwiki/index.php?title=Diagrams/Dev/Bounds&diff=43721&oldid=prevByorgey: import old notes re: bounding functions2011-12-21T19:38:05Z<p>import old notes re: bounding functions</p>
<p><b>New page</b></p><div>Note: this problem has now been solved using the inverse transpose (see the last section below); this page is still here just for historical reference.<br />
<br />
= The problem =<br />
<br />
We've chosen to represent bounding regions for diagrams in a<br />
functional style. A bounding region for a vector space V with<br />
scalar type S is a function h : V -> S such that h(v)v is the<br />
shortest vector in the direction of v whose perpendicular<br />
hyperplane completely contains the region.<br />
<br />
For example, to represent a circular region of radius 2, we use<br />
h(v) = 2/|v|, since multiplying any vector v by 2/|v| gives a<br />
vector in the direction of v of length 2, which brings us to the<br />
edge of the circle.<br />
<br />
The problem is how to transform h along with a diagram when<br />
applying some sort of transformation. It is not hard to<br />
transform h when applying a transformation T ''which preserves angles''. Then we have (Th)(v) = h(T^-1^ v). However, this<br />
does not work for transformations which do not preserve angles<br />
(such as shears and non-uniform scalings).<br />
<br />
(Illustration of the problem goes here.)<br />
<br />
= Options =<br />
<br />
As [http://projects.haskell.org/pipermail/diagrams/2010-August/000009.html discussed in this thread]:<br />
<br />
# 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.<br />
# Only allow angle-preserving transformations. Pros: this option is simplest. Cons: might be too restrictive.<br />
# 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.<br />
<br />
For the moment, at least, the consensus seems to be that we should keep pushing on (1).<br />
<br />
= Explorations and possible solutions =<br />
<br />
== Other representations of bounding regions ==<br />
<br />
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<br />
<br />
e(v) = min,,v' in V,, { (h(v')v').v / (v.v) }<br />
<br />
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.<br />
<br />
== Transforming hyperplanes ==<br />
<br />
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):<br />
<br />
# Compute some appropriate representation of the hyperplane containing the endpoint of v and perpendicular to v, call it H.<br />
# 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.<br />
# Find v' perpendicular to, with its endpoint contained in, H', and compute s = h(v').<br />
# 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.<br />
<br />
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 [http://projects.haskell.org/pipermail/diagrams/2010-June/000005.html based on an idea of Ryan Yates].<br />
<br />
The outstanding issues seem to be:<br />
<br />
# How to compute step (1)? What is an appropriate representation of a hyperplane in general?<br />
# Work out the details of step (4). Does it really work?<br />
<br />
For step (1), perhaps see [http://en.wikipedia.org/wiki/Gramâ€“Schmidt_process Gram-Schmidt process], and also this exchange from the [http://tunes.org/~nef/logs/haskell/10.09.30 #haskell IRC channel on 30 Sep 2010]:<br />
<br />
<pre><br />
18:18:27 <byorgey> given a vector v in an inner product space, how might I go about computing a basis for the hyperplane orthogonal to v?<br />
18:18:45 <Veinor> ask #math? :D<br />
18:19:02 --- join: dnolen (~davidnole@cpe-68-173-254-181.nyc.res.rr.com) joined #haskell<br />
18:19:09 * byorgey shudders<br />
18:19:11 <ddarius> byorgey: for all basis vectors b, keep b if b ^ v /= 0<br />
18:20:00 --- join: c_wraith (~c_wraith@209.237.247.90) joined #haskell<br />
18:20:01 <byorgey> ddarius: ^ is inner product?<br />
18:20:10 <Cale> byorgey: Well, pick random vectors and subtract off the orthogonal projection onto the subspace spanned by v<br />
18:20:11 <benmachine> isn't ^ usually used for cross product<br />
18:20:11 <ddarius> byorgey: Wedge product.<br />
18:20:13 <benmachine> or is that v<br />
18:20:24 * benmachine always just used, you know, cross<br />
18:20:30 <ddarius> Of course, the dual of v will be a blade that represents the hyperplane orthogonal to it already...<br />
18:20:50 <aristid> so google found IOSpec for me http://www.cse.chalmers.se/~wouter/repos/IOSpec/index.html<br />
18:20:53 <ddarius> b ^ v = b . dual(v)<br />
18:21:08 <byorgey> ddarius: where can I read about this?<br />
18:21:28 <Veinor> byorgey: for each basis vector b, compute b - proj_v b<br />
18:21:36 <byorgey> can I apply affine transformations to such duals?<br />
18:21:47 <Veinor> (I don't know anything about vector spaces besides R^n)<br />
18:22:42 <ddarius> http://geocalc.clas.asu.edu/ (mathematical/physics), http://www.mrao.cam.ac.uk/~clifford/ (physics), http://www.science.uva.nl/ga/ (computer science)<br />
18:22:47 <ddarius> byorgey: ^<br />
18:23:36 <benmachine> haskell-src-exts' fixity resolution is super-brokwn<br />
18:23:39 <benmachine> *broken<br />
18:23:45 <benmachine> well, fairly broken anyway<br />
18:24:12 <ddarius> byorgey: I recommend starting here: http://geocalc.clas.asu.edu/html/Intro.html and here: http://www.science.uva.nl/ga/publications/index.html<br />
18:25:14 <ddarius> byorgey: This deceptively named paper is rather useful a bit later on: http://www.science.uva.nl/ga/publications/content_publications.html#leo_inner<br />
</pre><br />
<br />
== Inverse transpose ==<br />
<br />
See [http://www.unknownroad.com/rtfm/graphics/rt_normals.html this page]. Is it really that simple? Note we can carry along the inverse transpose in the same way that we currently carry along the inverse, so we don't have to resort to extracting matrix representations.<br />
<br />
See also Subject 5.27 in http://www.faqs.org/faqs/graphics/algorithms-faq/ .</div>Byorgey