Cтраница 4
На плоскости задан простой многоугольник с п вершинами. Требуется найти его выпуклую оболочку. [46]
Другим краеугольным камнем нашего метода служит очень тесная взаимосвязь между вычислением видимости и задачей о жордановои сортировке. Задача жордановои сортировки для простого многоугольника Р и горизонтальной прямой L состоит в упорядочении точек пересечения дР и L в соответствии со значением х-координаты в случае, когда в качестве исходных данных служит лишь список этих точек пересечения, перечисленных в порядке их прохождения при движении вдоль дР в направлении по часовой стрелке. [47]