More

Considering holes/constraints in Voronoi polygon creation in QGIS?

Considering holes/constraints in Voronoi polygon creation in QGIS?


I am trying to create voronoi polygons in QGIS that would consider "holes" in the general domain. An example would be:

I actually created the Voronois in this image using QGIS through the GRASS command, then using the "Difference" tool to create the holes. A separate polygon shapefile, which contains the extents of the holes, was used as the "Difference" layer. An example application would be creating polygons around sampling points that were collected between structures that should be excluded from the analysis.

Two problems arise here:

  1. The "difference" function does not appear to work 100% properly, with some polygon boundaries extending into the "holes". This can be fixed by finding row in the Attribute Table which do not have a polygon ID number (or ID of "0").

  2. This type of after-the-fact "hole-punching" can result in discontinuous polygons, as shown by the red arrow in the image.

My question is: is there a Voronoi tool or plugin that can consider the presence of "holes" in the center of the domain, as a one-step process, and also eliminate the generation of discontinuous polygons? I envision that such a tool would extend a polygon boundary to the nearest intersection with another boundary, unless that other boundary slams against a "hole" boundary first.


This might be possible using rasters. First convert your points and boundary polygons into a high resolution raster. Set a mask for your boundaries usingr.mask. Then, runr.grow.distancein GRASS and use theValue= output. This will give you for each pixel, which is the closest point. Convert this back into vector polygons. There might be extra steps needed to get rid of sliver polygons.


This is certainly possible with rasters.

This screenshot hopefully shows the issue more clearly. The portion B of the voronoi is closer 'as the crow flies' to the original voronoi centre, but this doesn't take into account the fact that it would take longer to walk around the building. My understanding of the OP's question is that the voronoi needs to take into account this extra distance to walk around the building.

I like the suggestion from @Guillaume. However, when I tried it I had problems gettingr.grow.distanceto honour the mask (see below. The ripples shouldn't pass through the buildings).

My Grass knowledge isn't as strong as it could be, so maybe I'm doing something stupid. Definitely, check out that suggestion first as it'll be a lot less work than mine ;-)

Step 1 - Create a cost surface

First step is to create a cost surface. This only needs to be done once.

  • create an editable layer, holes and all.
  • add a field called 'unit', set it to 1.
  • using polygon-to-raster on your "punched out" vector layer (the one which has the holes), using field 'unit'. You now have a layer "mask", where 1 is free space and 0 is building.
  • use raster calculator to turn this into a cost surface. I'll set 'outdoors' to 1 and 'indoors' to 9999. This will make moving through buildings prohibitively difficult.

    (("[email protected]"=1)*1)+(("[email protected]"=0)*9999)

You can get more 'organic' results by adding a bit of noise to the cost surface (e.g. use random number from 1 to 3, rather than just 1 for outdoor pxiels.)

Step 2. Create cumulative cost rasters for each voronoi center

Now we can run (for one voronoi cell at a time) the GRASS algorithmr.cost.coordinatesagainst our cost surface layer.

For the start coordinate, use the vornoi center. For the end coordinate, choose one of the corners of your area. I suggest using 'Knights Tour' as this gives smoother results.

The result shows lines of equal travel time from one voronoi center. Note how the bands wrap around the buildings.

Not sure how best to automate this. Maybe processing batch mode, or done in pyqgis.

Step 3. Merge down the rasters

This will probably need code. The algorithm would be

create a raster 'A' to match the size of your cumulative cost images fill raster 'A' with a suitably high number e.g. 9999 create an array of the same size as the raster. for each cumulative cost raster number 1… N for each cell in image if cell < value in raster 'A' set value in raster 'A' to cell value set corresponding cell in array to cum. cost image number write out array as a raster

That approach should yield a raster where each cell is categorised by the voronoi center it's closest to, taking into account obstacles.

You could then use raster-to-polygon. You could then use the Generalise plugin to remove the "step" effect artifacts from the raster.

Apologies for vagueness on steps 2 and 3… I'm hoping someone chimes in with a more elegant solution :)


Note #1: I was not able to reproduce the proposed issue because the Difference tool worked well for me in several tests that I performed (maybe it was due to the simple geometry of the issue or because the tool has been improved since the question was asked 1 year ago).

However, I propose a workaround in PyQGIS to avoid the using of the Difference tool. Everything is based on the local intersection between two input layers (see figure below):

  1. a polygon vector layer representing the Voronoi polygons;
  2. a polygon vector layer representing the holes/constraints which need to be excluded from the analysis.

Note #2: Since I don't want to use the Difference tool, I'm not able to avoid the creation of "slivers" (see then), so I needed to run thev.cleantool to eliminate them. Furthermore, as @Chris W said,

[… ] but the second resulting in slivers is not entirely unexpected - after all, that area would still be allocated to the same point even if the hole is present. You could use that method and then incorporate the slivers into their neighbors with a cleanup method.

After these necessary premises, I post my code:

##Voronoi_Polygons=vector polygon ##Constraints=vector polygon ##Voronoi_Cleaned=output vector from qgis.core import * voronoi = processing.getObject(Voronoi_Polygons) crs = voronoi.crs().toWkt() ex = voronoi.extent() extent = '%f,%f,%f,%f' % (ex.xMinimum(), ex.xMaximum(), ex.yMinimum(), ex.yMaximum()) constraints = processing.getObject(Constraints) # Create the output layer voronoi_mod = QgsVectorLayer('Polygon?crs='+ crs, 'voronoi' , 'memory') prov = voronoi_mod.dataProvider() fields = voronoi.pendingFields() # Fields from the input layer prov.addAttributes(fields) # Add input layer fields to the outLayer voronoi_mod.updateFields() # Spatial index containing all the 'constraints' index_builds = QgsSpatialIndex() for feat in constraints.getFeatures(): index_builds.insertFeature(feat) final_geoms = {} final_attrs = {} for feat in voronoi.getFeatures(): input_geom = feat.geometry() input_attrs = feat.attributes() final_geom = [] multi_geom = input_geom.asPolygon() input_geoms = [] # edges of the input geometry for k in multi_geom: input_geoms.extend(k) final_geom.append(input_geoms) idsList = index_builds.intersects(input_geom.boundingBox()) mid_geom = [] # edges of the holes/constraints if len(idsList) > 0: req = QgsFeatureRequest().setFilterFids(idsList) for ft in constraints.getFeatures(req): geom = ft.geometry() hole = [] res = geom.intersection(input_geom) res_geom = res.asPolygon() for i in res_geom: hole.extend(i) mid_geom.append(hole) final_geom.extend(mid_geom) final_geoms[feat.id()] = final_geom final_attrs[feat.id()] = input_attrs # Add the features to the output layer outGeom = QgsFeature() for key, value in final_geoms.iteritems(): outGeom.setGeometry(QgsGeometry.fromPolygon(value)) outGeom.setAttributes(final_attrs[key]) prov.addFeatures([outGeom]) # Add 'voronoi_mod' to the Layers panel QgsMapLayerRegistry.instance().addMapLayer(voronoi_mod) # Run 'v.clean' processing.runalg("grass7:v.clean",voronoi_mod, 2, 0.1, extent, -1, 0.0001, Voronoi_Cleaned, None) # Remove 'voronoi_mod' to the Layers panel QgsMapLayerRegistry.instance().removeMapLayer(voronoi_mod)

which leads to this result:

Just for clearness, this would be the result without the using of thev.cleantool:

The difference with the result by @LeaningCactus is that, by now, the geometries are not broken and they could be "cleaned" without errors.


Triangulate polygon matching Delaunay property

I want to triangulate a polygon (without selfintersection, but with holes and the polygon can also be concav). In this question (e.g.): Delaunay triangulating the 2d polygon with holes a Constrained Delaunay Triangulation is proposed. What I was wondering about: is this the best way to do so or is it like "using a sledge-hammer to crack a nut"? An alternativ would be to use an algorithm for creating a "normal" triangulation (eg splitting the polygon in y-monoton parts and triangulate these parts) and flipping the edges afterwards. But it seams that (nearly) nobody takes this solution. Is there a reason? What are the pros and cons for one of these solutions? (the polygons can have an arbitrary size)


de Berg, M., van Kreveld, M., Overmars, M., & Schwarzkopf, O. (1997). Computational geometry: Algorithms and applications. Springer.

Ester, M., Kriegel, H., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the second international conference on knowledge discovery and data mining (pp. 226–231). Portland, OR.

Estivill-Castro, V., & Lee, I. J. (2000a). AUTOCLUST: Automatic Clustering via boundary extraction for mining massive point-data sets. In Proceedings of the fifth international conference on geocomputation (pp. 23–25). Medway Campus, UK: University of Greenwich.

Estivill-Castro, V., & Lee, I. J. (2000b). AUTOCLUST+: Automatic clustering of point-data sets in the presence of obstacles. In Proceedings of the International Workshop on Temporal, Spatial and Spatio-Temporal Data Mining (pp. 133–146). Lyon, France.

Gao, Y., & Zheng, B. (2009). Continuous obstructed nearest neighbor queries in spatial databases. SIGMOD, 577–590.

Lee, C. H. (2002). Density-based clustering of spatial data in the presence of physical constraints. Master’s Thesis. University of Alberta, Edmonton, Canada.

Malerba, D., Appice, A., Varlaro, A., & Lanza, A. (2005). Spatial clustering of structured objects. ILP, 227–245.

Ng, R., & Han, J. (1994). Efficient and effective clustering method for spatial data mining. In Proceedings of the Twentieth International Conference on Very Large Data Bases (pp. 144–155). Santiago, Chile.

O’Rourke, J. (1998). Computational geometry in C (2nd ed.). New York: Cambridge University Press.

Sander, J., Ester, M., Kriegel, H., & Xu, X. (1998). Density-based clustering in spatial databases: the algorithm GDBSCAN and its applications. Data Mining and Knowledge Discovery, 2(2), 169–194.

Tung, A. K. H. , Han, J., Lakshmanan, L. V. S. , & Ng, R. T. (2001a). Constraint-based clustering in large databases. In Proceedings of the Eighth International Conference on Database Theory (pp. 405–419). London, UK.

Tung, A. K. H. , Hou, J., & Han, J. (2001b). Spatial clustering in the presence of obstacles. In Proceedings of the Seventeenth International Conference On Data Engineering (pp. 359–367). Heidelberg, Germany.

Wang, X., & Hamilton, H. J. (2003). DBRS: A density-based spatial clustering method with random sampling. In Proceedings of the Seventh Pacific-Asia Conference on Knowledge Discovery and Data Mining (pp. 563–575). Seoul, Korea.

Wang, X., & Hamilton, H. J. (2005). Clustering spatial data in the presence of obstacles. International Journal on Artificial Intelligence Tools, 14(1–2), 177–198.

Zaïane, O. R. , & Lee, C. H. (2002). Clustering spatial data when facing physical constraints. In Proceedings of the IEEE International Conference on Data Mining (pp. 737–740). Maebashi City, Japan.

Zhang, B., Ying, W., Xie, M., & Dong, J. (2007). Geo-spatial clustering with non-spatial attributes and geographic non-overlapping constraint: a penalized spatial distance measure. PAKDD, 1072–1079.


Perspective transformation of a 2d streamplot

I have a two-dimensional streamline plot from a fluid dynamics simulation. I am wondering: is it possible to somehow allow Mathematica to treat the streamline plot as a plane in three-dimensional plot so that I can apply a camera perspective transformation to the resulting three-dimensional plot?

To provide a bit more information, I have three-dimensional scenes (an example of which is shown below) for which I am running fluid dynamics simulations. As a result of these simulations, I obtain a series of two-dimensional windflow velocity fields, which are cross-sections of the true three-dimensional windflow velocity fields. These fields quantify the direction and speed of the wind through the environment subject to the geometry constraints of the scene and some user-defined parameters and boundary conditions.

For visualization purposes, I'm interested in transforming and overlaying one or more of the two-dimensional streamline plots of the velocity fields onto my three-dimensional scene such that the two-dimensional streamline plot takes the place of the red plane in the image below. Although I could simply rasterize the streamline plot, treat it as a texture for the plane, and render the scene in 3DS Max, I'm hoping to overlay the streamline plots as vector graphics.

Addendum: As per Yves' suggestion, I have supplied a subsampled version of the windflow velocity field that I am using for my plots. Using his wonderful script, I am able to take a two-dimensional streamline plot and rotate/scale it as if it was a three-dimensional plot.

ListStreamPlot[data, StreamPoints -> Fine][[1]] /. Arrow[pts_] :> Arrow[ <#[[1]], 0, #[[2]]>& /@ pts] // Graphics3D

The only remaining question that I have is: how can I change the camera perspective parameters of the plot? Specifically, I would like change the perspective of the three-dimensional streamline plot such that the bounding box around the plot takes the shape of a trapezoid and the streamline trajectories are modified accordingly. I am aware that Graphics3D has ViewAngle , ViewPoint , and ViewVector options, but I am unsure as to how to use them in the context of Yves' script.


Considering holes/constraints in Voronoi polygon creation in QGIS? - Geographic Information Systems

All articles published by MDPI are made immediately available worldwide under an open access license. No special permission is required to reuse all or part of the article published by MDPI, including figures and tables. For articles published under an open access Creative Common CC BY license, any part of the article may be reused without permission provided that the original article is clearly cited.

Feature Papers represent the most advanced research with significant potential for high impact in the field. Feature Papers are submitted upon individual invitation or recommendation by the scientific editors and undergo peer review prior to publication.

The Feature Paper can be either an original research article, a substantial novel research study that often involves several techniques or approaches, or a comprehensive review paper with concise and precise updates on the latest progress in the field that systematically reviews the most exciting advances in scientific literature. This type of paper provides an outlook on future directions of research or possible applications.

Editor’s Choice articles are based on recommendations by the scientific editors of MDPI journals from around the world. Editors select a small number of articles recently published in the journal that they believe will be particularly interesting to authors, or important in this field. The aim is to provide a snapshot of some of the most exciting work published in the various research areas of the journal.


Hole Detection for Quantifying Connectivity in Wireless Sensor Networks: A Survey

Owing to random deployment, environmental factors, dynamic topology, and external attacks, emergence of holes in wireless sensor networks is inescapable. Hole is an area in sensor network around which sensors cease to sense or communicate due to drainage of battery or any fault, either temporary or permanent. Holes impair sensing and communication functions of network thus their identification is a major concern. This paper discusses different types of holes and significance of hole detection in wireless sensor networks. Coverage hole detection schemes have been classified into three categories based on the type of information used by algorithms, computation model, and network dynamics for better understanding. Then, relative strengths and shortcomings of some of the existing coverage hole detection algorithms are discussed. The paper is concluded by highlighting various future research directions.

1. Introduction

A wireless sensor network is a network that is made of hundreds or thousands of sensor nodes which are densely deployed in an unattended environment with the capabilities of sensing, wireless communications, and computations [1]. Sensor nodes are tiny, low power devices equipped with processor, memory, radio, actuator, and power supply. Radio transmitters and receivers help sensor nodes to communicate with each other.

Some of the challenges in WSNs are node deployment, energy consumption, node heterogeneity, data aggregation, and fault tolerance [2]. Hole detection is one of the major problems in WSN. Holes affect the network capacity and perceptual coverage of the network. Due to limited battery the nodes may die with passage of time. In case of random deployment, there is a huge possibility that all areas of target region are not covered properly leading to formation of holes. Detection of holes is important because of their negative and damaging effects.

WSNs have myriad of interdisciplinary applications such as weather forecasting, battlefield surveillance, threat identification [3], health monitoring [4], environment monitoring [5], and wild life monitoring. All those applications that demand random deployment and uncontrolled environment suffer from holes problem [6]. Thus, hole detection can be useful for all disciplines of sciences and engineering.

The rest of the paper is organized as follows. Section 2 discusses different types of holes in WSNs and importance for hole detection algorithms. Section 3 proposes a novel taxonomy of coverage hole detection algorithms and reviews some of the existing coverage hole detection algorithms referring to taxonomy. Conclusions and future research directions are presented in Section 4.

2. Holes in WSN

An area where a group of sensor nodes stops working and does not take part in data sensing and communication is termed as a hole in the network [7]. Holes are the barriers for communication. Holes have a huge impact on the performance of the network. Hole detection identifies damaged, attacked, or inaccessible nodes. If there is a hole in the network then data will be routed along the hole boundary nodes again and again which will lead to premature exhaustion of energy present at these nodes [8]. This will ultimately increase the size of hole in the network. Detection of holes avoids the additional energy consumption around holes because of congestion. It assures long network life and adequate quality of service.

One of the most prominent problems in wireless sensor networks is detection of network boundary, that is, the nodes that are present on the boundary of network and hole boundary [7], that is, the nodes that surround a hole as shown in Figure 1.


Holes can be classified with respect to their mobility (mobile or static), lifetime (persistent or temporary), purposes (intentional or unintentional), affected function (functional or nonfunctional), and cause of anomaly [9] as shown in Figure 2. Holes formed in static sensor network are called static holes. Mobile nodes create and break connections while moving, thus creating mobile holes. External events such as wildfire or heavy rain destroy sensor nodes in an area leading to formation of persistent holes. Inefficient sleep wake-up scheduling of sensor nodes can form temporary holes in the target region. Unintentional holes are formed when a node accidently lacks some physical capabilities. Intentional holes are formed when some part of target field is not sensed by any node because nodes in that area are intentionally scheduled to be in sleep state to save energy. If, due to failure of some nodes sensing, communication and processing tasks of sensor network are affected, then the corresponding hole formed is functional hole. On the other hand if some nonfunctional tasks such as security are affected then nonfunctional holes are formed.


Jabeur et al. [9] discussed PLMS (physical/logical/malicious/semantic), a cause-based taxonomy in detail, where sensor holes are studied from a cause-effect-solution perspective. Semantic holes mainly relate to collection, processing, and routing of data. Some of the reasons for their formation are inaccurate data collection and absence of specialized sensors. Logical holes are created due to cluster based approaches where a sensor node may not get support from its neighbors belonging to the same cluster. Physical holes may arise due to limited processing capabilities of sensor nodes called processing holes, through excessive consumption of energy at some nodes leading to formation of energy holes, or due to limited sensing range of nodes creating sensing holes. Coverage and routing holes come under physical holes category. Coverage holes are the result of unplanned deployment of nodes because of which target area is not covered properly. They may also occur due to changing topology due to which some sensor nodes may move over time leading to coverage holes. Routing holes occur in wireless sensor networks if either there is insufficient number of nodes or the nodes that are available cannot take part in routing [10]. These holes have a direct effect on the routing performance of the network. These holes mostly occur in geographic greedy forwardingbecause of local minimum phenomenon.

Holes formed by malicious behavior of some nodes in the network are called malicious holes. Further categorization of malicious node includes jamming, sink, and trust holes. Jamming holes occur if some high frequency signals block the radio frequency used for communicating by sensor nodes. Denial of service attacks causes Sink/black holes [11] where an adversary announces attractive routes to sink and thus succeeds in deceiving other nearby nodes which may select this node as their next hop. Trust hole is a new type of holes proposed by author that comes under malicious holes category. Sensors assign weighted trust values based on different parameters to their neighbors. Trust weight threshold values are application dependent. We can see a trust hole in Figure 3, delimited by sensors having weight values less than or equal to 0.5.


Out of all the types of holes discussed so far, coverage holes are the most important to detect as they play a vital role in assuring good QoS. They help us to identify whether each point in sensing field has the required degree of coverage or not. They are the indicators of general health of sensor networks and help in identifying geographic characteristics of target region [12]. Hole boundaries can determine areas of interest like fire, flood, or earthquake. They help us to find out locations where more nodes need to be deployed and thus assist in patching the holes. Hole detection ensures reliability by preventing data loss.

Coverage hole detection aids in identifying alternative communication pathways and assists in regulating data traffic flow. Absence of hole detection algorithms will eventually cause problems in routing. Thus, the rest of the paper is focused on identifying different ways to detect coverage holes in sensor networks.

3. Taxonomy of Coverage Hole Detection Algorithms

There has been a large body of research on detection of coverage holes in WSNs over the last few years. In Figure 4, coverage hole detection algorithms have been classified into different categories: (A) based on the type of information used, (B) based on computational model, and (C) based on network dynamics. In this section, we analyze and summarize some of the typical hole detection algorithms of each category.


3.1. Approaches Based on Type of Information Used

The efforts invested so far in the field of coverage hole detection based on the type of information used by the algorithms can be divided into three approaches, namely, topological, statistical, and geometrical approaches [13].

3.1.1. Geographical Approach

This approach assumes that exact location of sensor nodes is known beforehand. Each node knows its location either with the help of special location hardware such as GPS [12] or by using scanning devices, thereby increasing size and structure of sensor nodes. It is also known as location based approach.

Yang and Fei [14] proposed a hole detection and adaptive geographical routing (HDAR) algorithm to detect holes and to use this information to deal with local minimum problem. If the angle between two adjacent edges of a node is greater than 120 degrees, then it begins hole detection algorithm. Here, the ratio of network distance over the Euclidean distance is used as metric to detect a hole that is, Length_pro

/dist_euc is the hole detection ratio. If for a node the value of hole detection ratio is greater than a predefined threshold, then it is on boundary. One of the main advantages is that a single node can efficiently detect the hole. After detecting hole, it advertises this information to nodes in vicinity which can adaptively adjust the forwarding direction.

3.1.2. Topological Approach

Also called as connectivity based approach, it uses only the available connectivity information of network to detect holes [13]. This approach requires no location information and works even for dense networks. There is no assumption about node distribution. One of the algorithms based on topological approach to detect coverage holes within wireless sensor networks was given in [15] and later improved in [16]. Authors proposed a distributed cooperative scheme based on the fact that nodes at the hole or network boundary have smaller degrees than interior nodes. It deals with static, uniformly distributed nodes with each node having a unique id. If the degree of a node is lower than the average degree of its 2-hop neighbors, then it makes a decision whether it is on hole boundary or not. If yes, then it sends messages informing its status to its 1-hop neighbors who may also be on hole boundary. The algorithm is scalable, but approach produces poor results for randomly deployed dense networks. If there are not sufficient nodes surrounding a hole then output produced is not accurate.

Martins et al. [17] used the concepts of Rips complex and Cech complex to discover coverage holes. If communication radius is greater than or equal to twice the sensing radius and there is a hole in Rips complex, then there must be a hole in Cech complex. Authors classified holes to be either triangular or nontriangular. The distributed algorithm proposed by authors is capable of detecting nontriangular holes and the area of triangular holes. After constructing neighbor graph, each node checks whether there exists a Hamiltonian cycle in graph. If not, then node is on the hole boundary. After making decision, each node broadcasts its status to its neighbors. The algorithm further finds cycles bounding holes.

Zeadally et al. [18] proposed a hop based approach to find holes in sensor networks. There are three phases, namely, information collection phase where each node exchanges information to build a list of x-hop neighbors, path construction phase where communication links between sensor nodes in list of x-hop neighbors are identified, and finally path checking phase where paths are examined to infer boundary and inner nodes. If the communication path of x-hop neighbors of a node is broken, then it is boundary node. Algorithm works for node degree of 7 or higher which is better than some of the other approaches, but there is a huge communication overhead involved to identify x-hop neighbors.

Chu and Ssu [19] proposed a decentralized boundary detection (DBD) algorithm to identify sensor nodes near a hole or obstacle in WSN using topological approach. Each node knows its three-hop neighbors by exchanging HELLO messages and one-hop and two-hop node information. There is no UDG constraint. Each node then constructs 2-hop neighbor graph. If cycle exists in such a graph, then there is a hole in network. For dealing with hole which is not included totally inside 2-hop neighbor graph, another rule based on contour structure was developed. Detection of broken contour line implies either network boundary or an obstacle.

There are very few algorithms that can detect boundaries of small holes. Dong et al. [20] proposed a distributed algorithm that can accurately detect boundaries of small holes in the network. The first step of algorithm is to reduce the connectivity graph by using vertex deletion and edge deletion so as to obtain a skeleton graph. Thereafter, skeleton graph is further partitioned to get coarse inner boundary cycles. Each cycle either encloses a hole of graph or corresponds to outer boundary. The coarse outer boundaries are then further refined to get fine grained boundary cycles. There is no assumption related to node density. The authors further proved the correctness of hole detection.

3.1.3. Statistical Approach

Some statistical function is applied on data collected from neighboring nodes and then a Boolean function decides whether nodes are at hole boundary or not. It is based on the assumption that distribution of nodes follows some statistical function. There is no need of GPS, but it requires high node density that is, average degree must be 100 or higher [21]. In practice, such dense uniform deployment is not practical. The concept used by Fekete et al. [21] is that boundary nodes have lower average degrees than interior nodes. Average density is the metric used to detect holes where actual node degree is compared with a predefined threshold value to infer its position. Another metric used by Fekete et al. [21] is centrality index, where high value is assigned to inner nodes and less value to outer nodes.

Discussion. We have considered many algorithms under different categories each having its own limitations. Geometrical approach for hole detection requires GPS enabled sensor and is expensive. They consume a lot of energy and it is not practical for sensors to know their exact location in hostile environment. Considering huge applications of WSN, these approaches have limited scope. Statistical approaches provide optimal performance, but they are computationally expensive. Owing to the challenges in wireless sensor networks it is not desirable that nodes perform complex mathematical and statistical calculations [13]. Topological approach provides realistic results but involves communication overhead. Some of the algorithms do not work for small network degrees.

3.2. Algorithms Based on Computational Model

On the basis of computational model used, coverage hole detection algorithms can be classified into two categories, namely, centralized and distributed.

3.2.1. Centralized

Centralized algorithms run on one or more nodes at centralized location. Bldg and Funke [28] presented a centralized hole detection algorithm based on connectivity information of the network. Authors select a set of nodes and then identify whether isolevels generated from each node are broken or continuous. Algorithm is based on the fact that isolevels are always broken at either the network boundary or the hole boundary. It identifies the nodes near boundaries but gives no idea of how they might be connected. Moreover, it requires dense deployment. Ghrist and Muhammad [25] have introduced a centralized technique for detecting coverage holes based on homology, an algebraic topology variant. It uses only available connectivity information to detect single level coverage holes. Time complexity is

, with being the number of nodes. Approach gives no guarantee to detect hole boundary accurately.

3.2.2. Distributed

In decentralized algorithms, multiple nodes work together to efficiently detect hole in the network resulting in uniform division of workload. Senouci et al. [24] proposed a hole detection and healing (HEAL), a distributed and localized algorithm which can detect coverage holes using distributed coverage hole detection and can heal the detected holes using virtual forces concept. Attractive and repulsive forces act inside hole healing area (HHA) to recover from holes without any side effects. The computational complexity of this algorithm is

, where is the average number of 1-hop neighbors. HEAL deals with holes of various forms and sizes and provides cost effective and accurate solution for hole detection and healing. Kröller et al. [30] developed a distributed algorithm to detect holes in large sensor networks using quasiunit disk graph. Algorithm does not perform well in sparse networks where identification of even one flower is difficult.

Wang et al. [27] presented a simple, distributed boundary recognition algorithm based on repetitive network flooding. Nearest common ancestors (NCA) are used to detect holes. In Figure 5, node r is the nearest common ancestor of nodes p and q. Algorithm builds the shortest path tree rooted at some arbitrary nodes. Nodes where shortest paths of distinct homotopy types meet past the hole are called cut nodes.


After determining cuts in shortest path tree, coarse inner boundary which is a shortest cycle enclosing the composite hole is detected. Network is then flooded with shortest cycle to identify external nodes, that is, nodes whose hop counts to cycle are locally maximal. Finally coarse inner boundary is refined. There is no UDG constraint. Huge communication overhead is involved for synchronizing nodes before tree is constructed. Moreover, algorithm fails if there are multiple adjacent holes.

On the basis of nodes that invoke hole detection algorithm, we can further classify distributed algorithms into two categories, namely, local detection and global detection. A hole occurs when several adjacent nodes in sensor network fail and is defined as the convex hull of the region containing failed sensors [22]. Holes affect their immediate neighbors, as well as remote nodes whose routing options are reduced. Based on the nodes which invoke hole detection algorithm, there are two categories of hole detection algorithms, namely, local detection and global detection. In local detection, nodes that are immediately affected by the hole initiate hole detection algorithm. However, in global detection, hole is detected by a node that is far away and is not affected directly by damage caused by hole.

(a) Local Detection. Corke et al. [22] presented, analyzed, and implemented two distributed algorithms for hole detection. In local detection, node initialization phase is necessary to know about initial connectivity state. In the initialization phase, each node sends out a ping requesting neighbor information. Nodes that reply with their id are added to the list of neighbors. Neighbors are then pinged periodically to verify integrity of network. If neighboring node gives no response to pinged message, then it is regarded as dead. When dead count exceeds dead threshold, then node marks itself as sitting on damage perimeter. During damage extent computation, each node finds out the overall convex hull incrementally by calculating convex hulls at each node and sharing the hulls until there are no further changes to the hull set. Wang et al. [27] have developed a distributed algorithm where each node first checks whether it is a stuck node or not using TENT rule. If a node is closer to target than all its 1-hop neighbors, then it is a stuck node. The stuck nodes are marked as hole boundary nodes. Boundhole algorithm then builds routes around hole boundary to route packets. Approach needs only angle information within its 1-hop neighbors therefore detection is local.

(b) Global Detection. In global method, routing information is used to detect the holes. In paper [22], path density is the metric used to detect presence of holes. Each node randomly broadcasts a diagnostic packet containing source coordinate, destination coordinate, previous coordinate, distance travelled, and message id. Distance travelled and previous coordinate are updated at each hop. Message id is used to ignore duplicate messages. When message reaches destination, path density is calculated as the ratio of straight line distance from source to destination to actual distance travelled. Low ratio implies that a hole exists in the network.

Discussion. Limited storage is one of the challenges of sensor networks thus, algorithms that collect whole data at some node to perform centralized computations are infeasible. Centralized approach suffers from problem of single point of failure. Due to dynamic topology and exogenous disturbances, WSNs need dense deployment. Protocols designed for such dense networks should be distributed in order to accommodate scalable architecture. Centralized algorithms consume more energy to achieve higher percentage of hole area recovered as compared to distributed algorithm. On the other hand, distributed algorithms are more complex than centralized as they need to run on many nodes throughout the network. Global approach helps to overcome ambiguity often faced by local detection. Local detection algorithms run periodically to give information about health of sensor network. They can be used to look for changes from initial state.

3.3. Algorithms Based on Network Dynamics

Algorithms discussed in this section are classified based on network dynamics in sensor network as static sensors, mobile sensors, and hybrid sensors.

3.3.1. Static Sensors

Li et al. [34] proposed 3MeSH (triangular mesh self-healing hole detection algorithm), which is a distributed coordinate-free hole detection algorithm. It is assumed that each node has uniform sensing radius R and communication radius 2R. Initially a subset of active nodes is selected. An active node x is neighbor of active node y if they are between R and 2R distance apart. Nodes that lie within the sensing range of an active node are called redundant nodes. Connectivity information is collected by each active node from its neighbors. If node detects presence of 3MeSH ring as shown in Figure 6 defined by all its neighbors, then it is a boundary node. For detecting large holes, nodes are allowed to collect connectivity information from nodes further away but at the cost of increased complexity. 3MeSH-DR is an improved version of 3MeSH algorithm presented in [31].


3.3.2. Mobile Sensors

Mobile sensor nodes can move around after initial deployment. The main objective in mobile WSN is to maximize coverage. Topology of sensor network is affected by mobile nodes as they form new connections and break old ones. If the coverage area of a node can be covered by its neighboring node, then only a node can move to another area. In [26], authors have used Voronoi diagrams to detect coverage holes. Voronoi diagram is a diagram of boundaries around each sensor such that every point within sensor’s boundary is closer to that sensor than any other sensor in the network [35]. Figure 7 shows a Voronoi cell. Nodes P, Q, R, S, and T are Voronoi neighbors of X and a, b, c, d, and e represent Voronoi edges. These edges are the vertical bisector of line connecting X to its Voronoi neighbors.


A polygon constructed from all these Voronoi edges is called Voronoi cell of node X. We can see a Voronoi diagram in Figure 8.


To detect hole, each node checks whether its Voronoi polygon is covered by its sensing area. If not, then coverage hole exists. After detecting hole, one of the three proposed algorithms is used to find target location where a mobile node is to be moved so as to heal the hole. In vector based algorithm (VEC), sensor nodes are pushed from dense regions to sparse regions so that nodes are evenly distributed. Voronoi based algorithm (VOR) is a pull algorithm which pulls nodes towards sparse regions. In minimax algorithm, target location is at the center of its Voronoi polygon. Minimax algorithm achieves maximum coverage at the cost of increased computational overhead.

Zhao et al. [32] proposed a coverage hole detection method (CHDM) by mathematical analysis. It is assumed that network consists of mobile nodes each with sensing radius r and communication radius 2r. A node p is defined as neighbor of node q if it lies in its communication range. On the basis of central angle between neighbor sensors, the authors presented different cases to find coverage holes in communication circle around a redundant movable node. To patch hole, a redundant node is moved to an appropriate position inside the hole.

3.3.3. Hybrid Sensors

Hybrid WSNs consist of both stationary and mobile nodes. Mobile nodes help in healing the coverage holes created by stationary nodes. Babaie and Pirahesh [29] presented a triangular oriented diagram to detect a hole. The authors connected the center of three adjacent sensors to produce triangle and further presented various possibilities of occurrence of holes and then calculated the area which is not covered by any of them. This uncovered area is coverage hole. To patch the coverage hole, a mobile node is moved to incenter or circumcenter depending on whether hole area is more or less than sensing region, respectively. The approach is simple as compared to Voronoi diagram construction. Moreover, it can determine exact area of hole.

Wang et al. [33] proposed a distributed bidding protocol for detecting coverage holes in hybrid sensor networks. Mobile nodes act as hole healing server with certain base price initially set to zero. Base price is the estimate of new coverage hole generated when a mobile node moves to new target location for healing purpose. During advertisement phase, mobile sensors broadcast their locations and base price. In bidding phase, static sensors examine their respective Voronoi cell to detect coverage holes locally. If hole exists, it estimates its size and determines target position inside the hole. Static nodes then calculate the bid using formula

, with being the distance between target location and the node that wants to bid. Static sensors send bidding message to the nearest mobile sensor whose base price is less than its bid. Each mobile node compares the received bids and chooses the message with highest bid and moves to the target location specified in message. This bid becomes new base price of mobile node. This process stops when the bid of any static sensor is not higher than the base price of any mobile sensor.

Discussion. The probability of the formation of hole in a high density network is less. Therefore, for dense networks static sensor networks are preferred while in case of sparse density, hybrid and mobile sensor networks give better coverage. Some of the nodes in hybrid and mobile networks can move to patch the coverage holes, thereby improving the network connectivity. Sensors moved through a long distance will consume more energy. If energy of a sensor is so less that it dies shortly after being relocated to target region, then this effort is wasted. Therefore, moving and messaging cost must be kept at minimum while dispatching mobile nodes to target locations in hybrid and mobile sensor networks.

4. Summaries and Outlook

In this paper, taxonomy is proposed which gives an exhaustive classification of coverage hole detection algorithms. In the last few years, many innovative ideas have been provided by researchers to solve coverage hole detection problem in WSNs, but research in this direction is still in growing phase. Table 1 summarizes the characteristics of various coverage hole detection algorithms in aspect of approach used, computational model, network dynamics, detection level, and simulation environment. From Tables 2 and 3, it can be seen that each algorithm has its own strengths and shortcomings, but none is absolutely the best. Table 4 discusses some of the application suggestions for coverage hole detection algorithms.


Discussion

An ecological interpretation of why birds were feeding at locations with greater time-integrated habitat availability

Little Blue Herons and Great White Herons used foraging locations nonrandomly and patterns of use at the 5-km spatial scale were best explained by time-integrated habitat availability. Both species were two to three times more likely to use foraging locations with greater (7 h) time-integrated habitat availability than nearby locations with lower (1 h) time-integrated habitat availability. In addition, locations where Little Blue Herons were observed foraging had a population-averaged time-integrated habitat availability of

6.5 h, and locations where Great White Herons were observed foraging had even greater values (

8 h of availability). We propose that energetics and distributional relationships between predators and prey are directly related to time-integrated habitat availability.

Theoretical foraging models suggest that residence time in a patch will increase as the travel cost between patches increases (Bernstein et al. 1991 ), but time spent foraging is also dependent on the availability and the rate of depletion of food (van Alphen et al. 2003 ). It is therefore reasonable to assume that moving large distances in search of alternate foraging locations is a risky strategy during tidal fluctuations. In fact, dynamic variables (distance to deep water and water depth) were present in the top models of both species at the 500-m spatial scale analysis, suggesting an importance of these dynamic variables, which provides support that the statistical model is successfully capturing a response of foraging birds to changes in the environment over the tidal cycle there was only support for the static variables (distance to island and time-integrated habitat availability) in the statistical models at the 5-km spatial scale analysis and no evidence that the dynamic variables improved the models. Most of the birds, once at a feeding location, displayed only localized prey-searching movements (<500 m L. Calle and D. E. Gawlik, personal observation) and continued feeding during the entirety of the low tide, which is consistent with Little Blue Heron feeding behavior during low tides in Brazil (Moralez-Silva et al. 2010 ). Presumably, this behavior was due to the high cost of large-scale (>500 m) movements to find alternate feeding locations as the tides can change the areal extent of available feeding locations by more than an order of magnitude in short time periods (Calle et al. 2016 ). The relatively stationary behavior of feeding herons may suggest that the travel cost during tides is too high or that prey depletion was negligible. Our work suggests that wading birds were feeding at locations with greater time-integrated habitat availability to more efficiently meet energetic demands by reducing the time spent moving and tracking changes in water depths.

Although we did not quantify the distribution of fishes over the full tidal cycle, it is likely that prey were more available to the birds during low tides and less available at other times (Lekuona 1999 , Matsunaga 2000 , Regós 2011 ). Other researchers have observed a quadratic increase in the strike rates and capture rates of wading birds feeding at low tides, declining rapidly during ebb and flood portions of the tide (Moralez-Silva et al. 2010 , Regós 2011 ), suggesting that either prey densities are greater or prey are more vulnerable to capture during low tides. We suggest that an increased duration of access to foraging habitat (i.e., greater time-integrated resource availability) helps avian predators meet their energetic demands.

The total duration a location has shallow water might also serve a dual purpose in this system by providing habitat for small or juvenile fishes, and by logical extension, an increase in wading bird prey. The numerical response of fishes to tidal fluctuations is species specific (Ellis and Bell 2008 ), with the maximum abundance of some species occurring during high-, low-, or mid-tides. Yet, there appears consensus that the abundance of small fishes is generally higher in shallower water than in deeper water (Nagelkerken et al. 2000 , Whitfield 2017 ). Although Great White Herons do take large fishes (L. Calle, personal observation), the majority of the prey fish are small (<12 cm L. Calle, unpublished data), and studies of the similar-sized Grey Heron (A. cinera) also found that small prey fish were the norm (Gwiazda and Amirowicz 2006 , Regós 2011 ). Furthermore, many species remain in the intertidal zone at low tide even when surface water is temporarily absent as some fishes are well-adapted to survival out of water by air breathing (Martin 1995 ) and by modified nitrogen metabolism (e.g., toadfish and gobies Walsh and Milligan 1995 ). However, exposure of the seafloor to air was not common for large expanses on the tidal flats in our study area (L. Calle, personal observation) and persistent shallow water could be suitable refuge for small fishes that cannot survive out of water (Nagelkerken et al. 2000 , Baker and Sheaves 2007 , Ryer et al. 2010 ).

In fact, if shallow-water (<1 m) exists on tidal flats for the majority of a tidal cycle, these locations could be important areas of refuge for small or juvenile fishes to escape lethal and sublethal effects by aquatic predators (Ruiz et al. 1993 , Baker and Sheaves 2007 , Ryer et al. 2010 ). In a focal study of a single tidal flat over a full tidal cycle, we did not observe edge-following feeding behavior or perceptible differences in feeding locations relative to ebb and flood tides (L. Calle, unpublished data), which suggests that there was not a large concentration of fishes at the leading edge of tidal inundation. However, we also found in this study that, at the 500-m spatial scale of resource selection, the probability of use decreased by 1.8–3.4-fold at a distance of 200–300 m from deep water (>1 m). The apparent preference for locations close to deep water might suggest that prey fishes were moving on and off tidal flats during the tides (Gibson 2003 ) in a pattern that does not aggregate the prey at the tidal flat margins, or where the effects of movement on and off the tidal flats do not extend far beyond the deep water. Topographical features, such as channel morphology might also play a role in fish movement. The prediction that the distribution and abundance of small fishes is a function of the average duration a habitat has shallow-water (<1 m) would need to be verified by field studies. We suggest that wading birds in intertidal systems have converged upon a pattern of use that is dually influenced by (1) the high cost of movement and limited time of access to feeding habitat during tides and also influenced by (2) ecosystem dynamics that result in a dual-purpose benefit for small fishes.

Is there evidence that traditional habitat attributes explain patterns of resource use?

The benthic factors considered in this analysis (i.e., seagrass percent cover and benthic substrates) did not explain patterns of habitat use in our study, but these factors are most likely crucial to modifying patterns of small fish distributions (Matsunaga 2000 , Ellis and Bell 2004 ). Hurricanes (Fourqurean and Rutten 2004 ) and nutrients (Lapointe et al. 2004 , Green et al. 2015 ) may modify the benthic conditions of foraging locations, and thereby affect patterns of habitat use by birds. Even still, the benthic attributes are relatively static and unchanging over time scales relevant to wading bird foraging decisions. As such, the fact that vegetation and substrate did not contribute to habitat use models was not surprising.

Water depth itself imposes physical limitations in access to aquatic foraging habitat, but it is a dynamic variable that was only marginally correlated with time-integrated habitat availability (Appendix S1: Fig. S4). The latter is calculated as the integral of accessible water depths and shallow water by itself does not guarantee that time-integrated habitat availability will be of long duration. Water depth can therefore be considered a property that is independent of time-integrated habitat availability. Even still, there was only evidence that water depth helped explain patterns of use for Great White Herons at the smallest spatial analysis, whereas Little Blue Herons used water depths randomly. In both instances, time-integrated habitat availability helped describe patterns of use most generally.

Our simplified model of the system that was largely based on time-integrated habitat availability was able to make accurate predictions of habitat use. The strong patterning of birds feeding at locations with greater time-integrated habitat availability suggests that benthic conditions and accessible water depths alone do not meet criteria for increasing probability of use. Instead, instantaneous water depths may serve as a practical limit to access, but the time-integrated habitat availability of the foraging location is the most important habitat property.

Time-integrated resource availability is a dynamic resource property and also a robust measure for ecological inference

Long-term sea level rise (Maul and Martin 1993 ) will reduce the areal extent of present-day foraging habitat for wading birds (Galbraith et al. 2002 ) this is well known. However, the negative effect of habitat loss is compounded by a loss in the duration of access, and so it can be argued that habitat loss is temporal as well as spatial. Aside from species-specific differences in behavioral constraints on access, the duration of access to foraging locations is predominately controlled by tides (Powell 1987 , Raposa et al. 2009 , Calle et al. 2016 ). Tidal characteristics (amplitude, period) will change as sea levels rise because changes in tidal wave speeds will occur around the globe as barriers to flow change (for example, as water depth increases in shallow areas and as islands become inundated), but the direction of change (increase or decrease) will differ by region (Pickering et al. 2017 ). Even so, our models strongly suggest that a reduction in the duration of availability will affect patterns of habitat use. Habitat loss from sea level rise will be preceded by a reduction in the duration of access to present-day foraging locations while creating opportunities to forage in newly inundated upland locations (Dawson et al. 2011 ), but temporal resource dynamics will continue to affect patterns of use. Consequently, time-integrated habitat availability can be an important tool in predicting the effects of sea level rise on aquatic and terrestrial fauna that rely on intertidal zones for survival.

When is the concept of time-integrated resource availability ecologically and practically relevant?

A critical factor that influenced the usefulness of the time-integrated measure of resource availability in our study was that of the nonlinear change in inundated area due to the interaction between quickly changing water levels during tides and the underlying topography with large planar features. Prior to this study, the nonlinear changes in habitat availability were difficult to evaluate relative to other static factors. Previous studies evaluated habitat availability through the use of tide height (Powell 1987 , Spear et al. 1999 , Ellis and Bell 2008 , Raposa et al. 2009 ), tidal flows (Kneib and Wagner 1994 , Forward and Tankersley 2001 ), or other point-based metrics. The same issues pervade other studies as well. For example, freshwater fishes commonly use flood plains and ephemeral streams as habitat (i.e., for supplemental feeding or spawning) during different life-stages (Humphries et al. 1999 , King et al. 2003 , Lytle and Poff 2004 ). These topics are often studied in the context of flow regimes, flood days or hydroperiod, or timing of movement (Lytle and Poff 2004 ). However, the problem is inherently an interaction between space and time a small flood plain may provide more resources for a fish than a large flood plain if the inundation period is longer. The same processes operate in terrestrial ecosystems. For example, when a dominant lion forces a sub-dominant cheetah predator to alter and restrict its feeding times (Dröge et al. 2016 ), the total time-integrated habitat available to the subordinate predator is significantly reduced in a nonlinear way, in both space and time. This reduction in available habitat can be quantified by the change in the time-integrated availability of habitat. Although the lion–cheetah example is adequately summarized by restrictions in feeding duration alone, the time-integrated measure of habitat availability is well suited, in this case, for integration into energetic or population models that try to account for integrated measures of time and energy gained or lost among life-cycle compartments (Caraco 1980 , Pulliam 1988 ). As practical guidance for application, any physical (morphometric) or behavioral trait that constrains resource availability over time or in space should be considered in the estimation of the time-integrated resource availability because it is a characteristic property of the resource that is independent of other individual-centric properties such as intake rate or residence time.

Behavioral constraints in other taxa also act in a similar way to constrain the upper limit estimates of resource availability over time. An ectothermic lizard (Sceloporus merriami) requires heat from the sun to regulate and excite its metabolism (Grant and Dunham 1988 ). In this case, cloud cover and cold fronts reduce the amount of insolation or temperatures during the day, and thus clouds or cold fronts modify the time-integrated resource (heat) availability, as tides did in our study, whereas day length sets the upper boundaries on resource acquisition. Adolph and Porter ( 1993 ) offer a classic mathematical model to determine the nonlinear activity budgets of lizards based on heat loads, but their model only addresses temporal limitations. Recent work on reptiles, which build on Adolph and Porter ( 1993 ), merges a mechanistic understanding of temporal processes with the spatial advantages of species distribution modeling (Kearney and Porter 2009 ), but we think that these efforts miss an important point. In our previous examples, the time-integration of resource availability is the unifying principle for understanding the underlying process and asking research questions that are mechanistic in nature and comparable among studies.

Behavioral traits do not only set fixed upper limits on time-integrated resource availability, they also moderate resource dynamics at finer time scales. Additional behavioral traits impart a more nuanced limitation to resource dynamics that was not considered in our study. For example, Michaelis–Menton type of enzymatic kinetics are used to describe asymptotic consumption limits by predators based on the time required to search, handle prey and process food in the gut (Jeschke et al. 2002 ). If we had considered these additional behavioral traits and if we assume that they operate at time scales shorter than a tidal cycle, then the factors controlling the time-integrated resource availability can be ordered as daylight > tidal fluctuations > search/handle/digest time. Importantly, processes regulating daylight and tides operate at different rates and timeframes, such that while a bird is feeding, the total remaining daylight decreases and water levels continue to rise or fall. Further, individual processes that appear to control the dynamics of resource availability (tides, day-light cycles, behavioral traits) do not necessarily influence both axes of time and space directly, but they do so indirectly or as consequence of the continuous movement of background processes. For instance, time allotted to searching and handling prey does not directly influence resource (habitat) availability in space, but all the while, the background process of tidal fluctuations decreases the spatiotemporal availability of habitat to feeding birds. In this manner, the search and handling times are much more costly for an animal in a system in which there is a greater difference between the rates of processes that modulate resource availability in time and space. With this type of systems understanding, we can assume a reasonably fixed time scale for processing food in the gut, and take an average of the search and handling times to derive an estimate of the maximum number of prey a bird can consume within the constraints of daytime and tidal fluctuations, while considering the spatiotemporal discounting of a foraging activity on resource availability. Our ability to reduce the complexity of resource dynamics to individual components using the concept of time-integrated resource availability is largely based on systems thinking and an understanding that, in many cases, processes that regulate resource dynamics can be considered independent, with unique rates and timeframes, but linked by the fabric of space-time.

The modulation of resource availability by behavioral constraints can be either, or dually, spatial and temporal and the same processes can modulate resource dynamics oppositely for different taxa in the same systems. In the intertidal zone, birds appear to actively respond to water levels, whereas reproductive cycles and larval development of intertidal midges (Cluino marinus) are primarily determined by two

15-d tidal-lunar and solar cycles (Neumann and Heimbach 1984 ). The solar cycle influences the timing and magnitude of peak insolation, which influences larval development and is typically thought to occur at noon, but water is an efficient thermal mass and the maximum heat balance at the benthic surface occurs when tides are lowest at noon every

15 d (Vugts and Zimmerman 1975 ). Although the majority of the literature on Clunio marinus relates to their role in the study of genetically controlled biological rhythms, one could easily attempt to model their distribution by thinking about the dual nature of their resource dynamics: spatially and temporally constrained by a dependence on periodic cycles of solar insolation.

The examples given above are in many ways a reframing of classic ecological inquiry. We think there is considerable added value in framing ecological investigations of resource dynamics within the context of time-integrated availability. Our argument is not simply a case for additional jargon. Instead, we think that ecological studies can do more to focus on process-level understanding of resource dynamics, thereby making ecological insight more easily translatable among studies that differ in their focal taxa or ecosystem because they would operate from an understanding of general systems principles, time, and space.


The geo-graph in practice: creating United States Congressional Districts from census blocks

Every 10 years, United States Congressional Districts must be redesigned in response to a national census. While the size of practical political districting problems is typically too large for exact optimization approaches, heuristics such as local search can help stakeholders quickly identify good (but suboptimal) plans that suit their objectives. However, enforcing a district contiguity constraint during local search can require significant computation tools that can reduce contiguity-based computations in large practical districting problems are needed. This paper applies the geo-graph framework to the creation of United States Congressional Districts from census blocks in four states—Arizona, Massachusetts, New Mexico, and New York—and finds that (a) geo-graph contiguity assessment algorithms reduce the average number of edges visited during contiguity assessments by at least three orders of magnitude in every problem instance when compared with simple graph search, and (b) the assumptions of the geo-graph model are easily adapted to the sometimes-irregular census block geography with only superficial impact on the solution space. These results show that the geo-graph model and its associated contiguity algorithms provide a powerful constraint assessment tool to political districting stakeholders.

This is a preview of subscription content, access via your institution.


Considering holes/constraints in Voronoi polygon creation in QGIS? - Geographic Information Systems

A wireless sensor network is a network that is made of hundreds or thousands of sensor nodes which are densely deployed in an unattended environment with the capabilities of sensing, wireless communications, and computations [ 1 ]. Sensor nodes are tiny, low power devices equipped with processor, memory, radio, actuator, and power supply. Radio transmitters and receivers help sensor nodes to communicate with each other.

Some of the challenges in WSNs are node deployment, energy consumption, node heterogeneity, data aggregation, and fault tolerance [ 2 ]. Hole detection is one of the major problems in WSN. Holes affect the network capacity and perceptual coverage of the network. Due to limited battery the nodes may die with passage of time. In case of random deployment, there is a huge possibility that all areas of target region are not covered properly leading to formation of holes. Detection of holes is important because of their negative and damaging effects.

WSNs have myriad of interdisciplinary applications such as weather forecasting, battlefield surveillance, threat identification [ 3 ], health monitoring [ 4 ], environment monitoring [ 5 ], and wild life monitoring. All those applications that demand random deployment and uncontrolled environment suffer from holes problem [ 6 ]. Thus, hole detection can be useful for all disciplines of sciences and engineering.

The rest of the paper is organized as follows. Section 2 discusses different types of holes in WSNs and importance for hole detection algorithms. Section 3 proposes a novel taxonomy of coverage hole detection algorithms and reviews some of the existing coverage hole detection algorithms referring to taxonomy. Conclusions and future research directions are presented in Section 4 .

An area where a group of sensor nodes stops working and does not take part in data sensing and communication is termed as a hole in the network [ 7 ]. Holes are the barriers for communication. Holes have a huge impact on the performance of the network. Hole detection identifies damaged, attacked, or inaccessible nodes. If there is a hole in the network then data will be routed along the hole boundary nodes again and again which will lead to premature exhaustion of energy present at these nodes [ 8 ]. This will ultimately increase the size of hole in the network. Detection of holes avoids the additional energy consumption around holes because of congestion. It assures long network life and adequate quality of service.

One of the most prominent problems in wireless sensor networks is detection of network boundary, that is, the nodes that are present on the boundary of network and hole boundary [ 7 ], that is, the nodes that surround a hole as shown in Figure 1 .

Holes can be classified with respect to their mobility (mobile or static), lifetime (persistent or temporary), purposes (intentional or unintentional), affected function (functional or nonfunctional), and cause of anomaly [ 9 ] as shown in Figure 2 . Holes formed in static sensor network are called static holes . Mobile nodes create and break connections while moving, thus creating mobile holes . External events such as wildfire or heavy rain destroy sensor nodes in an area leading to formation of persistent holes . Inefficient sleep wake-up scheduling of sensor nodes can form temporary holes in the target region. Unintentional holes are formed when a node accidently lacks some physical capabilities. Intentional holes are formed when some part of target field is not sensed by any node because nodes in that area are intentionally scheduled to be in sleep state to save energy. If, due to failure of some nodes sensing, communication and processing tasks of sensor network are affected, then the corresponding hole formed is functional hole. On the other hand if some nonfunctional tasks such as security are affected then nonfunctional holes are formed.

Jabeur et al. [ 9 ] discussed PLMS (physical/logical/malicious/semantic), a cause-based taxonomy in detail, where sensor holes are studied from a cause-effect-solution perspective. Semantic holes mainly relate to collection, processing, and routing of data. Some of the reasons for their formation are inaccurate data collection and absence of specialized sensors. Logical holes are created due to cluster based approaches where a sensor node may not get support from its neighbors belonging to the same cluster. Physical holes may arise due to limited processing capabilities of sensor nodes called processing holes, through excessive consumption of energy at some nodes leading to formation of energy holes, or due to limited sensing range of nodes creating sensing holes . Coverage and routing holes come under physical holes category. Coverage holes are the result of unplanned deployment of nodes because of which target area is not covered properly. They may also occur due to changing topology due to which some sensor nodes may move over time leading to coverage holes. Routing holes occur in wireless sensor networks if either there is insufficient number of nodes or the nodes that are available cannot take part in routing [ 10 ]. These holes have a direct effect on the routing performance of the network. These holes mostly occur in geographic greedy forwardingbecause of local minimum phenomenon.

Holes formed by malicious behavior of some nodes in the network are called malicious holes. Further categorization of malicious node includes jamming, sink, and trust holes. Jamming holes occur if some high frequency signals block the radio frequency used for communicating by sensor nodes. Denial of service attacks causes Sink/black holes [ 11 ] where an adversary announces attractive routes to sink and thus succeeds in deceiving other nearby nodes which may select this node as their next hop. Trust hole is a new type of holes proposed by author that comes under malicious holes category. Sensors assign weighted trust values based on different parameters to their neighbors. Trust weight threshold values are application dependent. We can see a trust hole in Figure 3 , delimited by sensors having weight values less than or equal to 0.5.

Sensor network with different holes.

Out of all the types of holes discussed so far, coverage holes are the most important to detect as they play a vital role in assuring good QoS. They help us to identify whether each point in sensing field has the required degree of coverage or not. They are the indicators of general health of sensor networks and help in identifying geographic characteristics of target region [ 12 ]. Hole boundaries can determine areas of interest like fire, flood, or earthquake. They help us to find out locations where more nodes need to be deployed and thus assist in patching the holes. Hole detection ensures reliability by preventing data loss.

Coverage hole detection aids in identifying alternative communication pathways and assists in regulating data traffic flow. Absence of hole detection algorithms will eventually cause problems in routing. Thus, the rest of the paper is focused on identifying different ways to detect coverage holes in sensor networks.

3. Taxonomy of Coverage Hole Detection Algorithms

There has been a large body of research on detection of coverage holes in WSNs over the last few years. In Figure 4 , coverage hole detection algorithms have been classified into different categories: (A) based on the type of information used, (B) based on computational model, and (C) based on network dynamics. In this section, we analyze and summarize some of the typical hole detection algorithms of each category.

Coverage hole detection algorithm categorization in WSN.

3.1. Approaches Based on Type of Information Used

The efforts invested so far in the field of coverage hole detection based on the type of information used by the algorithms can be divided into three approaches, namely, topological, statistical, and geometrical approaches [ 13 ].

3.1.1. Geographical Approach

This approach assumes that exact location of sensor nodes is known beforehand. Each node knows its location either with the help of special location hardware such as GPS [ 12 ] or by using scanning devices, thereby increasing size and structure of sensor nodes. It is also known as location based approach.

Yang and Fei [ 14 ] proposed a hole detection and adaptive geographical routing (HDAR) algorithm to detect holes and to use this information to deal with local minimum problem. If the angle between two adjacent edges of a node is greater than 120 degrees, then it begins hole detection algorithm. Here, the ratio of network distance over the Euclidean distance is used as metric to detect a hole that is, Length_pro ( p , x ) /dist׾uc ( p , x ) is the hole detection ratio. If for a node the value of hole detection ratio is greater than a predefined threshold, then it is on boundary. One of the main advantages is that a single node can efficiently detect the hole. After detecting hole, it advertises this information to nodes in vicinity which can adaptively adjust the forwarding direction.

Also called as connectivity based approach, it uses only the available connectivity information of network to detect holes [ 13 ]. This approach requires no location information and works even for dense networks. There is no assumption about node distribution. One of the algorithms based on topological approach to detect coverage holes within wireless sensor networks was given in [ 15 ] and later improved in [ 16 ]. Authors proposed a distributed cooperative scheme based on the fact that nodes at the hole or network boundary have smaller degrees than interior nodes. It deals with static, uniformly distributed nodes with each node having a unique id. If the degree of a node is lower than the average degree of its 2-hop neighbors, then it makes a decision whether it is on hole boundary or not. If yes, then it sends messages informing its status to its 1-hop neighbors who may also be on hole boundary. The algorithm is scalable, but approach produces poor results for randomly deployed dense networks. If there are not sufficient nodes surrounding a hole then output produced is not accurate.

Martins et al. [ 17 ] used the concepts of Rips complex and Cech complex to discover coverage holes. If communication radius is greater than or equal to twice the sensing radius and there is a hole in Rips complex, then there must be a hole in Cech complex. Authors classified holes to be either triangular or nontriangular. The distributed algorithm proposed by authors is capable of detecting nontriangular holes and the area of triangular holes. After constructing neighbor graph, each node checks whether there exists a Hamiltonian cycle in graph. If not, then node is on the hole boundary. After making decision, each node broadcasts its status to its neighbors. The algorithm further finds cycles bounding holes.

Zeadally et al. [ 18 ] proposed a hop based approach to find holes in sensor networks. There are three phases, namely, information collection phase where each node exchanges information to build a list of x-hop neighbors, path construction phase where communication links between sensor nodes in list of x-hop neighbors are identified, and finally path checking phase where paths are examined to infer boundary and inner nodes. If the communication path of x-hop neighbors of a node is broken, then it is boundary node. Algorithm works for node degree of 7 or higher which is better than some of the other approaches, but there is a huge communication overhead involved to identify x-hop neighbors.

Chu and Ssu [ 19 ] proposed a decentralized boundary detection (DBD) algorithm to identify sensor nodes near a hole or obstacle in WSN using topological approach. Each node knows its three-hop neighbors by exchanging HELLO messages and one-hop and two-hop node information. There is no UDG constraint. Each node then constructs 2-hop neighbor graph. If cycle exists in such a graph, then there is a hole in network. For dealing with hole which is not included totally inside 2-hop neighbor graph, another rule based on contour structure was developed. Detection of broken contour line implies either network boundary or an obstacle.

There are very few algorithms that can detect boundaries of small holes. Dong et al. [ 20 ] proposed a distributed algorithm that can accurately detect boundaries of small holes in the network. The first step of algorithm is to reduce the connectivity graph by using vertex deletion and edge deletion so as to obtain a skeleton graph. Thereafter, skeleton graph is further partitioned to get coarse inner boundary cycles. Each cycle either encloses a hole of graph or corresponds to outer boundary. The coarse outer boundaries are then further refined to get fine grained boundary cycles. There is no assumption related to node density. The authors further proved the correctness of hole detection.

Some statistical function is applied on data collected from neighboring nodes and then a Boolean function decides whether nodes are at hole boundary or not. It is based on the assumption that distribution of nodes follows some statistical function. There is no need of GPS, but it requires high node density that is, average degree must be 100 or higher [ 21 ]. In practice, such dense uniform deployment is not practical. The concept used by Fekete et al. [ 21 ] is that boundary nodes have lower average degrees than interior nodes. Average density is the metric used to detect holes where actual node degree is compared with a predefined threshold value to infer its position. Another metric used by Fekete et al. [ 21 ] is centrality index, where high value is assigned to inner nodes and less value to outer nodes.

Discussion . We have considered many algorithms under different categories each having its own limitations. Geometrical approach for hole detection requires GPS enabled sensor and is expensive. They consume a lot of energy and it is not practical for sensors to know their exact location in hostile environment. Considering huge applications of WSN, these approaches have limited scope. Statistical approaches provide optimal performance, but they are computationally expensive. Owing to the challenges in wireless sensor networks it is not desirable that nodes perform complex mathematical and statistical calculations [ 13 ]. Topological approach provides realistic results but involves communication overhead. Some of the algorithms do not work for small network degrees.

3.2. Algorithms Based on Computational Model

On the basis of computational model used, coverage hole detection algorithms can be classified into two categories, namely, centralized and distributed.

Centralized algorithms run on one or more nodes at centralized location. Bldg and Funke [ 28 ] presented a centralized hole detection algorithm based on connectivity information of the network. Authors select a set of nodes and then identify whether isolevels generated from each node are broken or continuous. Algorithm is based on the fact that isolevels are always broken at either the network boundary or the hole boundary. It identifies the nodes near boundaries but gives no idea of how they might be connected. Moreover, it requires dense deployment. Ghrist and Muhammad [ 25 ] have introduced a centralized technique for detecting coverage holes based on homology, an algebraic topology variant. It uses only available connectivity information to detect single level coverage holes. Time complexity is O ( n 5 ) , with n being the number of nodes. Approach gives no guarantee to detect hole boundary accurately.

In decentralized algorithms, multiple nodes work together to efficiently detect hole in the network resulting in uniform division of workload. Senouci et al. [ 24 ] proposed a hole detection and healing (HEAL), a distributed and localized algorithm which can detect coverage holes using distributed coverage hole detection and can heal the detected holes using virtual forces concept. Attractive and repulsive forces act inside hole healing area (HHA) to recover from holes without any side effects. The computational complexity of this algorithm is O ( v 2 ) , where v is the average number of 1-hop neighbors. HEAL deals with holes of various forms and sizes and provides cost effective and accurate solution for hole detection and healing. Kröller et al. [ 30 ] developed a distributed algorithm to detect holes in large sensor networks using quasiunit disk graph. Algorithm does not perform well in sparse networks where identification of even one flower is difficult.

Wang et al. [ 27 ] presented a simple, distributed boundary recognition algorithm based on repetitive network flooding. Nearest common ancestors (NCA) are used to detect holes. In Figure 5 , node r is the nearest common ancestor of nodes p and q. Algorithm builds the shortest path tree rooted at some arbitrary nodes. Nodes where shortest paths of distinct homotopy types meet past the hole are called cut nodes.

Nearest common ancestor of p and q is node r.

After determining cuts in shortest path tree, coarse inner boundary which is a shortest cycle enclosing the composite hole is detected. Network is then flooded with shortest cycle to identify external nodes, that is, nodes whose hop counts to cycle are locally maximal. Finally coarse inner boundary is refined. There is no UDG constraint. Huge communication overhead is involved for synchronizing nodes before tree is constructed. Moreover, algorithm fails if there are multiple adjacent holes.

On the basis of nodes that invoke hole detection algorithm, we can further classify distributed algorithms into two categories, namely, local detection and global detection. A hole occurs when several adjacent nodes in sensor network fail and is defined as the convex hull of the region containing failed sensors [ 22 ]. Holes affect their immediate neighbors, as well as remote nodes whose routing options are reduced. Based on the nodes which invoke hole detection algorithm, there are two categories of hole detection algorithms, namely, local detection and global detection. In local detection, nodes that are immediately affected by the hole initiate hole detection algorithm. However, in global detection, hole is detected by a node that is far away and is not affected directly by damage caused by hole.

(a) Local Detection . Corke et al. [ 22 ] presented, analyzed, and implemented two distributed algorithms for hole detection. In local detection, node initialization phase is necessary to know about initial connectivity state. In the initialization phase, each node sends out a ping requesting neighbor information. Nodes that reply with their id are added to the list of neighbors. Neighbors are then pinged periodically to verify integrity of network. If neighboring node gives no response to pinged message, then it is regarded as dead. When dead count exceeds dead threshold, then node marks itself as sitting on damage perimeter. During damage extent computation, each node finds out the overall convex hull incrementally by calculating convex hulls at each node and sharing the hulls until there are no further changes to the hull set. Wang et al. [ 27 ] have developed a distributed algorithm where each node first checks whether it is a stuck node or not using TENT rule. If a node is closer to target than all its 1-hop neighbors, then it is a stuck node. The stuck nodes are marked as hole boundary nodes. Boundhole algorithm then builds routes around hole boundary to route packets. Approach needs only angle information within its 1-hop neighbors therefore detection is local.

(b) Global Detection . In global method, routing information is used to detect the holes. In paper [ 22 ], path density is the metric used to detect presence of holes. Each node randomly broadcasts a diagnostic packet containing source coordinate, destination coordinate, previous coordinate, distance travelled, and message id. Distance travelled and previous coordinate are updated at each hop. Message id is used to ignore duplicate messages. When message reaches destination, path density is calculated as the ratio of straight line distance from source to destination to actual distance travelled. Low ratio implies that a hole exists in the network.

Discussion . Limited storage is one of the challenges of sensor networks thus, algorithms that collect whole data at some node to perform centralized computations are infeasible. Centralized approach suffers from problem of single point of failure. Due to dynamic topology and exogenous disturbances, WSNs need dense deployment. Protocols designed for such dense networks should be distributed in order to accommodate scalable architecture. Centralized algorithms consume more energy to achieve higher percentage of hole area recovered as compared to distributed algorithm. On the other hand, distributed algorithms are more complex than centralized as they need to run on many nodes throughout the network. Global approach helps to overcome ambiguity often faced by local detection. Local detection algorithms run periodically to give information about health of sensor network. They can be used to look for changes from initial state.

3.3. Algorithms Based on Network Dynamics

Algorithms discussed in this section are classified based on network dynamics in sensor network as static sensors, mobile sensors, and hybrid sensors.

Li et al. [ 34 ] proposed 3MeSH (triangular mesh self-healing hole detection algorithm), which is a distributed coordinate-free hole detection algorithm. It is assumed that each node has uniform sensing radius R and communication radius 2R. Initially a subset of active nodes is selected. An active node x is neighbor of active node y if they are between R and 2R distance apart. Nodes that lie within the sensing range of an active node are called redundant nodes. Connectivity information is collected by each active node from its neighbors. If node detects presence of 3MeSH ring as shown in Figure 6 defined by all its neighbors, then it is a boundary node. For detecting large holes, nodes are allowed to collect connectivity information from nodes further away but at the cost of increased complexity. 3MeSH-DR is an improved version of 3MeSH algorithm presented in [ 31 ].

Mobile sensor nodes can move around after initial deployment. The main objective in mobile WSN is to maximize coverage. Topology of sensor network is affected by mobile nodes as they form new connections and break old ones. If the coverage area of a node can be covered by its neighboring node, then only a node can move to another area. In [ 26 ], authors have used Voronoi diagrams to detect coverage holes. Voronoi diagram is a diagram of boundaries around each sensor such that every point within sensor’s boundary is closer to that sensor than any other sensor in the network [ 35 ]. Figure 7 shows a Voronoi cell. Nodes P, Q, R, S, and T are Voronoi neighbors of X and a, b, c, d, and e represent Voronoi edges. These edges are the vertical bisector of line connecting X to its Voronoi neighbors.

A polygon constructed from all these Voronoi edges is called Voronoi cell of node X. We can see a Voronoi diagram in Figure 8 .

To detect hole, each node checks whether its Voronoi polygon is covered by its sensing area. If not, then coverage hole exists. After detecting hole, one of the three proposed algorithms is used to find target location where a mobile node is to be moved so as to heal the hole. In vector based algorithm (VEC), sensor nodes are pushed from dense regions to sparse regions so that nodes are evenly distributed. Voronoi based algorithm (VOR) is a pull algorithm which pulls nodes towards sparse regions. In minimax algorithm, target location is at the center of its Voronoi polygon. Minimax algorithm achieves maximum coverage at the cost of increased computational overhead.

Zhao et al. [ 32 ] proposed a coverage hole detection method (CHDM) by mathematical analysis. It is assumed that network consists of mobile nodes each with sensing radius r and communication radius 2r. A node p is defined as neighbor of node q if it lies in its communication range. On the basis of central angle between neighbor sensors, the authors presented different cases to find coverage holes in communication circle around a redundant movable node. To patch hole, a redundant node is moved to an appropriate position inside the hole.

Hybrid WSNs consist of both stationary and mobile nodes. Mobile nodes help in healing the coverage holes created by stationary nodes. Babaie and Pirahesh [ 29 ] presented a triangular oriented diagram to detect a hole. The authors connected the center of three adjacent sensors to produce triangle and further presented various possibilities of occurrence of holes and then calculated the area which is not covered by any of them. This uncovered area is coverage hole. To patch the coverage hole, a mobile node is moved to incenter or circumcenter depending on whether hole area is more or less than sensing region, respectively. The approach is simple as compared to Voronoi diagram construction. Moreover, it can determine exact area of hole.

Wang et al. [ 33 ] proposed a distributed bidding protocol for detecting coverage holes in hybrid sensor networks. Mobile nodes act as hole healing server with certain base price initially set to zero. Base price is the estimate of new coverage hole generated when a mobile node moves to new target location for healing purpose. During advertisement phase, mobile sensors broadcast their locations and base price. In bidding phase, static sensors examine their respective Voronoi cell to detect coverage holes locally. If hole exists, it estimates its size and determines target position inside the hole. Static nodes then calculate the bid using formula π * ( d - sensing-range ) 2 , with d being the distance between target location and the node that wants to bid. Static sensors send bidding message to the nearest mobile sensor whose base price is less than its bid. Each mobile node compares the received bids and chooses the message with highest bid and moves to the target location specified in message. This bid becomes new base price of mobile node. This process stops when the bid of any static sensor is not higher than the base price of any mobile sensor.

Discussion . The probability of the formation of hole in a high density network is less. Therefore, for dense networks static sensor networks are preferred while in case of sparse density, hybrid and mobile sensor networks give better coverage. Some of the nodes in hybrid and mobile networks can move to patch the coverage holes, thereby improving the network connectivity. Sensors moved through a long distance will consume more energy. If energy of a sensor is so less that it dies shortly after being relocated to target region, then this effort is wasted. Therefore, moving and messaging cost must be kept at minimum while dispatching mobile nodes to target locations in hybrid and mobile sensor networks.

In this paper, taxonomy is proposed which gives an exhaustive classification of coverage hole detection algorithms. In the last few years, many innovative ideas have been provided by researchers to solve coverage hole detection problem in WSNs, but research in this direction is still in growing phase. Table 1 summarizes the characteristics of various coverage hole detection algorithms in aspect of approach used, computational model, network dynamics, detection level, and simulation environment. From Tables 2 and 3 , it can be seen that each algorithm has its own strengths and shortcomings, but none is absolutely the best. Table 4 discusses some of the application suggestions for coverage hole detection algorithms.

Characteristics of various coverage hole detection algorithms.

Strengths and shortcomings of coverage hole detection algorithms.

Comparison of hole detection algorithms under different parameters.

Application suggestions for coverage hole detection algorithms.

Having surveyed various coverage hole detection algorithms, this section discusses some of the future research directions. Authors have made a good attempt to detect holes, but most of the algorithms produce poor results for nonuniformly deployed dense networks. Computational complexities of the topological algorithms have not been analyzed. Further research on optimizing algorithms in hybrid sensor networks and evaluating tradeoffs between latency and data gathering techniques can provide valuable information to optimize coverage and connectivity. Although the literature is replete with coverage hole detection techniques, so far there is no application specific hole detection protocol. There exist very few protocols that can deal with open holes at the network boundaries.

Future work can also focus on mitigating holes problem after its occurrence and provide an optimal hole healing process. Some of the ways to avoid the hole formation can be using mobile sinks or multiple sinks. Nodes forward their data to sink when mobile sink gets closer, thereby avoiding unnecessary energy wastage in multihop delivery paths. In order to save energy of sensor nodes, multiple sinks can be deployed in target area so as to reduce the distance data has to travel to reach sink. Mobility of nodes can be exploited to patch the coverage holes. Algorithms can be built that give special considerations to nodes that are on the verge of becoming a hole. Another interesting work can be on developing commercial products to detect holes in WSNs.

Most of the algorithms consider nodes being deployed in 2-dimensional environment, but in real-world applications, sensor nodes are deployed in 3-dimensional environment. So, work can be done in this direction. One of the interesting research issues in the future can be detecting the presence of holes in underwater and underground WSNs. Mathematical modelling and real-world testing must be included in actual steps of research. This will also allow fair comparison among algorithms.


3.5 Key characteristics and shortcomings of current approaches

As shown in this chapter, there is great variety among the techniques used to model different aspects of 2D and 3D space, time and geographic scale. Considering all the possible ways in which these techniques can be combined together into a complete modelling approach, many different feasible approaches can be devised, which can be further fine-tuned for a particular application or use case. These vary in fundamental aspects, such as their explicitness, their use of geometry and topology, and the class of objects that they are able to handle efficiently.

However, despite these very real and substantial differences, the representation approaches in 2D GIS have become largely interchangeable in practice. There is a myriad of well-known topological data structures that can be used, such as the DCEL [Muller and Preparata, 1978] and the quad-edge [Guibas and Stolfi, 1985], and even when certain objects are not directly supported in them (e.g. those with a non-manifold shape or with holes), they can usually be nevertheless stored using various simple &lsquotricks&rsquo, such as repeated combinatorial primitives (as shown previously in Figure 3.10), special kinds of attributes or external data structures such as indices.

Moreover, many 2D GIS applications do not even require the explicit topology of a topological data structure. Visualisation and simple computations can just as easily do without it, and consequently use data structures with very little or no topology, opting for a Simple Features-like representation [OGC, 2011]. Also, considering that the computation of topological relationships between 2D objects is relatively simple, it can be done on-the-fly only when it is needed [ESRI, 2005]&mdashsomething that is especially true for the relatively small size of most 2D datasets, which often pale in comparison to the computing power that is now readily available. All of these reasons point towards a similar conclusion: objects of up to two dimensions (i.e. points, line segments and polygons) can be represented using either topological or non-topological approaches with little difference in practice.

In 3D, the situation is more complex and topology brings more significant advantages, even as storing topological relationships comes at a significantly increased cost in terms of memory. Compared to the circumstances in 2D, there are more topological relationships between 3D objects, and these are more difficult and expensive to compute, so their storage becomes highly desirable in many instances. At the same time, datasets are usually much larger, which makes topological relationships more valuable in order to traverse them efficiently. More complex applications such as simulations greatly benefit from 3D topological representations as well&mdashor at least from data that is known to be valid, for which 3D topological data structures are used [Ledoux, 2013].

Moreover, many of the strong properties that allow for simple but powerful data structures and quick computations in 2D do not work in 3D. For instance, there is a natural order for the vertices or line segments around a polygon&mdashused e.g. to efficiently store a polygon as a sequence of vertices&mdashbut there is no similar natural order for the faces around a polyhedron. Similarly, storing a complete planar partition as a set of edge primitives where every edge records the polygons that lie on each of its two sides [Peucker and Chrisman, 1975] is straightforward and efficient, but a 3D space partition stored as a set of faces where every face only knows the volumes that lie on both of its sides is very cumbersome to navigate&mdasheven a simple operation such as extracting the volumes in the partition is difficult without the adjacency relationships between the faces.

Partly because of this, as well as the general increase in complexity that comes with an increase in the number of dimensions, the topological data structures that are capable of storing topological relationships between sets of 3D objects are less used in practice. The third spatial dimension, time, and scale are mainly implemented using ad hoc adaptations to 2D data structures, effectively limiting the capabilities of GIS software. 3D GIS often mimic the third dimension by using a so-called 2.5D structure [Raper, 1989], essentially treating the third dimension as an attribute and restricting the geometries that can be represented or represent 3D objects individually and only implicitly through their 2D boundary, using a 2D data structure with no 3D topological relationships 52 . This implies that many operations are only possible using expensive searches involving many more objects than otherwise needed.

Time and scale are considered to be inseparable in the representational process by theorists, since events have an intrinsic place in space and time, as well as specific spatial and temporal resolutions [Raper, 2000]. However, spatiotemporal GIS keep multiple representations of 2D [Armstrong, 1988] or 3D [Hamre et al., 1997] structures, or a list of changes per object [Worboys, 1992a Peuquet, 1994], limiting combined spatio-temporal analysis of such objects. Multi-scale datasets generally consist of independent datasets for each scale, which are either unconnected or connected only at the object level (e.g. through the use of IDs). This means that complex relationships between objects, such as collapses, aggregations and others that are not one-to-one are difficult to store, which causes, among others, update and maintenance problems as well as inconsistencies. It also complicates the storage of semantic information about these relationships.

18. Cartesian products of simplices↩

19. There are certainly exceptions, such as 3D+scale models as 4D models where a volume collapses to a point. However, the large number of primitives that would need to be defined for a system of this kind would make it impractical.↩

Figure 3.1: An object represented as a tree of Boolean set operations on a sphere, a cube and three cylinders. From Wikimedia Commons.↩

20. i.e. a line in 2D and a plane in 3D.↩

21. This is equivalent to a triangle in 2D and a polyhedral pyramid in 3D.↩


Watch the video: GIS Tricks: Create Polygon, Clip and Difference