Thesis Defence: Polyline Approximation by Lines and Circular Arcs
August 26 at 9:00 am - 1:00 pm
Pantea Fatemi, supervised by Dr. Yves Lucet, will defend their thesis titled “Polyline Approximation by Lines and Circular Arcs” in partial fulfillment of the requirements for the degree of Master of Science in Computer Science.
An abstract for Pantea Fatemi’s thesis is included below.
Defences are open to all members of the campus community as well as the general public. Registration is not required for in-person defences.
Abstract
The horizontal alignment design of roads requires smooth curves that satisfy geometric constraints while minimizing construction costs. Traditional approaches rely on manual design or heuristic methods that may not achieve optimal solutions. This thesis addresses the problem of approximating a given polyline with alternating line segments and circular arcs while maintaining G1 continuity, staying within a specified tolerance, respecting a minimum radius and reducing the number of segments.
We develop a hybrid approximation framework that combines classical computational geometry algorithms with dynamic programming. The approach consists of three main components. First, we use the classical simplification algorithms to identify key vertices in the polyline, providing a complexity measure that guides subsequent processing. Second, we introduce an adaptive candidate generation strategy that allocates junction points based on the pivot locations, curvature-weighted interpolation, and high-curvature vertices. Restricting the optimization to these key vertices, rather than all input points, drastically reduces its computation time. This three-source allocation ensures adequate coverage in geometrically complex regions. Third, a dynamic programming solver is implemented to construct a G1-continuous path through candidate locations using alternating line and circular arc segments. On a benchmark of 29 real-world road alignments, our framework reduces the number of segments by over 60% relative to commercial software, while remaining fast enough for interactive design.
