扫描线算法处理圆相交：半圆表示及BST排序方法咨询

一、半圆的数据结构 #

每个半圆只需关联原圆的核心信息，加一个类型标记即可，无需复杂结构。以Python代码示例为例：

class HalfCircle:
    def __init__(self, center_x, center_y, radius, is_upper):
        self.cx = center_x  # 原圆圆心x坐标
        self.cy = center_y  # 原圆圆心y坐标
        self.r = radius     # 原圆半径
        self.is_upper = is_upper  # True代表上半圆，False代表下半圆

核心逻辑：

• 上半圆对应扫描线与圆的上交点，计算式为 y = cy + √(r² - (x - cx)²)（仅当|x - cx| ≤ r时有效）
• 下半圆对应扫描线与圆的下交点，计算式为 y = cy - √(r² - (x - cx)²)（仅当|x - cx| ≤ r时有效）

同时每个半圆绑定扫描线事件：

• 所有半圆的添加事件在圆的左边界x = cx - r处触发
• 所有半圆的移除事件在圆的右边界x = cx + r处触发

二、BST中的半圆排序规则 #

BST的核心作用是维护当前扫描线与所有半圆的交点顺序，排序依据是当前扫描线位置x处，半圆对应的y坐标值，具体规则：

1. 基础排序逻辑：按y值从大到小排列（从上到下），只有相邻的半圆在扫描线移动时才可能产生交点，方便后续检测。
2. 精度友好的比较方式：
   直接开根号易引入浮点误差，可通过对应计算式比较两个半圆h1和h2的y值：
   • 若均为上半圆：比较 h1.cy + sqrt(h1.r² - (x - h1.cx)²) 与 h2.cy + sqrt(h2.r² - (x - h2.cx)²)
   • 若均为下半圆：比较 h1.cy - sqrt(h1.r² - (x - h1.cx)²) 与 h2.cy - sqrt(h2.r² - (x - h2.cx)²)
   • 若一个上半圆一个下半圆：上半圆的y值必然大于下半圆，直接按此排序
3. 相等情况处理：当两个半圆在当前x处y值相等（即扫描线经过两圆交点），需指定稳定排序依据（比如按圆心x坐标从小到大，或原圆的唯一ID），避免重复检测同一交点。

补充说明 #

拆分上下半圆的本质是把每个圆的两个交点拆成独立的“弧段交点”，让扫描线的BST中每个元素对应唯一交点，从而准确维护相邻弧的关系，这是扫描线算法处理圆交点的核心技巧。

内容的提问来源于stack exchange，提问作者optional