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
Jörg Krämer wrote:
> Hello Andrew,
> concerning algorithms used for Visibility Graph Analysis, there is a 2001
> paper by Alasdair Turner where he explains his software Depthmap, including
> pseudocode for basic algorithms he uses to construct the visibility graph
> and to measure Mean Depth, Clustering Coefficient, Control, Point Depth
> Entropy etc. It is available from the proceedings of the 3rd Space Syntax
> Symposium at
> http://undertow.arch.gatech.edu/homepages/3sss/papers_pdf/31_turner.pdf .
> But for a comprehensive overview of algorithms (especially any clever
> speed-optimised alternatives) I would be most grateful too, as we are
> working on our own little VGA implementation at the moment.
>
> Regards
> Joerg Kraemer
>
>
--
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
|