jrpeters edited this page Mar 31, 2016 · 17 revisions

This page provides detailed information about key operations and objects in AreaCon.

##Polygons ###Creating Polygons Polygons are the most basic object involved in partitioning operations, since a partition (at least, in this context), is essentially a collection of polygons. In its current form, AreaCon can only store polygons that are simple, that is, polygons that consist of a single shape with non-intersecting edges (this is all that is necessary to perform the operations that AreaCon is designed for). Simple polygons are created and stored using the Poly class, which primarily serves as a container for storing the list of vertices which make up the polygon. Individual vertices are stored using the Point class, and the vertex list is stored as a std::vector.

IMPORTANT: The vertices making up the polygon must appear in counterclockwise order in the vector Polygon::Vertices, and no vertex can be repeated. For example, if we wanted to create a polygon object called "mypoly" whose corners are (0,0), (0,1), (1,1), and (1,0), we would use Poly mypoly({Point(0,0), Point(1,0), Point(1,1), Point(0,1)}). Note that the default constructor for poly produces an empty vertex list.

Upon construction of a polygon, AreaCon automatically runs a few basic checks to ensure dimensional consistency; however, it does not explicitly run a check to verify that edges are non-intersecting. Attempting to use non-simple polygons will result in undefined behavior.

###Creating A Polygon for Partitioning

Polygons that are to be used for partitioning have the additional requirement that they must be convex (this is an algorithmic requirement). Once again, as of right now, AreaCon does not automatically run checks to ensure that the regions that are being fed into the partitioning algorithm are convex (possibly an addition for the next version). Initializing a partitioning object with a non-convex region will result in undefined behavior.

How do I tell if a polygon is convex?: There are a number of ways to test if a polygon is convex, but in the vast majority of cases it is easy to tell if a polygon is convex by graphical inspection. Graphically, a polygon is convex if any two points inside the polygon can be connected by a line that lies entirely inside the polygon. See below:

A more quantitative (but slightly more tedious) check is to see if all of the interior angles are less than 180 degrees.

##Density Functions

The other major driving force in a generic area-constrained partitioning problem is the underlying prior probability density function (sometimes just called a "prior"). Indeed, the entire reason for constructing an area-constrained partition of a polygonal space is so that each individual region has a pre-specified weighted area, and the prior is what determines how this area is calculated. As such, it is crucial that users of AreaCon understand precisely how the software represents and handles priors to ensure that the results produced by the software are consistent with the underlying environment.

###Discretizing Density Functions

Although AreaCon performs geometric manipulations of polygons in continuous space, it requires a discrete representation of the underlying prior in order to perform integration and other operations required by the partitioning algorithm. Therefore, the software implicitly assumes that there is a uniform grid that covers the polygonal region of interest, and that the value of some continuous prior evaluated at each grid point is available. AreaCon stores the list of values as a representation of the continuous function.

To create a discrete density that can be used by AreaCon, users should do the following. First, decide on the number of horizontal and vertical grid points that should be used. These parameters are referred to as Nx and Ny, respectively. Second, draw a tight bounding box around the region of interest whose sides are aligned with the horizontal and vertical axis. Therefore, points on the region boundary should be touching the bounding box, but no points should lie outside. Then, place Nx x Ny grid points uniformly throughout the bounding box such that the first and last row/column of points lie on the boundary of the box. As such, the horizontal spacing between successive grid points should be dx = (max{x}-min{x})/(Nx-1) and the vertical spacing between successive points should be dx = (max{x}-min{x})/(Nx-1). Next, assign values to each grid point. Points that lie outside of the region of interest will not affect the calculation, but they need to be assigned a value anyway.

IMPORTANT: AreaCon will treat the value assigned to each grid point as if it were the value of a continuous probability density function evaluated at the particular point in question. Therefore, do not multiply density values by the grid spacing (dx x dy). In other words, do not create a probability mass function that is analogous to the continuous function. Rather, simply evaluate the continuous function at the grid points.

Note: The function that is evaluated at each of the grid points need not be a "true" probability density function since it need not be normalized (AreaCon will do this automatically).

Once the density grid is created and values are assigned, all that remains is to create a vectorized version of the density. To do so, simply create a std::vector<double> of size Nx*Ny (called, for instance, Example) and store the density grid as follows: Assign indices ranging 0 to Nx-1 to the grid columns, starting from the left side and working right, and assign indices ranging from 0 to Ny-1 to the grid rows, starting from the bottom and working up. Then, store the value associated with the _(i,j)_th grid point in Example[i*Ny+j].

###Graphical Example

###Area and Centroid Calculations with Density Objects

One particularly useful tool that AreaCon provides is the explicit ability to calculate the weighted area and centroid of a polygon whose density is defined via a Density object. Indeed, given a Density object, the weighted area of any (non-convex, simple) polygon that lies entirely within Density::Region can be calculated via the function Density::CalculateWeightedArea, and its corresponding centroid can be calculated with Density::CalculateCentroid. Note that the weighted area of the polygon of interest is one of the inputs to Density::CalculateCentroid, so it is usually necessary to first call Density::CalculateWeightedAreabefore doing centroid calculations.

When using this functionality, it is especially important to ensure that the polygon being used for centroid calculation does not have any points that lie outside of the polygon Density::Region, or else errors will occur. It is also important to note that the centroid calculation is done by interpolating over the density grid, and thus the accuracy of the result is directly proportional to Density::Nx and Density::Ny.

##Algorithmic Parameters AreaCon computes partitions over a continuous space by discretizing the space and subsequently simulating solution curves to a continuous-time differential equation. As such, the behavior of AreaCon is somewhat sensitive to the algorithmic parameters that are chosen. The purpose of this section is to give some guidance as to how to choose appropriate parameters for your problem.

###Parameter Descriptions

####Parameters::centers_step

The area-constrained partitioning algorithm used by AreaCon iterates between two "modes:" 1) adjust centers, and 2) adjust weights (see Theory). During the "adjust centers" mode, the algorithm looks at the current configuration, and moves the center (generator) of each region toward the centroid. The parameter Parameters::centers_step determines the percentage along the straight-line path between the current center location and the centroid that the current center should be moved. For example, if centers_step is 0.5, on each iteration of the "adjust centers" mode, the center will be moved to the mid-point between the current center location and the centroid.

####Parameters::weights_step

As mentioned, the partitioning algorithm iterates between two "modes": 1) adjust centers, and 2) adjust weights (see Theory). During each iteration of the "adjust weights" mode, the new weights are chosen by approximating the (convergent) solution curve of a continuous-time ODE, and subsequently defining the new-weights to be the limiting configuration. To approximate solutions to the ODE, the algorithm uses a simple forward Euler method (see references). The parameter Parameters::weights_step is the (uniform) step-size of the forward Euler method used.

####Parameters::line_int_step

AreaCon uses a simple trapezoidal rule in order to calculate line integrals. The parameter Parameters::line_int_step represents the normalized spacing used for the trapezoidal rule. For example, if calculating the integral along some line segment and line_int_step=0.1, then 10 uniformly-spaced points will be used for the trapezoidal rule.

####Parameters::volume_tolerance

Each time AreaCon enters the "adjust weights" mode, the solution curve to a continuous-time ODE is simulated, and the new-weights are chosen according to the limiting behavior of the curve. Theoretically, the solution curve will converge to some fixed, limiting configuration, and, if the weights are chosen to exactly match this limiting configuration, then each region of the resulting partition will have the correct area. However, it will take infinite time to reach the limiting configuration, so it is necessary to approximate. The parameter Parameters::volume_tolerance, loosely speaking, determines when the weights are "close enough" to the ideal weights, at which point the algorithm enters the "adjust centers" mode. Smaller values indicate smaller acceptable error.

####Parameters::convergence_criterion

Each time AreaCon enters the "adjust centers" mode, the centroid of each region in the current configuration is calculated, and is compared to the location of the current center. If the centroid is "close enough" to the current configuration, then the partitioning operation terminates. The parameter Parameters::convergence_criterion determines the definition of "close enough". Smaller values indicate smaller acceptable error.

####Parameters::max_iterations_volume

Convergence during the "adjust weights" mode can be slow at times, in which case it is usually beneficial to run an iteration of the "adjust centers" mode, and then try to adjust weights again to see if convergence speed increases. The parameter Parameters::max_iterations_volume indicates the maximum number of Euler steps that can be taken during each iteration of the "adjust weights" mode before switching to the "adjust centers" mode.

####Parameters::max_iterations_center

The parameter Parameters::max_iterations_center specifies the maximum number of "adjust center" steps that can be taken before the partitioning algorithm is terminated.

####Parameters::Volume_Lower_Bound

Numerical issues can sometimes arise if, during the course of the iterative partitioning algorithm, the area of some region becomes too small. Therefore, the parameter Parameters::Volume_Lower_Bound specifies a lower bound to be enforced on the area of each region. The user is not allowed to specify a desired area that is smaller than this bound.

####Parameters::Robustness_Constant

There are many instances in which it is necessary to determine if entities in 2D space, e.g., two points, are numerically equal. Loosely speaking, the parameter Parameters::Robustness_Constant determines how close to each other two entities need to be in order for them to be considered equal by the numerical algorithm.

####Density::Nx, Density::Ny

These parameters specify the number of columns and rows, respectively, of grid points used for the discrete representation of the prior density. For example, if Density::Nx = 50, Density::Ny = 100 AreaCon assumes that the density is represented via a uniform grid with 50 columns and 100 rows of points (see Density).

###Choosing Appropriate Parameters

The process of choosing appropriate parameter values is somewhat delicate, and is heavily influenced by a number of factors, including the characteristics of the particular problem or class of problems of interest, the desired degree of accuracy, and speed requirements. AreaCon has been defined with default parameter values that (at least in the author's experience) produce reasonable solutions in reasonable time for a number of common partitioning problems. However, it is impossible to define a set of universally appropriate values, so it is important that users take a moment to consider the affects of parameters on their particular problem. The list here is provided to give a bit of guidance to this process.

####Scenario 1: The prior density function is highly concentrated in a few small regions, or is is highly spatially variant (has large spatial derivatives)

Recommendation: Choose Density::Ny, Density::Ny large, and choose Parameters::weights_step, Parameters::line_int_step small. If speed is not a primary concern, it may also help to choose a large Parameters::max_iterations_volume

####Scenario 2: The prior density function is uniform, or doesn't vary much across the entire region.

Recommendation: Choose Density::Ny, Density::Ny very small, and choose Parameters::weights_step, Parameters::line_int_step somewhat large, and choose Parameters::max_iterations_volume relatively small.

####Scenario 3: A high degree of accuracy is required.

Recommendation: Choose Density::Ny, Density::Ny large, choose Parameters::volume_tolerance and Parameters::convergence_criterion small, and choose all step-sizes (with the exception of Parameters::centers_step, which won't affect accuracy) small. Choosing large values for Parameters::max_iterations_volume, Parameters::max_iterations_centers may also be necessary for high precision/accuracy.

####Scenario 4: The calculation needs to be very fast, and accuracy isn't a primary concern.

Recommendation: Choose Density::Ny, Density::Ny small, choose Parameters::volume_tolerance and Parameters::convergence_criterion as large as possible, choose all step-sizes (with the exception of Parameters::centers_step, which won't affect accuracy) reasonably large (although one needs to be careful to retain numerical stability), and choosing a small value for Parameters::max_iterations_volume.

###Common Problems with Parameter Selection

Here are a few common issues and some parameter adjustments that may help.

####Problem 1: The partition calculation is taking a very long time, and the output volume errors are fluctuating rapidly when the calculation is running

Recommendation: This usually indicates numerical instability. The easiest way to fix this would be to decrease Parameters::weights_step, and possibly Parameters::line_int_step. If possible, increasing Density::Nx, Density::Ny can also help. If accuracy isn't a primary issue, sometimes increasing Parameters::volume_tolerance can also help.

####Problem 2: The partition calculation seems like it is stuck, and the terminal output is displaying "inf"

Recommendation: This is most likely a numerical issue caused by Parameters::Volume_Lower_Bound being too small. Increase this parameter and it should fix the issue.

####Problem 3: The partition calculation is taking a long time, and the output volume error doesn't seem to be changing much on each iteration.

Recommendation: If the prior density function is somewhat uniform, then this can most easily be fixed by increasing Partition::weights_step. If the density is highly concentrated in a small area (sometimes called a "stiff" problem), then it can sometimes help to decrease Partition::max_iterations_volume to force the program to iterate between modes faster.

####Problem 4: The program is behaving strangely, or numerical overflows are occurring

Recommendation: AreaCon works best when the coordinates/distances are on the order of tens or hundreds. If the program is behaving oddly, or numerical overflows are occurring, it would probably be beneficial to scale all distances to lie within this range before using AreaCon. Another possible fix is to alter the value of Parameters::Robustness_Constant(usually larger values will help).

####Problem 5: The regions resulting from the partition calculation have the wrong area.

Recommendation: This is usually the result of Parameters::max_iteration_volume being too small. This may also happen due to numerical error. Try decreasing the volumetric error tolerance, i.e., Parameters::volume_tolerance, and/or decreasing the step-size, i.e., Parameters::weights_step. This can also happen if the underlying density is too coarse, i.e., Density::Nx, Density::Ny are too small.

####General Rule If accuracy or stability is an issue, decrease step sizes (except for Parameters::centers_step), decrease error tolerances, and increase the max allowable iterations. If speed is an issue, then do the opposite.

##Partition Objects

The Partition object is the main platform for performing partitioning operations. This section discusses the proper creation, initialization, and usage of these objects for partitioning calculations.

###Creating a Partition Object

Creating the actual partition object is straightforward once all of the necessary components have been created. To create a meaningful partition object, the following are required at the time of creation:

  • The number of regions, NRegions,
  • A Density object, Prior,
  • A vector specifying the desired (normalized) area of each region, desired_area, and
  • A Parameters object, Alg_Params, containing all algorithmic parameters.

A default constructor does exist for the Partition class, but nothing useful can really be done until the aforementioned variables are set. This can be done after creation of an initial Partition object using Partition::SetPartitionVariables.

###Initializing the Partition Object

After creating the Partition object, there is one additional initialization step that needs to be done before the final partitioning calculation is started: initial values for the centers (generators) and weights need to be chosen. This step is accomplished by calling Partition::InitializePartition. If the function is called with no arguments, AreaCon will automatically choose an appropriate initial values. However, the user also has the option of manually choosing the initial centers and weights. If manually chosen, care must be taken to ensure that centers are distinct and lie within the region of interest, otherwise errors will occur.

Automatically generated centers and weights will allow AreaCon to calculate a high-quality solution. However, if additional information about the operational environment is known, then initial centers and weights can be strategically chosen in a way that can drastically speed computation time. For example, it may be beneficial to cluster the initial centers in regions of high density, and choose initial weights proportional to the desired region areas.

###Calculating Partitions

Once a Partition object is created and initialized, then the main partitioning operation is called via the function Partition::Calculate_Partition. Notice that the inputs to the function determine if the output is to be recorded via a text file.

Once the calculation finishes, the covering and centers can be accessed via the functions Partition::GetCovering and Partition::GetCenters, respectively. More information and low level details about function usage is found in the source documentation.

##Other Tips

  • Before performing any partitioning calculations, make absolutely sure that the region that is being partitioned is convex. If it is not, AreaCon will behave unpredictably. There are a few cases where it is possible to calculate partitions of non-convex areas using AreaCon (see example); however, the library is not designed for this case and AreaCon will not produce a meaningful solution in the general case.

  • Scale all distances to lie on the order of tens or hundreds. In the authors experience, AreaCon works best at this scale.

  • Choose step-sizes and other granularity-related parameters very coarse initially, and make them finer only if necessary. In the author's experience, AreaCon is relatively robust to large step-sizes and these will usually give the best computation times.

  • Think carefully about the underlying structure of the problem or class of problems at hand, and use that knowledge as an advantage in choosing parameters, initializing, etc. This can also be used to guide optimization of the algorithm. For example, if the prior density is uniform and AreaCon is still taking a long time, chances are that better parameter choice exist.

You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.