1 2 /**************************************************************************** 3 * 4 * MODULE: r.viewshed 5 * 6 * AUTHOR(S): Laura Toma, Bowdoin College - ltoma@bowdoin.edu 7 * Yi Zhuang - yzhuang@bowdoin.edu 8 9 * Ported to GRASS by William Richard - 10 * wkrichar@bowdoin.edu or willster3021@gmail.com 11 * Markus Metz: surface interpolation 12 * 13 * Date: april 2011 14 * 15 * PURPOSE: To calculate the viewshed (the visible cells in the 16 * raster) for the given viewpoint (observer) location. The 17 * visibility model is the following: Two points in the raster are 18 * considered visible to each other if the cells where they belong are 19 * visible to each other. Two cells are visible to each other if the 20 * line-of-sight that connects their centers does not intersect the 21 * terrain. The terrain is NOT viewed as a tesselation of flat cells, 22 * i.e. if the line-of-sight does not pass through the cell center, 23 * elevation is determined using bilinear interpolation. 24 * The viewshed algorithm is efficient both in 25 * terms of CPU operations and I/O operations. It has worst-case 26 * complexity O(n lg n) in the RAM model and O(sort(n)) in the 27 * I/O-model. For the algorithm and all the other details see the 28 * paper: "Computing Visibility on * Terrains in External Memory" by 29 * Herman Haverkort, Laura Toma and Yi Zhuang. 30 * 31 * COPYRIGHT: (C) 2008 by the GRASS Development Team 32 * 33 * This program is free software under the GNU General Public License 34 * (>=v2). Read the file COPYING that comes with GRASS for details. 35 * 36 *****************************************************************************/ 37 38 /* 39 A grid in ArcInfo Ascii Grid Format 40 */ 41 42 43 #ifndef __GRID_H 44 #define __GRID_H 45 46 #include <stdio.h> 47 #include <limits.h> 48 49 extern "C" 50 { 51 #include <grass/gis.h> 52 #include <grass/raster.h> 53 } 54 55 #define G_SURFACE_TYPE FCELL_TYPE 56 typedef float surface_type; 57 typedef FCELL G_SURFACE_T; 58 59 /* this should accommodate grid sizes up to 2^16-1=65,535 60 If this is not enough, change type and recompile */ 61 typedef unsigned short int dimensionType; 62 static const dimensionType maxDimension = USHRT_MAX - 1; 63 64 65 typedef struct grid_header 66 { 67 dimensionType ncols; /*number of columns in the grid */ 68 dimensionType nrows; /*number of rows in the grid */ 69 double xllcorner; /*xllcorner refers to the western edge of grid */ 70 double yllcorner; /*yllcorner refers to the southern edge of grid */ 71 double ew_res; /*the ew resolution of the grid */ 72 double ns_res; /*the ns resolution of the grid */ 73 surface_type nodata_value; /*the value that represents missing data */ 74 75 struct Cell_head window; 76 } GridHeader; 77 78 79 80 typedef struct grid_ 81 { 82 GridHeader *hd; 83 84 /*two dimensional array holding all the values in the grid */ 85 float **grid_data; 86 87 float minvalue; /*the minimum value in the grid */ 88 float maxvalue; /*the maximum value in the grid */ 89 } Grid; 90 91 92 93 /*copy from b to a */ 94 void copy_header(GridHeader * a, GridHeader b); 95 96 97 /*returns 1 if value is Nodata, 0 if it is not */ 98 int is_nodata(GridHeader * hd, float value); 99 int is_nodata(Grid * grid, float value); 100 101 /* create and return an empty grid */ 102 Grid *create_empty_grid(); 103 104 /*allocate memory for grid data, grid must have a header */ 105 void alloc_grid_data(Grid * grid); 106 107 /*destroy the structure and reclaim all memory allocated */ 108 void destroy_grid(Grid * grid); 109 110 111 #endif 112