On the Area of Overlap of Translated Polygons

摘要

Given two simple polygonsPandQin the plane and a translation vectort∈R2, thearea-of-overlapfunction ofPandQis the function Ar(t) = Area(P∩ (t+Q)), wheret+QdenotesQtranslated byt. This function has a number of applications in areas such as motion planning and object recognition. We present a number of mathematical results regarding this function. We also provide efficient algorithms for computing a representation of this function and for tracing contour curves of constant area-of-overlap.