I meant BSP tree (Binary Space Partition), not B-star tree.
As for the data structure that will help you, I'm not sure -- I think
Sheep's doing something on rendering optimisation through identification
of thresholds at the moment, which might help. However, finding some
sort of optimised structure must be similar to the clique problem.
Alasdair
Jörg Krämer wrote:
> Dear Alasdair,
>
> thank you for your details on Depthmap algorithms and the hint with the
> b*tree.
>
> So far we have our VGA routine running with an expanding ring (only upwards
> so as not to check individual connections twice) as well, but
> intervisibilities and depth steps stored in system-size matrices for each
> grid point, with just basic iteration so as not to have to search a list. It
> works ok but we use it to evaluate fitness in a GA (roll eyes) which of
> course multiplies any delays, so it might be worth restructuring. I just
> found it hard to predict whether establishing a more complicated data
> structure in the first place would save us any time - probably depends on
> the small-world qualities of the individual graph.
>
> Joerg
>
>
> --
> Joerg Kraemer, Jan-Oliver Kunze
> Diplomanden FG Finn Geipel, Technische Universitaet Berlin
> Ackerstrasse 71-76, Raum 438, 13355 Berlin, Germany +49 30 31472748
> [log in to unmask], [log in to unmask]
>
>
>
>
>>-----Original Message-----
>>From: [log in to unmask] [mailto:[log in to unmask]] On
>>Behalf Of Alasdair Turner
>>Sent: Friday, April 15, 2005 10:06 PM
>>To: [log in to unmask]
>>Subject: Re: Seeking a list of space syntax algorithms
>>
>>Dear Jorg,
>>
>>In order to make graph connections, Depthmap simply uses an expanding
>>ring around the current grid point -- I believe it's a fairly standard
>>technique, although probably not the fastest -- if I were doing it again
>>I would use a B*-tree (do a Google search to find online algorithms). I
>>believe Yiorgos Chrysanthou (Google once more) coded the version used in
>>Sanjay Rana's Isovist Analyst extension.
>>
>>As for integration the analysis, Depthmap just uses a straight forward
>>breadth first search -- any algorithm book should be able to give you as
>>good a algorithm as used in Depthmap -- there are no hidden
>>optimisations, although I would say that it is very well written! :-)
>>
>>Alasdair
>>
>
>
>
--
Alasdair Turner
Lecturer in Architectural Computing
Bartlett School of Graduate Studies
UCL Gower Street LONDON WC1E 6BT
Course Director: MSc Virtual Environments
MSc Adaptive Architecture and Computation
|