EL-REP: A New 2D Geometric Decomposition Scheme and Its Applications.

Area of Science:

• Computational Geometry
• Computer Graphics
• Geometric Algorithms

Background:

• Polygon decomposition is fundamental in computational geometry.
• Existing methods face challenges with complex polygon types (e.g., holes, multiple shells).
• Efficient algorithms are needed for applications like collision detection and spatial indexing.

Purpose of the Study:

• To introduce and describe the Edge-Loop Decomposition (EL-REP) scheme.
• To detail a method for constructing the EL-REP for various simple polygons.
• To highlight key applications of the EL-REP.

Main Methods:

• The study presents a novel 2D decomposition scheme called EL-REP.
• A detailed construction method for EL-REP is described.
• The scheme is designed to handle simple polygons, including those with holes or multiple shells.

Main Results:

• The EL-REP is computable for diverse simple polygons (convex, nonconvex, with/without holes, multiple shells).
• The paper details the construction algorithm for the EL-REP.
• Demonstrated applications include fast point-in-polygon tests, 2D location, polygon triangulation, and collision detection.

Conclusions:

• The EL-REP is a versatile and efficient 2D polygon decomposition technique.
• Its ability to handle complex polygons makes it suitable for various geometric applications.
• EL-REP provides a foundation for improved performance in computational geometry tasks.