кто-нибудь занком с методом декомпозиции на монотонные полигоны методом сканирующей линии?
Я пользуюсь книгой "Computational Geometry. Algorithms and applications' 3rd edition, ы ней есть целая глава, точнее часть главы, посвящённая этой теме. В ней "светила" американской науки объясняют "простой" алгоритм разбиение на монотоныые полигоны.
Одной из подзадач данного алгоритма является нахождение ребра (edge), лежащего слева от заданной вершины. Для решения этой задачи автор предлагает следующее:
In the approach above, we need to find the edge to the left of each vertex.
Therefore we store the edges of P intersecting the sweep line in the leaves
of a dynamic binary search tree T. The left-to-right order of the leaves of
T corresponds to the left-to-right order of the edges. Because we are only
interested in edges to the left of split and merge vertices we only need to store
edges in T that have the interior of P to their right.
возможно я чего-то не понимаю, но что такое left-to-right порядок для сторон полигона и как они должны располагаться в дереве, чтоб можно было найти сторону, лежащую слева от заданной вершины?
может вы сталкивались с этим алгоритмом или понимаете что хотел донести до читателя автор, поделитесь пожалуйста, а то мне дипом скоро сдавать
Заранее большое спасибо.