Implementing Zones - NAVADMC/ADSM GitHub Wiki

This document describes the implementation of zones in ADSM.

This document refers frequently to the Model Specification.

A first look

The simplest possible implementation for zones would attach a number to each unit: 1 if the unit is inside a ring of the smallest, highest surveillance ring, 2 for the next ring out, and so on (figure 1).
Figure 1: A simple labelling of units (in a uniform grid) by zone. Detected units are in red.

We quickly see that this will be inadequate for enforcing the rule forbidding movement between separate foci of the same zone (figure 2).
Figure 2: Movement inside a zone may be allowed, but movement between physically separated foci of the same zone is not.

A sensible extension would be to store another number for each unit, a serial number for disconnected areas of the same zone (figure 3). This is sufficient for enforcing the rule in figure 2.
Figure 3: Labelling of units by zone and zone focus.

This also suggests a way to manage overlapping/merging foci. When we go through the list of units to find the ones that are inside a newly-added focus, if we encounter a unit labelled with the same zone but a different focus, we record that “old” label. We then do an additional sweep through the list of units, changing any occurrence of the old label to the new one (figure 4). This will properly handle merging zones unless there are no units in the overlap area.
Figure 4: Merging overlapping zone foci. When a “1-1” label is found inside the new focus, all units with that label are updated.

The problem of holes

This simple labelling of units looks promising, but when we consider the “no donuts” rule (figure 5) we see that it is still inadequate. The scheme described so far provides no way to recognize when a donut-hole has been created, nor does it provide a way to identify the units inside the donut-hole.
Figure 5: Zones with lower surveillance levels are absorbed when enclosed by a zone of a higher surveillance level.

At a modeling level, there are two possible ways to deal with holes in zones. One is to allow holes but stipulate that units trapped inside the donut-hole cannot have contact with units outside. Another is to disallow holes, to fill them in as soon as they appear. Team members familar with real-world disease control policies preferred the latter. (Although note that in both cases we need to recognize and label the units inside the donut-hole.)

Since it appears we need more sophisticated machinery in the code to handle donut-holes, we should ask whether they will actually occur in simulations. In other words, does this actually matter or is it just an “academic” question?

To answer this, we turned on zones in simulations using the UK North Cumbria data set, drawing 3- and 10-km zones around units that are detected as diseased. In the 32-day simulations, holes had to be filled an average of 42 times per iteration. So donut-holes do occur and need to be handled.

Using a polygon operations library

Rather than invent solutions from scratch for this implementation, we searched for a ready-made library of code for polygon operations. We chose the General Polygon Clipper (GPC) library by Alan Murta because it is

  • able to handle polygons with multiple separate pieces and holes
  • free for non-commercial use.

Using the GPC library, each zone can be stored as a polygon. A polygon can be made of multiple “contours,” corresponding to physically separated foci of a zone. Adding a focus to a zone then consists of

  1. creating a regular polygon with enough sides to approximate a circle
  2. using the GPC’s union operation to merge the circle with the existing zone contours.

The GPC uses a particularly convenient representation for holes in polygons. It is simple to remove the holes, treating each hole as a polygon itself and using a point- in-polygon test to identify the units that are inside the donut-hole.

So using the GPC library provides an easy solution to merging foci (even when there are no units in the overlap area) and to recognizing and filling in donut-holes. Are there any drawbacks?

First, there is the cost of maintaining information about zones in two forms: labels on individual units, and separate polygon data structures. Second, there is the expense of doing polygon union operations each time a focus is added to a zone.

There is also one sticky point with polygon union operations. Figure 6 shows that adding a focus to a zone may increase the number of contours, leave the number of contours the same, or decrease the number of contours. We need to know which pre-merge contours correspond to which post-merge contours in order to track which units belong to which contours. But the GPC library’s polygon union operation does not provide this information.
Figure 6: Adding a focus (red) may increase the number of contours in a zone polygon by 1, leave the number of contours the same, or decrease the number of contours.

We can address this by storing along with each contour a point that is known to be inside the contour. (The location of the unit that caused the zone focus to be established is an obvious choice.) Then, when a new focus changes the number of contours in a zone polygon, we can (at some computational expense) test which post-merge contour contains each of those points.

A persistent structure for labelling units

The final point I want to address is how we can efficiently maintain useful zone information for each unit. In the movement/contact module we want to be able to tell, with minimum effort, whether two units are in the same contour of a zone polygon.

We could store a number with each unit identifying in which contour of the zone polygon it lies. But as we saw in figure 6, contours are not a persistent data structure: the number of contours is likely to increase as the first detections happen, then decrease as the contours grow large and numerous enough to overlap and merge.

We address this by creating a persistent intermediate data structure that we call a zone “fragment.” A unit can be assigned to a fragment, and the fragment in turn maps to a contour. Figure 7 shows how fragments allow contours to merge without disrupting the assignment of units to fragments.
Figure 7: An intermediate layer to map units to contours. Note that adding a focus reduces the number of contours from 3 to 2 but does not change the existing mapping of units to fragments.

In this way, once a unit is assigned to a zone fragment, it can stay assigned to that fragment — regardless of how many times contours merge. And we can check whether two units are in the same contour simply by asking whether their fragments map to the same contour.

Useful source code