平面扫描算法:如何在交点后对线段进行排序 [英] Plane sweep algorithm: How to order the segments after intersection point

问题描述

我正在尝试根据这本书在C ++代码中实现分段相交的平面扫描算法:http://www.cs.uu.nl/geobook/.他们建议使用平衡的二叉搜索树实现平面扫描的状态结构.

我正在使用std :: set结构来实现状态结构，但是我在重新排序包含点"p"且其上端点是点"p"的段时遇到了问题.它们具有相同的坐标点，这意味着我不能将它们插入到std :: set中，因为它不允许重复的值...我试图将它们的下端点插入其中，但是它们将失去顺序它们与"p"正下方的扫掠线相交.

本书中的伪代码表示以下内容:

6. 将U(p)∪C(p)中的线段插入到Tao中.Tao中的片段顺序应与它们相交的顺序相对应位于p下方的扫掠线.如果有一个水平线段在所有包含p的句段中排在最后.
7. (*删除并重新插入C(p)的片段会颠倒它们的顺序.*)

我不知道它们将如何颠倒顺序.当我在状态结构中插入句段时，我正在按它们的x上端点坐标对它们进行排序.我不知道交叉路口后如何调换订单.

有什么主意吗?

更新:这本书在这里: https://books.google.com/books?id= C8zaAWuOIOcC ，但是有些页面没有出现.它位于第2章第24、25和26页.希望它有助于提供一些背景信息

最好

解决方案

用作平面扫描状态数据结构的 std :: set 的排序谓词必须按以下方式工作:

1. 必须(动态)计算扫掠线当前位置的给定线段与扫掠线相交的坐标.

2. 在打结的情况下(当两个线段似乎在同一坐标上与扫掠线相交时)，还必须比较两个线段的角度-这样可以找出线段在扫描中的顺序.扫描线将来位置的状态.

请注意，上述要求1.意味着谓词对象必须持有对扫掠线位置变量的引用，以便它可以在扫掠线前进时正确比较段.扫行位置不能存储在谓词本身中，因为这样您将无法从算法中对其进行更新( std :: set 无法通过引用访问其谓词).

编辑

请注意，算法中仍然有维护段中正确顺序(即按需交换)的责任-具有这样谓词的 std :: set 不会自动对其重新排序元素.

I'm trying to implement in C++ code the plane sweep algorithm for segment intersections based on this book: http://www.cs.uu.nl/geobook/. They suggest to implement the status structure of the plane sweep using a balanced binary search tree.

I'm using the std::set structure to implement the status structure but I'm having problems to reorder the segments that contain the point "p" and their upper endpoint is the point "p". They have the same coordinate point which means that I cannot insert them in std::set because it doesn't allow repetitive values... I tried to insert them with their lower endpoint but then, they are going to lose the order in which they intersect by a sweep line just below "p".

The pseudo-code that is in the book says the following:

6. Insert the segments in U(p) ∪C(p) into Tao. The order of the segments in Tao should correspond to the order in which they are intersected by a sweep line just below p. If there is a horizontal segment, it comes last among all segments containing p.
7. (∗ Deleting and re-inserting the segments of C(p) reverses their order. ∗)

I don't know how they are going to reverse their order.. As I insert segments in the status structure, I'm sorting them by their x upper endpoint coordinate. I don't know how to swap their order after an intersection.

Any idea?

Update: The book is here: https://books.google.com/books?id=C8zaAWuOIOcC but there a some pages that don't appear. It is on chapter 2, pages 24, 25 and 26. Hope it helps to give some context

Best,

解决方案

The sorting predicate for the std::set used as the plane sweep status data structure must work as follows:

1. It must (dynamically) compute the coordinate of the intersection of a given segment with the sweep-line for the current position of the sweep-line.

2. In case of a tie (when two segments appear to intersect the sweep line at the same coordinate) it must also compare the angles of the two segments - this will allow to find out the order of the segments in the status for future positions of the sweep line.

Note that the requirement 1. above means that the predicate object must hold a reference to the sweep-line position variable, so that it can compare segments correctly as the sweep-line advances. The sweep-line position cannot be stored in the predicate itself because then you will be unable to update it from your algorithm (std::set doesn't provide access to its predicate by reference).

EDIT

Note that the responsibility of maintaining correct order of segments in the set (i.e. swapping them as required) is still with the algorithm - an std::set with such a predicate will not automatically reorder its elements.

这篇关于平面扫描算法:如何在交点后对线段进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！