[GRASS-dev] r.los scales badly

GRASS GIS GRASS GIS developer
1

Hi,

I've done some time measurements with r.los.

Basically I'm working on a DTM raster of Austria derived from SRTM data.

Thus, the region has a native res of 90m and has 2224 rows and 2228 columns.

If I'm doing a r.los after g.region -pa res=360 it takes 1.719 s to complete the calculation (time taken through the time command). With res=180, res=120, res=90 I get the following table:

res t (s)
--- --------
360 1.72
180 17.96
120 123.68
90 688.37

It scales very badly. Is this expected? Are there better algorithms for calculating LOS then that used in r.los?

Regards,

Peter

2

On Tue, Nov 20, 2007 at 12:46:19PM +0100, Peter Hopfgartner wrote:

Hi,

I've done some time measurements with r.los.

Basically I'm working on a DTM raster of Austria derived from SRTM data.

Thus, the region has a native res of 90m and has 2224 rows and 2228 columns.

If I'm doing a r.los after g.region -pa res=360 it takes 1.719 s to
complete the calculation (time taken through the time command). With
res=180, res=120, res=90 I get the following table:

res t (s)
--- --------
360 1.72
180 17.96
120 123.68
90 688.37

It scales very badly. Is this expected? Are there better algorithms for
calculating LOS then that used in r.los?

I have run valgrind on r.los (NC data set):

GRASS 6.3.cvs (nc_spm_06):~ > g.region -p | grep 'row\|col'
rows: 450
cols: 500
# rather small region!

#valgrind:
CMD="r.los elev_ned_30m out=test coord=642212,224767 obs=165 max=50000 --o"
valgrind --tool=callgrind --trace-children=yes --dump-instr=yes --trace-jump=yes $CMD
kcachegrind callgrind.out.28977

This shows up to 227361 calls to 'find_orientation' (r.los: pts_elim.c).
Not sure but problably there is space for optimization?

Markus

3

Peter Hopfgartner wrote:

I've done some time measurements with r.los.

Basically I'm working on a DTM raster of Austria derived from SRTM data.

Thus, the region has a native res of 90m and has 2224 rows and 2228 columns.

If I'm doing a r.los after g.region -pa res=360 it takes 1.719 s to
complete the calculation (time taken through the time command). With
res=180, res=120, res=90 I get the following table:

res t (s)
--- --------
360 1.72
180 17.96
120 123.68
90 688.37

It scales very badly. Is this expected? Are there better algorithms for
calculating LOS then that used in r.los?

Yes, it is expected that it scales very badly. Just recently a comment was
added to the help page to that effect. To speed it up you can use a cover mask
(patt_map), or try r.cva (GRASS / GEM addons), which has more cover map options
(but is based on the same slow method).

I'd advise updating to GRASS 6.2.3rc or the latest 6.3 cvs to get new fixes for
r.los.

Paul found a faster method to use, see this post from Aug 2003 (RT bug 2061)
  http://article.gmane.org/gmane.comp.gis.grass.devel/1781

the link to the journal article is now dead, but Google Scholar found it:
  http://cat.inist.fr/?aModele=afficheN&cpsidt=14922941

'Photogrammetric Engineering & Remote Sensing' July 2003
'A Fast Algorithm for Approximate Viewshed Computation'
by David Izraelevitz, USACE

Hamish

      ____________________________________________________________________________________
Be a better pen pal.
Text or chat with friends inside Yahoo! Mail. See how. http://overview.mail.yahoo.com/