[Haskell-cafe] Re: Painting logs to get a coloured tree

[Joachim Breitner]

Hi,

Am Dienstag, den 10.02.2009, 11:59 +0100 schrieb Heinrich Apfelmus:
> However, I would be surprised if  someAlgorithm  could not be formulated
> directly on the tree or at least satisfies a few invariants like for example
> 
>     map fst . someAlgorithm = map snd
> 
> Also, how does  cutTreeApart  arrange the list? The idea is that most of
> the tree structure survives in the list and can be reconstructed.

Probably not. My algorithm calculates the amount of light that shines
through the branches, and the amount of light cought by the branches
(seeing branches as approximations for leaves here :-)).

The algorithm works by taking the list of branches (represented by their
start and end point), projects them along the direction of light,
creates a list of start and endpoints, sorts them (to be able to sweep
the line somewhat efficiently) and adds the projections of all
intersections of branches. Then it iterates through the intervals on
this line, gets the list of branches that are hit by this interval,
sorts them by hights and adds, from top to bottom, the appropriate,
decreasing portion of the light that comes in this interval.

In this process, the branches are sorted around quite a bit, and I
assume it would be hard to preserve the structure.

If you want to see code (not sure though if you really want to see that
code :-)), it’s in 
http://git.nomeata.de/?p=L-seed.git;a=blob;f=src/Lseed/Geometry.hs
Lines 74-142.

Greetings,
Joachim

-- 
Joachim Breitner
  e-Mail: mail at joachim-breitner.de
  Homepage: http://www.joachim-breitner.de
  ICQ#: 74513189
  Jabber-ID: nomeata at joachim-breitner.de
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: Dies ist ein digital signierter Nachrichtenteil
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20090210/9c9889c7/attachment.bin