Well I will be talking algorithms at the next
conference during my keynote speech. Historically
it was always believed that it was not the right
thing to write papers on algorithms in syntax as
'they did not answer an architectural question'.
I've had a number of abstracts rejected on this
matter. My paper on how to compute segmental
integration using complex numbers was the only
one that got though.
There are 3 primary algorithms
1. Line intersection algorithms - how to you intersect each axial line. I use
left right testing ( do a search on google) Its
very very fast and gives a good answer in
difficult cases.
2. Global intersections methods - These are algorithms which stop one short
line on one side of the city don't intersect
lines on another. Ovation/the Log lady
use a quad tree. The only problem with using a
quad tree ( or rather a quin tree) is when an
axial line is truly horizontal or vertical. BSP
trees do the same thing. But
quad trees work well if you want to do things
like mouse intersection checking and only drawing
sub regions( when zoomed in).
3. Depth building (google
Shortest-Paths Algorithms ALL PAIRS ) that is
building the process of figuring out the depth
from one root point to all the others.
- don't build a connection matrix ( Adjacency
Matritx) and then raise it to an infinite power.
This needs far to much space for large graphs or
VGA graphs.
- don't build recursively. ( Depth First search)
The algorithms spends far to much time doing
nothing.
- I tend to using rolling wave/tooth paste
algorithums. This is simple and doesn't need any
allocation while its running. its an efficient
version of Breadth-first search.
- if you have access to the standard template
library you can do little better than implement
the standard DIJKSTRA algorithm. Its N squared
log N. I never liked it early on ( axman ) my
self as you have to write your own efficient
priority que.
if you don't like doing these your self use BOOST
http://www.boost.org/libs/graph/doc/index.html
or
My algorithms tend to be optimized on the fact
that space syntax used to only be interested in
step depths (integers 1,2.3...) - that is every
edge depth is just one. Be very careful using
floating point depths in syntax algorithms.
Rounding errors can give problems. Also my
algorithms have to be happy with multiple sources.
Natrually we are moving towards fractional
weights on the graph means moving towards more
traditional algorithms ( DIJKSTRA ). I've been
looking at optimizing shortest paths algorithms
in the case of fractional weights. When I
processed the road center line data for Atlanta
the initial algorithm the program was predicted
to take serval years on the linux box we where
running on. After some optimization we got this
down to 14 days but assumes you know what the
cacheing mechanism your CPU/OS is using.
Recently I've been thinking about next link
methods. That is for a very large city ( or a
small city with segments ) its interesting to
wonder how much of shortest path depths from one
node change when you move to another. For example
if you are on street A and move to a connected
street B then
1) all the depth changes must be One or zero different.
2) If you find a street (C) with zero depth
change from A to B then logically its impossible
for the streets from C ( streets/nodes with
larger depths ) to change. So logically you don't
have to process them ( or any nodes they connect
to ).
I have not tried this out but I'm guessing the
performance increase should be stunning. Isovist
graphs and metropolitan area processing might
find these kinds of optimizations useful.
and remember TEST TEST TEST. I always program the
simplest possible algorithm test that and then
use it as a gold test against all the other
optimizations. Its very easy to make mistakes and
a gold test can make sure your algorithm is not
generating invisible approximations(the most
insidious kind of error).
sheep
>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
|