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