Evaluating the boundary and covering degree of planar Minkowski sums and other geometrical convolutions

摘要: Algorithms are developed, based on topological principles, to evaluate the boundary and ''internal structure'' of Minkowski sum two planar curves. A graph isotopic envelope curve is constructed by computing its characteristic points. The edges this in one-to-one correspondence with a set monotone segments. simple formula allows degree be assigned each face defined graph, indicating number times points covered sum. can then identified that separate faces zero non-zero degree, segments corresponding these approximated any desired geometrical accuracy. For applications require only boundary, algorithm minimizes computations ''internal'' edges, do not contribute final boundary. In other applications, internal structure interest, provides comprehensive information covering for different regions within Extensions computation sums R^3, forms convolution, briefly discussed.