Inner and outer rounding of Boolean operations on lattice polygonal regions (Q2575584)

New methods for the determination of geometric interval containing the exact result of set operations are presented. The authors explain the problem in form of solving the intersection of two planar lattice polygonal regions (vertices of planar lattice polygonal regions have integer coordinates). Given two intersecting lattice polygonal regions, two new lattice polygonal regions are constructed: inner and outer rounding. The exact result of intersection is contained in the geometric interval. Limits of the geometric interval are created by these two new lattice polygonal regions. To obtain the inner and outer rounding versions, the reflex vertical decomposition of the exact intersection region is used. The presented method guarantees that the biggest distance between the point on the rounded boundary and the point on the exact boundary is less than \(\sqrt{2}\). A generalization of the suggested method to general regions (vertices of general regions do not have to have integer coordinates) and to the other set operations is presented.