algorithm - 平面扫描算法 - 位于磁盘之外的点

Question

LetD是一组n不相交的磁盘并且P是一组n点。

如何设计一种O(n*log(n))平面扫描算法来报告P位于所有磁盘之外的每个点？

标签： algorithmmathcomputational-geometry

Answer 1

从上到下对点进行排序，并按其顶部纵坐标对磁盘进行排序。“活动列表”包含与当前点水平相交的所有磁盘。

您将从一个点到另一个点，每次更新活动列表（检查新条目和退出）。

如果当前点位于活动列表中的所有磁盘之外，则当前点位于所有磁盘之外。