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

Компьютеры - Алгоритм Бентли Оттмана - Обработка вертикальных отрезков

Возникает проблема с вертикальным отрезком в том смысле как его сравнивать на выше/ниже с пересекающими отрезками. Для этого можно, например, считать, что если точка пересечения вертикального с не вертикальным отрезков находится ниже текущей координаты y точки события, то вертикальный отрезок находится выше, если точка пересечения выше текущей координаты y точки события, то вертикальный отрезок считается ниже пересекающего его. Если текущая координата y равна координате y точки события, то при удалении отрезка считать, что вертикальный отрезок ниже, при вставке же считать, что он выше.

Квадрат памяти

В худшем случае, когда, например, все отрезки, пересекаясь между собой, образуют прямоугольную сетку, будет точек пересечений, которые надо будет хранить. Чтобы избежать использования квадрата памяти в алгоритме, можно удалять точку пересечения отрезков, которые временно перестают быть соседними при данном положении выметающей прямой. Эти точки все равно будут снова найдены при последующих шагах алгоритма, когда данные отрезки снова станут соседними.