THE IMPLEMENTATION AND APPLICATION OF AN ALGORITHM FOR STRAIGHT LINES SUBDIVING PLANES

A data structure of binary tree called " region tree " is introduced and applied to express planar subdivision by straight lines. An algorithm for straight lines subdividing planes is presented and applied to solve several problems, they are: point location in the planar subdivision by straight lines, intersection of half-planes, convex decomposition of a simple polygon, intersection of two simple polygons.