An open source C++ library for performing area-constrained partitioning operations on convex, 2D polygonal regions
All of the codes contained on this site are open-source, subject to terms specified here .
Please use the bibtex citation found here.
The performance of AreaCon, i.e., convergence speed, is dependent upon a variety of factors including, but not limited to, the number of regions used, the size of the polygon of interest, the nature of the underlying density function, and the degree of accuracy required. For a given problem setup, performance can be optimized by adjusting algorithmic parameters.
If AreaCon is taking an unreasonably long time, it is usually an indicator of poor parameter choice. For tips and in-depth information about choosing parameters wisely, see the discussion on the Wiki.
Occasionally, the problem scaling can also cause poor performance. AreaCon operates best over length scales on the order of ones or tens, so it is usually beneficial to scale problem dimensions to be on this order of magnitude. Mismatches in length scales, e.g., densities with both coarse and fine level features, should also be avoided if possible.
If none of the adjustments mentioned result in reasonable performance, it may be necessary to consider manipulating the problem structure, e.g., choose fewer regions, a smaller area, or a different density function.
If the algorithm converges, i.e., the script finishes, but the calculated regions do not have the correct area, the most likely culprit is numerical error. As previously mentioned, AreaCon is a numerical implementation of a continuous-time algorithm and thus there are a number of algorithmic parameters that can affect the library's convergence properties. It is important to choose these parameters wisely, based on the particular problem of interest to ensure useful results. For a thorough discussion about choosing appropriate parameters, visit the Wiki.
Decreasing the parameters "volume_tolerance" and "convergence_criterion", while simultaneously increasing "max_iterations_volume" will usually fix accuracy issues. Note however, that it may also be necessary to decrease "weights_step" upon adjusting the aforementioned parameters to maintain numerical stability. Using finer density grids can also sometimes help (increasing "Nx" and "Ny").
Possibly...AreaCon is not explicitly designed for use with non-convex regions. If a partitioning operation is initialized directly with a non-convex region, AreaCon may or may not produce a valid solution.
However, the prior density function that is used is not required to be non-zero over the entire convex region. Therefore, an alternative approach to partitioning of a non-convex region would be to bound the region with a (convex) bounding box, specify the box as the partitioning area, and create a prior density that is zero at every grid point that is not located in the original non-convex region. Using the result, a partition of the non-convex region can be created by intersecting each region resulting from the bounding box partition. Note, however, that this method may cause oddly shaped or disconnected regions, and may produce centers that do not actually lie in the region.
This could be correct if the desired areas are unbalanced. For example, if the partition has only 2 regions with specified desired areas of, say, 0.1 and 0.9, then this sort of behavior is certainly possible.
The more likely scenario, however, is that the density vector is not oriented correctly. That is, the entries of Density::Values are not aligned with what was intended. The values should be stored so that the value of the prior density at the (i,j)th grid point appears in Density::Values[Ny*i+j]. See the Wiki for a more thorough discussion.
The current version of AreaCon, unfortunately, does not contain explicit functions for creating density vectors. This is a potential addition to future versions.
However, there are a number of freely available libraries (that are not explicitly associated with AreaCon) that contain tools for creating and working with probability density functions, especially those based on common distributions. It is relatively straightforward to utilize these, or other methods, to create a properly oriented density grid for use with AreaCon (see Wiki).
The current version of AreaCon does not contain built-in functions for creating images or video. This is a potential addition to future versions. For now, AreaCon does contain functions that will write the results of partitioning operations (and the underlying density function) to text files. Using these files, it is straightforward to write scripts in other platforms (Matlab, for example) to read in the data and plot the result.