如何检测2D曲线上被点光源遮挡的顶点（规避射线检测）

你的问题根源在于仅用单向的累积极值判断所有顶点——右侧（x > 光源x）从左到右的累积最大极角有效，但左侧（x < 光源x）需要反向遍历并维护累积最小极角，才能准确检测遮挡。

核心逻辑 #

以点光源为原点，计算每个顶点的极角（用math.atan2(dy, dx)，范围[-π, π]，正右为0，逆时针为正）：

• 右侧顶点：按x从近到远（靠近光源到远离）遍历，维护极角的累积最大值。若当前点极角小于该最大值，说明被前方更靠上的顶点遮挡。
• 左侧顶点：按x从近到远遍历（即从靠近光源的x=8到远离的x=1），维护极角的累积最小值。若当前点极角大于该最小值，说明被前方更靠下的顶点遮挡。

Python实现 #

import math

def detect_occluded_vertices(x_list, y_list, light_x, light_y):
    # 确保顶点按x递增排序（兼容未排序输入）
    sorted_vertices = sorted(zip(x_list, y_list), key=lambda p: p[0])
    x_sorted, y_sorted = zip(*sorted_vertices)
    
    # 计算每个顶点相对光源的极角
    angles = []
    for x, y in sorted_vertices:
        dx = x - light_x
        dy = y - light_y
        angles.append(math.atan2(dy, dx))
    
    occluded_x = set()
    
    # 处理右侧顶点（x > 光源x）
    right_indices = [i for i, x in enumerate(x_sorted) if x > light_x]
    if right_indices:
        max_angle = -math.inf
        for i in right_indices:
            current_angle = angles[i]
            current_x = x_sorted[i]
            if current_angle < max_angle:
                occluded_x.add(current_x)
            else:
                max_angle = current_angle
    
    # 处理左侧顶点（x < 光源x）
    left_indices = [i for i, x in enumerate(x_sorted) if x < light_x]
    if left_indices:
        # 反转索引，实现从近到远（x从大到小）遍历
        min_angle = math.inf
        for i in reversed(left_indices):
            current_angle = angles[i]
            current_x = x_sorted[i]
            if current_angle > min_angle:
                occluded_x.add(current_x)
            else:
                min_angle = current_angle
    
    return sorted(occluded_x)

# 测试示例
x = [1,2,3,4,5,6,7,8,13,18,19,20,21,22,23,24]
y = [-2,-3,-10,-1,-2,2,3,4,7,5,5,5,3,1,1,1]
light_point = (11,16)
print("被遮挡的顶点x值：", detect_occluded_vertices(x, y, *light_point))

结果验证 #

运行代码会输出[3,5,21,22,23]，完全覆盖你提到的左侧失效顶点（x=3、5）和右侧遮挡顶点，且全程未使用射线检测，符合性能要求。

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