← Back to branch summary

~ubuntu-branches/ubuntu/vivid/grass/vivid-proposed

« back to all changes in this revision

Viewing changes to raster/r.viewshed/distribute.h

  • Committer: Package Import Robot
  • Author(s): Bas Couwenberg
  • Date: 2015-02-20 23:12:08 UTC
  • mfrom: (8.2.6 experimental)
  • Revision ID: package-import@ubuntu.com-20150220231208-1u6qvqm84v430b10
Tags: 7.0.0-1~exp1
* New upstream release.
* Update python-ctypes-ternary.patch to use if/else instead of and/or.
* Drop check4dev patch, rely on upstream check.
* Add build dependency on libpq-dev to grass-dev for libpq-fe.h.
* Drop patches applied upstream, refresh remaining patches.
* Update symlinks for images switched from jpg to png.

Show diffs side-by-side

added added

removed removed

Lines of Context:
raster/r.viewshed/distribute.h
 
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
#ifndef __DISTRIBUTE_H
 
40
#define __DISTRIBUTE_H
 
41
 
 
42
 
 
43
#include "visibility.h"
 
44
#include "grid.h"
 
45
#include "eventlist.h"
 
46
 
 
47
 
 
48
 
 
49
/* distribution sweep: write results to visgrid.
 
50
 */
 
51
IOVisibilityGrid *distribute_and_sweep(char *inputfname,
 
52
                                       GridHeader * hd,
 
53
                                       Viewpoint * vp,
 
54
                                       ViewOptions viewOptions);
 
55
 
 
56
 
 
57
 
 
58
 
 
59
/* distribute recursively the events and write results to
 
60
   visgrid. eventList is a list of events sorted by distance that fall
 
61
   within angle boundaries start_angle and end_angle;  enterBndEvents
 
62
   is a stream that contains all the ENTER events that are not in this
 
63
   sector, but their corresponding Q or X events are in this sector. 
 
64
 
 
65
   when problem is small enough, solve it in memory and write results
 
66
   to visgrid.
 
67
 
 
68
   invariant: distribute_sector deletes eventList and enterBndEvents
 
69
 
 
70
   returns the number of visible cells.
 
71
 */
 
72
unsigned long distribute_sector(AMI_STREAM < AEvent > *eventList,
 
73
                                AMI_STREAM < AEvent > *enterBndEvents,
 
74
                                double start_angle, double end_angle,
 
75
                                IOVisibilityGrid * visgrid, Viewpoint * vp,
 
76
                                GridHeader *hd, ViewOptions viewOptions);
 
77
 
 
78
/* bndEvents is a stream of events that cross into the sector's
 
79
   (first) boundary; they must be distributed to the boundary streams
 
80
   of the sub-sectors of this sector. Note: the boundary streams of
 
81
   the sub-sectors may not be empty; as a result, events get appended
 
82
   at the end, and they will not be sorted by distance from the
 
83
   vp.  
 
84
 */
 
85
void distribute_bnd_events(AMI_STREAM < AEvent > *bndEvents,
 
86
                           AMI_STREAM < AEvent > *SectorBnd, int nsect,
 
87
                           Viewpoint * vp, double start_angle,
 
88
                           double end_angle, double *high, long *insert,
 
89
                           long *drop);
 
90
 
 
91
 
 
92
/* same as above, but does it inemory. it is called when sector fits
 
93
   in memory. eventList is the list of events in increasing order of
 
94
   distance from the viewpoint; enterBndEvents is the list of ENTER
 
95
   events that are outside the sector, whose corresponding EXIT events
 
96
   are inside the sector.  start_angle and end_angle are the
 
97
   boundaries of the sector, and visgrid is the grid to which the
 
98
   visible/invisible cells must be written. The sector is solved by
 
99
   switching to radial sweep.  Returns the number of visible cells. */
 
100
unsigned long solve_in_memory(AMI_STREAM < AEvent > *eventList,
 
101
                              AMI_STREAM < AEvent > *enterBndEvents,
 
102
                              double start_angle, double end_angle,
 
103
                              IOVisibilityGrid * visgrid, GridHeader *hd,
 
104
                              Viewpoint * vp, ViewOptions viewOptions);
 
105
 
 
106
 
 
107
/*returns 1 if enter angle is within epsilon from boundary angle */
 
108
int is_almost_on_boundary(double angle, double boundary_angle);
 
109
 
 
110
/* returns 1 if angle is within epsilon the boundaries of sector s */
 
111
int is_almost_on_boundary(double angle, int s, double start_angle,
 
112
                          double end_angle, int nsect);
 
113
 
 
114
/* computes the number of sector for the distribution sweep;
 
115
   technically M/B */
 
116
int compute_n_sectors();
 
117
 
 
118
/* return 1 is s is inside sector; that is, if it is not -1 */
 
119
int is_inside(int s, int nsect);
 
120
 
 
121
/* compute the sector that contains this angle; there are nsect
 
122
   sectors that span the angle interval [sstartAngle, sendAngle] */
 
123
int get_event_sector(double angle, double sstartAngle, double sendAngle,
 
124
                     int nsect);
 
125
 
 
126
 
 
127
/* insert event in this sector */
 
128
void insert_event_in_sector(AMI_STREAM < AEvent > *str, AEvent * e);
 
129
 
 
130
/* insert event e into sector if it is not occluded by high_s */
 
131
void insert_event_in_sector(AEvent * e, int s, AMI_STREAM < AEvent > *str,
 
132
                            double high_s, Viewpoint * vp, long *insert,
 
133
                            long *drop);
 
134
 
 
135
/**********************************************************************
 
136
 insert event e into sector, no occlusion check */
 
137
void insert_event_in_sector_no_drop(AEvent * e, int s,
 
138
                                    AMI_STREAM < AEvent > *str, long *insert);
 
139
 
 
140
 
 
141
 
 
142
/* returns 1 if the center of event is occluded by the gradient, which
 
143
   is assumed to be in line with the event  */
 
144
int is_center_gradient_occluded(AEvent * e, double gradient, Viewpoint * vp);
 
145
 
 
146
/* called when dropping an event e, high is the highest gradiant value
 
147
   in its sector */
 
148
void print_dropped(AEvent * e, Viewpoint * vp, double high);
 
149
 
 
150
 
 
151
/* prints how many events were inserted and dropped in each sector */
 
152
void print_sector_stats(off_t nevents, int nsect, double *high, long *total,
 
153
                        long *insert, long *drop,
 
154
                        AMI_STREAM < AEvent > *sector,
 
155
                        AMI_STREAM < AEvent > *bndSector, long *bndInsert,
 
156
                        long longEvents, double start_angle,
 
157
                        double end_angle);
 
158
 
 
159
 
 
160
/* the event e spans sectors from start_s to end_s; Action: update
 
161
   high[] for each spanned sector.
 
162
 */
 
163
void process_long_cell(int start_s, int end_s, int nsect,
 
164
                       Viewpoint * vp, AEvent * e, double *high);
 
165
 
 
166
 
 
167
/* return the start angle of the i-th sector. Assuming that
 
168
   [start..end] is split into nsectors */
 
169
double get_sector_start(int i, double start_angle, double end_angle,
 
170
                        int nsect);
 
171
 
 
172
 
 
173
/* return the start angle of the i-th sector. Assuming that
 
174
   [start..end] is split into nsectors */
 
175
double get_sector_end(int i, double start_angle, double end_angle, int nsect);
 
176
 
 
177
/* returns true if the event is inside the given sector */
 
178
int is_inside(AEvent * e, double start_angle, double end_angle);
 
179
 
 
180
/* returns true if this angle is inside the given sector */
 
181
int is_inside(double angle, double start_angle, double end_angle);
 
182
 
 
183
 
 
184
#endif