简介
扫描线算法（Sweep Line Algorithm）或平面扫描算法（Plane Sweep Algorithm）是一种算法模式，虚拟扫描线或扫描面来解决欧几里德空间中的各种问题，一般被用来解决图形面积，周长等问题，是计算几何中的关键技术之一。
# 简介该算法通过扫描图像的每一条水平线，找到与多边形相交的线段，并确定相应的填充区域。
# 基本步骤确定多边形的边界：将多边形的顶点按照从上到下的顺序排序，并确定每条边的起点和终点。
初始化扫描线：从多边形的最高顶点开始，按照从上到下的顺序，依次扫描每一条水平线。
寻找交点：对于当前扫描线，确定与多边形边界相交的线段，即找到与扫描线相交的边。通过计算扫描线与多边形边的交点，得到交点的 x 坐标。
确定填充区域：根据交点的 x 坐标，确定相邻两个交点之间的区域为需要填充的区域。
进行颜色填充：在确定的填充区域内填充指定的颜色。
更新扫描线：将扫描线向下移动一条水平线，重复步骤 3-6，直到扫描到多边形的最低顶点。
# 算法实现//天际线问题
import heapq
from typing import List
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
result = list()
if not buildings:
return result
boundaries = list()
for building in buildings:
boundaries.append((building[0], building[2]))
boundaries.append((building[1], -building[2]))
# 排序规则：x坐标小的在前面，x坐标相同时，高度较大的在前面
boundaries.sort(key=lambda x: (x[0], -x[1]))
pre_height = 0
# 这里我们需要维护一个大根堆，使较大的高度在堆顶
pq = list()
heapq.heappush(pq, 0)
for boundary in boundaries:
# 如果遇到左侧的边界，就将其加入优先级队列
if boundary[1] > 0:
# 大根堆，所以要取高度的负值
heapq.heappush(pq, -boundary[1])
# 如果遇到右侧的边界，就将右侧的边界出队
else:
# 移除该右侧边界
pq.remove(boundary[1])
heapq.heapify(pq)
# 获取堆顶的元素的高度，注意取负值
current = -pq[0]
if current != pre_height:
result.append([boundary[0], current])
pre_height = current
return result
参考链接：天际线问题open in new window