An approach to triangulate area bounded simple polygons

摘要

This In the paper we propose optimal algorithm for area triangulation between m arbitrary polygons on the plane with time complexity O(NlogN). The efficiency of the algorithm is achieved by reducing the problem to the triangulation of simple polygons with holes. A simple polygon with holes we triangulate using the monotone chains method. It allows getting a simple implementation.