Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Бентли Оттмана

Алгоритм Бентли — Оттмана позволяет найти все точки пересечений прямолинейных отрезков на плоскости. В нем применяется метод выметающей прямой. В методе используется вертикальная выметающая прямая движущаяся слева направо, при этом отрезки, которые она пересекает при данной координате x, можно упорядочить по координате y, тем самым их можно сравнивать между собой. Это сравнение можно осуществить, например, используя уравнение прямой, проходящей через две точки: , где x₁, y₁ и x₂, y₂ — координаты, соответственно, первой и второй точек отрезка. Выметающая прямая перемещается по так называемым точкам событиям. После точки пересечения отрезки следует менять местами, так как, например, самый верхний из пересекающихся отрезков после точки пересечения становится самым нижним. Приведенный ниже алгоритм не рассчитан на случай, когда два отрезка пересекаются больше, чем в одной точке.

NB Выметающую прямую можно также представить как горизонтальную, движущуюся сверху вниз по координате y, и сравнивать пересекающие ее отрезки по координате x.

Пересечение отрезков