如何消除多边形的圆角，计算对应的尖角？

针对你提到的暴力解法效率低、易误判的问题，结合垂直扫描线无法预知后续边的限制，整理几个更高效的优化思路：

1. 预处理边特征，减少实时计算开销 #

提前给每条边计算好三个关键属性：

• 长度：直接用两点距离公式计算并存储
• 类型标记：标记为水平边（H）、垂直边（V）或倾斜边
• 斜率特征：算出斜率所在象限（比如0-90°为象限1，90-180°为象限2等），再将斜率归一化到对应象限的0-90°范围（比如象限2的120°归一化为60°），方便后续判断单调性

同时统计所有边的长度分布，取常规边长度阈值（比如取所有边长度的90分位数，短边长度低于这个值才纳入圆角候选），避免把本来就短的常规边误判为圆角的一部分。

2. 状态机跟踪圆角区域，避免全量遍历 #

定义三个状态控制遍历流程，不用追到结尾才判断：

• 正常遍历状态：遇到H/V边就记录它的端点和方向；遇到符合长度阈值的倾斜边，切换到「候选起始状态」，同时存好前一条H/V边的信息。
• 候选起始状态：检查下一条倾斜边的斜率是否和上一条在同一象限，且斜率单调（比如象限1里斜率从30°涨到40°，属于严格递增）。符合条件就进入「圆角跟踪状态」，否则直接退回正常状态，放弃当前候选。
• 圆角跟踪状态：继续检查后续倾斜边的长度、象限、斜率单调性。一旦遇到H/V边，先看中间收集的倾斜边数量是否达标（比如至少3条，避免误判1-2条偶然短边），达标就认定是圆角：删除中间所有倾斜边，把前后两条H/V边延长到交点，替换原有的边序列；如果遇到不符合条件的边（长度超标、斜率跨象限、单调性断裂），直接放弃跟踪，退回正常状态，保留所有边。

3. 滑动窗口+单调队列，优化斜率单调性检查 #

不用逐个比对所有历史倾斜边的斜率，用固定大小的滑动窗口（窗口大小设为常规边能容纳的短边最大数量，比如常规边是短边的10倍，窗口设15），窗口内维护一个单调队列：

• 比如象限1的圆角，队列里的斜率必须严格递增，一旦新边的斜率比队列最后一个小，直接判定当前窗口不属于圆角，重置状态。
  这样不用遍历所有之前的边，大大减少计算量，适合大规模数据处理。

4. 增加双重校验，减少误判 #

• 最小边数限制：要求圆角的中间倾斜边至少有3条，过滤掉偶然的短边组合。
• 交点合理性校验：延长前后H/V边得到交点后，检查这个交点和原圆角区域的首尾边界点距离是否在短边长度的2倍以内，确保是原本的尖角位置，而不是错误延长出来的点。

伪代码示例 #

import math

def restore_sharp_corners(edges):
    # 预处理单条边的特征
    def precompute_edge(edge):
        x1, y1 = edge["start"]
        x2, y2 = edge["end"]
        length = ((x2-x1)**2 + (y2-y1)**2)**0.5
        is_hv = (x1 == x2) or (y1 == y2)
        
        # 计算象限和归一化斜率
        dx = x2 - x1
        dy = y2 - y1
        quadrant = 0
        norm_slope = 0.0
        if dx == 0:
            quadrant = 2 if dy > 0 else 4
            norm_slope = 90.0
        elif dy == 0:
            quadrant = 1 if dx > 0 else 3
            norm_slope = 0.0
        else:
            slope = abs(dy/dx)
            norm_slope = math.degrees(math.atan(slope))
            if dx > 0 and dy > 0:
                quadrant = 1
            elif dx < 0 and dy > 0:
                quadrant = 2
            elif dx < 0 and dy < 0:
                quadrant = 3
            else:
                quadrant = 4
        
        return {
            "start": (x1, y1),
            "end": (x2, y2),
            "length": length,
            "is_hv": is_hv,
            "quadrant": quadrant,
            "norm_slope": norm_slope
        }
    
    processed_edges = [precompute_edge(e) for e in edges]
    # 计算长度阈值（取90分位数）
    lengths = [e["length"] for e in processed_edges]
    length_threshold = sorted(lengths)[int(len(lengths)*0.9)] if lengths else 0
    min_corner_edges = 3
    
    state = "normal"
    prev_hv = None
    corner_edges = []
    i = 0
    
    while i < len(processed_edges):
        current = processed_edges[i]
        if state == "normal":
            if current["is_hv"]:
                prev_hv = current
                i += 1
            elif current["length"] < length_threshold:
                state = "candidate"
                corner_edges.append(current)
                i += 1
            else:
                i += 1
        
        elif state == "candidate":
            if current["length"] >= length_threshold:
                state = "normal"
                corner_edges = []
                i += 1
                continue
            # 检查同象限和单调性
            last_corner = corner_edges[-1]
            if current["quadrant"] != last_corner["quadrant"]:
                state = "normal"
                corner_edges = []
                i += 1
                continue
            # 象限1、3斜率递增，象限2、4斜率递减（适配圆角方向）
            if (current["quadrant"] in [1,3] and current["norm_slope"] <= last_corner["norm_slope"]) or \
               (current["quadrant"] in [2,4] and current["norm_slope"] >= last_corner["norm_slope"]):
                state = "normal"
                corner_edges = []
                i += 1
                continue
            corner_edges.append(current)
            state = "tracking"
            i += 1
        
        elif state == "tracking":
            if current["is_hv"]:
                if len(corner_edges) >= min_corner_edges:
                    # 计算水平/垂直边的交点
                    def get_intersection(hv1, hv2):
                        if hv1["start"][1] == hv1["end"][1]:
                            # hv1是水平边，hv2是垂直边
                            return (hv2["start"][0], hv1["start"][1])
                        else:
                            # hv1是垂直边，hv2是水平边
                            return (hv1["start"][0], hv2["start"][1])
                    
                    intersection = get_intersection(prev_hv, current)
                    if intersection:
                        prev_hv["end"] = intersection
                        current["start"] = intersection
                        # 删除中间的圆角边
                        del processed_edges[i - len(corner_edges) : i]
                        i -= len(corner_edges)
                # 重置状态
                state = "normal"
                corner_edges = []
                i += 1
            
            else:
                if current["length"] >= length_threshold:
                    state = "normal"
                    corner_edges = []
                    i += 1
                    continue
                last_corner = corner_edges[-1]
                if current["quadrant"] != last_corner["quadrant"]:
                    state = "normal"
                    corner_edges = []
                    i += 1
                    continue
                if (current["quadrant"] in [1,3] and current["norm_slope"] <= last_corner["norm_slope"]) or \
                   (current["quadrant"] in [2,4] and current["norm_slope"] >= last_corner["norm_slope"]):
                    state = "normal"
                    corner_edges = []
                    i += 1
                    continue
                corner_edges.append(current)
                i += 1
    
    # 转换回原边格式
    restored_edges = [{"start": e["start"], "end": e["end"]} for e in processed_edges]
    return restored_edges

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