试题详情
简答题平面扫描（plane sweep）技术主要解决什么问题？其主要步骤？
  • 主要解决的是如何在过滤阶段中尽可能多的淘汰不符合条件的对，从而减少几何计算的计算代价。
    Step1：从左至右移动一条扫描线（例如，垂直于x轴的线），停在R∪S的第一个元素处。这就是具有最小T.xl值的矩形T，例子为是矩形R4。
    Step2：搜索S中已排序的矩形，直到抵达第一个矩形Sf，这里有Sf.xl>T.xu。显然，对于所有1≤j Step 3：如果对任意 l≤j≤f，关系 [T．yl，T．yu] ∩[Sj．yl，Sj．yu]存在，则 Sj 与 T 相交。因此，这一步就确定了 R4 与 S2 的确是交叠的，并且 < R4，S2>是连接结果的一部分。记录所有这样的信息，然后将矩形 T（R4）从集合 R∪S 中去掉，它不再需要参与结果集中的其他相交对。
    Step4：继续移动扫描线来穿过集合R∪S，直至碰到下一个矩形，在本例中是S2。这时进行步骤2和3。
    Step5：当R∪S=∅时，处理结束；

  • 关注下方微信公众号，在线模考后查看

热门试题