Geografic-Information-System/raster/r.viewshed/distribute.h

/****************************************************************************
 *
 * MODULE:       r.viewshed
 *
 * AUTHOR(S):    Laura Toma, Bowdoin College - ltoma@bowdoin.edu
 *               Yi Zhuang - yzhuang@bowdoin.edu

 *               Ported to GRASS by William Richard -
 *               wkrichar@bowdoin.edu or willster3021@gmail.com
 *               Markus Metz: surface interpolation
 *
 * Date:         april 2011 
 * 
 * PURPOSE: To calculate the viewshed (the visible cells in the
 * raster) for the given viewpoint (observer) location.  The
 * visibility model is the following: Two points in the raster are
 * considered visible to each other if the cells where they belong are
 * visible to each other.  Two cells are visible to each other if the
 * line-of-sight that connects their centers does not intersect the
 * terrain. The terrain is NOT viewed as a tesselation of flat cells, 
 * i.e. if the line-of-sight does not pass through the cell center, 
 * elevation is determined using bilinear interpolation.
 * The viewshed algorithm is efficient both in
 * terms of CPU operations and I/O operations. It has worst-case
 * complexity O(n lg n) in the RAM model and O(sort(n)) in the
 * I/O-model.  For the algorithm and all the other details see the
 * paper: "Computing Visibility on * Terrains in External Memory" by
 * Herman Haverkort, Laura Toma and Yi Zhuang.
 *
 * COPYRIGHT: (C) 2008 by the GRASS Development Team
 *
 * This program is free software under the GNU General Public License
 * (>=v2). Read the file COPYING that comes with GRASS for details.
 *
 *****************************************************************************/


#ifndef __DISTRIBUTE_H
#define __DISTRIBUTE_H


#include "visibility.h"
#include "grid.h"
#include "eventlist.h"



/* distribution sweep: write results to visgrid.
 */
IOVisibilityGrid *distribute_and_sweep(char *inputfname,
				       GridHeader * hd,
				       Viewpoint * vp,
				       ViewOptions viewOptions);




/* distribute recursively the events and write results to
   visgrid. eventList is a list of events sorted by distance that fall
   within angle boundaries start_angle and end_angle;  enterBndEvents
   is a stream that contains all the ENTER events that are not in this
   sector, but their corresponding Q or X events are in this sector. 

   when problem is small enough, solve it in memory and write results
   to visgrid.

   invariant: distribute_sector deletes eventList and enterBndEvents

   returns the number of visible cells.
 */
unsigned long distribute_sector(AMI_STREAM < AEvent > *eventList,
				AMI_STREAM < AEvent > *enterBndEvents,
				double start_angle, double end_angle,
				IOVisibilityGrid * visgrid, Viewpoint * vp,
				GridHeader *hd, ViewOptions viewOptions);

/* bndEvents is a stream of events that cross into the sector's
   (first) boundary; they must be distributed to the boundary streams
   of the sub-sectors of this sector. Note: the boundary streams of
   the sub-sectors may not be empty; as a result, events get appended
   at the end, and they will not be sorted by distance from the
   vp.  
 */
void distribute_bnd_events(AMI_STREAM < AEvent > *bndEvents,
			   AMI_STREAM < AEvent > *SectorBnd, int nsect,
			   Viewpoint * vp, double start_angle,
			   double end_angle, double *high, long *insert,
			   long *drop);


/* same as above, but does it inemory. it is called when sector fits
   in memory. eventList is the list of events in increasing order of
   distance from the viewpoint; enterBndEvents is the list of ENTER
   events that are outside the sector, whose corresponding EXIT events
   are inside the sector.  start_angle and end_angle are the
   boundaries of the sector, and visgrid is the grid to which the
   visible/invisible cells must be written. The sector is solved by
   switching to radial sweep.  Returns the number of visible cells. */
unsigned long solve_in_memory(AMI_STREAM < AEvent > *eventList,
			      AMI_STREAM < AEvent > *enterBndEvents,
			      double start_angle, double end_angle,
			      IOVisibilityGrid * visgrid, GridHeader *hd,
			      Viewpoint * vp, ViewOptions viewOptions);


/*returns 1 if enter angle is within epsilon from boundary angle */
int is_almost_on_boundary(double angle, double boundary_angle);

/* returns 1 if angle is within epsilon the boundaries of sector s */
int is_almost_on_boundary(double angle, int s, double start_angle,
			  double end_angle, int nsect);

/* computes the number of sector for the distribution sweep;
   technically M/B */
int compute_n_sectors();

/* return 1 is s is inside sector; that is, if it is not -1 */
int is_inside(int s, int nsect);

/* compute the sector that contains this angle; there are nsect
   sectors that span the angle interval [sstartAngle, sendAngle] */
int get_event_sector(double angle, double sstartAngle, double sendAngle,
		     int nsect);


/* insert event in this sector */
void insert_event_in_sector(AMI_STREAM < AEvent > *str, AEvent * e);

/* insert event e into sector if it is not occluded by high_s */
void insert_event_in_sector(AEvent * e, int s, AMI_STREAM < AEvent > *str,
			    double high_s, Viewpoint * vp, long *insert,
			    long *drop);

/**********************************************************************
 insert event e into sector, no occlusion check */
void insert_event_in_sector_no_drop(AEvent * e, int s,
				    AMI_STREAM < AEvent > *str, long *insert);



/* returns 1 if the center of event is occluded by the gradient, which
   is assumed to be in line with the event  */
int is_center_gradient_occluded(AEvent * e, double gradient, Viewpoint * vp);

/* called when dropping an event e, high is the highest gradiant value
   in its sector */
void print_dropped(AEvent * e, Viewpoint * vp, double high);


/* prints how many events were inserted and dropped in each sector */
void print_sector_stats(off_t nevents, int nsect, double *high, long *total,
			long *insert, long *drop,
			AMI_STREAM < AEvent > *sector,
			AMI_STREAM < AEvent > *bndSector, long *bndInsert,
			long longEvents, double start_angle,
			double end_angle);


/* the event e spans sectors from start_s to end_s; Action: update
   high[] for each spanned sector.
 */
void process_long_cell(int start_s, int end_s, int nsect,
		       Viewpoint * vp, AEvent * e, double *high);


/* return the start angle of the i-th sector. Assuming that
   [start..end] is split into nsectors */
double get_sector_start(int i, double start_angle, double end_angle,
			int nsect);


/* return the start angle of the i-th sector. Assuming that
   [start..end] is split into nsectors */
double get_sector_end(int i, double start_angle, double end_angle, int nsect);

/* returns true if the event is inside the given sector */
int is_inside(AEvent * e, double start_angle, double end_angle);

/* returns true if this angle is inside the given sector */
int is_inside(double angle, double start_angle, double end_angle);


#endif