Direct Calculation of Ellipse Overlap Areas for Force Based Models of Pedestrian Dynamics

Computer simulations based on models of pedestrian dynamics have become useful tools for evaluating emergency egress scenarios. 'Microscopic' models track individual pedestrian movements, which are then used to describe macroscopic pedestrian flow. Simulations enable the comparison of pedestrian facilities designs, evaluation of escape routes in various scenarios, and the study of more theoretical questions. Space-continuous, force-based models simulate interactions between pedestrians based on their separation distance and relative velocities. In a common approach, pedestrian's 'sensory zones' are modelled as ellipses, with ellipse parameters varying dynamically according to the pedestrian's direction and velocity. Interactions between individual pedestrians, and between pedestrians and the environment, are controlled in part by overlapping of sensory zones; path deviations result from superposition of repulsive and driving forces. Implementation of an ellipse-based model requires efficient calculation of ellipse overlap areas. Historically, overlap areas have been estimated by approximating ellipse boundaries with polygons or other proxy curves. More recently, an approach for direct calculation of ellipse overlap area has been described, using an algorithm for determining the area of an ellipse segment. The segment algorithm is then used to calculate the overlap area between two general ellipses, using points of intersection between the two ellipses to identify appropriate segment areas. Intersection points can be found by solving the two implicit ellipse equations simultaneously. Recent innovations to the core algorithm include effective relative position determination, increasing both efficiency and robustness of the overlap area algorithm. This paper describes the direct overlap area algorithm. Implementations in C++ are compared for speed and accuracy with proxy curve approaches. Benefits of the direct algorithm are demonstrated within the context of a force-based model of pedestrian dynamics.