= Sweep-line algorithm
= Sweep line
{synonym}
A <sweep-line algorithm> processes geometric events in the order a conceptual line crosses a <plane>. It keeps an event queue and a status describing objects intersecting the current line. For horizontal and vertical <line segments>, sweep left to right: insert a horizontal segment at its left endpoint, query active heights at a vertical segment, and delete horizontals at their right endpoints. A balanced search structure supports the updates and range reporting. Equal-coordinate event ordering determines whether endpoint contacts count. The method reduces a two-dimensional problem to a changing one-dimensional ordering rather than physically sampling every line position.
Back to article page
