如何判断2D星形凸多边形并获取Star-center？求非启发式方法及Python代码

我正在处理由边界轮廓（有序x、y坐标）表示的2D图形，需要判断该图形是否为星形凸（star-convex）；若为星形凸图形，还需找到其star-center——即一个能完整看到整个图形的点，该点到所有边界点的线段均完全位于图形内部。

请问是否存在详尽的非启发式实现方法？若已有对应的Python代码则更佳。

我目前尝试的方案是基于中点可见性测试的启发式方法，核心思路为：若某点到所有边界点线段的中点均位于多边形内部，则该点为有效star-center。我从质心开始采样候选点，在包围盒内随机扰动生成更多候选点并验证，但该方法无法保证找到star-center或准确判断图形是否为星形凸，且随机采样未必能定位到正确的核区域。

以下是我实现的代码：

import numpy as np
from shapely.geometry import Polygon, Point

def is_star_convex_and_get_center(x, y, n_samples=500):
    coords = np.column_stack((x, y))
    poly = Polygon(coords)

    if not poly.is_valid or poly.area == 0:
        print("Invalid shape.")
        return None

    # Try centroid first
    candidates = [np.mean(coords, axis=0)]

    # Add some random points around the centroid
    bbox = poly.bounds
    scale = max(bbox[2] - bbox[0], bbox[3] - bbox[1])
    for _ in range(n_samples - 1):
        offset = (np.random.rand(2) - 0.5) * scale
        candidates.append(candidates[0] + offset)

    # Check visibility condition for each candidate
    for pt in candidates:
        visible = True
        for px, py in coords:
            mid = 0.5 * (pt + np.array([px, py]))
            if not poly.contains(Point(mid)):
                visible = False
                break
        if visible:
            return pt  # pt is a valid star center

    # No valid star center found
    return None

星形凸多边形的本质是核非空的简单多边形，核（Kernel）就是所有star-center的集合——核内任意一点都能完整看到整个多边形的边界及内部。要非启发式地判断星形凸并找到star-center，只需计算多边形的核：若核非空，则是星形凸，取核内任意点即可作为star-center。

核心原理 #

多边形的核是所有满足以下条件的点的集合：

• 点位于多边形内部；
• 从该点出发到多边形任意顶点的线段，均完全包含在多边形内部。

对于有序简单多边形，核可通过半平面交集计算：

1. 对多边形每条边，定义半平面为所有位于边内侧（多边形所在一侧）的点；
2. 对多边形每个顶点，定义半平面为所有位于该顶点两条邻边形成的内角内部的点；
3. 所有半平面的交集即为多边形的核。

Python实现（基于半平面交） #

以下代码依赖numpy和shapely库，可直接安装：pip install numpy shapely

import numpy as np
from shapely.geometry import Polygon, Point

def cross(o, a, b):
    """计算叉积 (a-o) × (b-o)，用于判断点的相对位置"""
    return (a[0] - o[0])*(b[1] - o[1]) - (a[1] - o[1])*(b[0] - o[0])

def line_intersection(l1_start, l1_end, l2_start, l2_end):
    """计算两条线段的交点（仅返回线段范围内的有效交点）"""
    den = (l1_start[0] - l1_end[0])*(l2_start[1] - l2_end[1]) - (l1_start[1] - l1_end[1])*(l2_start[0] - l2_end[0])
    if abs(den) < 1e-8:
        return None  # 平行或重合，无有效交点
    t_num = (l1_start[0] - l2_start[0])*(l2_start[1] - l2_end[1]) - (l1_start[1] - l2_start[1])*(l2_start[0] - l2_end[0])
    u_num = -((l1_start[0] - l1_end[0])*(l1_start[1] - l2_start[1]) - (l1_start[1] - l1_end[1])*(l1_start[0] - l2_start[0]))
    t = t_num / den
    u = u_num / den
    if 0 - 1e-8 <= t <= 1 + 1e-8 and 0 - 1e-8 <= u <= 1 + 1e-8:
        x = l1_start[0] + t*(l1_end[0] - l1_start[0])
        y = l1_start[1] + t*(l1_end[1] - l1_start[1])
        return (x, y)
    return None

def clip_polygon(subject_poly, clip_line_start, clip_line_end):
    """用半平面（裁剪线左侧）裁剪多边形，返回裁剪后的顶点列表"""
    output_list = []
    n = len(subject_poly)
    for i in range(n):
        current_pt = subject_poly[i]
        next_pt = subject_poly[(i+1)%n]
        # 判断当前点是否在裁剪线内侧（左侧）
        current_inside = cross(clip_line_start, clip_line_end, current_pt) >= -1e-8
        next_inside = cross(clip_line_start, clip_line_end, next_pt) >= -1e-8

        if current_inside:
            output_list.append(current_pt)
        # 两点跨裁剪线时，计算交点并加入结果
        if current_inside != next_inside:
            intersection = line_intersection(current_pt, next_pt, clip_line_start, clip_line_end)
            if intersection is not None:
                output_list.append(intersection)
    return output_list

def compute_polygon_kernel(poly_coords):
    """计算简单多边形的核，支持顺时针/逆时针顶点顺序"""
    # 计算有向面积，调整多边形为逆时针方向
    signed_area = 0.5 * sum(poly_coords[i][0]*poly_coords[(i+1)%len(poly_coords)][1] - 
                           poly_coords[(i+1)%len(poly_coords)][0]*poly_coords[i][1] 
                           for i in range(len(poly_coords)))
    if signed_area < 0:
        poly_coords = poly_coords[::-1]

    # 初始核设为带padding的包围盒，确保覆盖所有可能的核区域
    min_x = min(p[0] for p in poly_coords)
    max_x = max(p[0] for p in poly_coords)
    min_y = min(p[1] for p in poly_coords)
    max_y = max(p[1] for p in poly_coords)
    padding = (max_x - min_x + max_y - min_y) * 0.1
    kernel = [
        (min_x - padding, min_y - padding),
        (max_x + padding, min_y - padding),
        (max_x + padding, max_y + padding),
        (min_x - padding, max_y + padding)
    ]

    n = len(poly_coords)
    for i in range(n):
        v_i = poly_coords[i]
        v_j = poly_coords[(i+1)%n]
        v_prev = poly_coords[(i-1)%n]

        # 用边v_i->v_j的内侧半平面裁剪核
        kernel = clip_polygon(kernel, v_i, v_j)
        if not kernel:
            return None
        
        # 用顶点v_i的内角半平面裁剪：确保点在v_prev->v_i和v_i->v_j的夹角内部
        kernel = clip_polygon(kernel, v_i, v_prev)
        if not kernel:
            return None
        kernel = clip_polygon(kernel, v_i, v_j)
        if not kernel:
            return None

    # 验证核的有效性（至少为面积大于阈值的多边形）
    if len(kernel) < 3:
        return None
    kernel_poly = Polygon(kernel)
    if not kernel_poly.is_valid or kernel_poly.area < 1e-8:
        return None
    return kernel_poly

def is_star_convex_and_get_center_non_heuristic(x, y):
    coords = list(zip(x, y))
    # 验证输入多边形有效性
    poly = Polygon(coords)
    if not poly.is_valid or poly.area < 1e-8:
        print("Invalid shape.")
        return None

    kernel = compute_polygon_kernel(coords)
    if kernel is None:
        return None  # 非星形凸
    # 返回核的质心作为star-center
    centroid = kernel.centroid
    return (centroid.x, centroid.y)

使用说明 #

1. 输入坐标需为简单多边形的有序顶点（顺时针/逆时针均可，代码会自动调整方向）；
2. is_star_convex_and_get_center_non_heuristic函数返回一个star-center坐标（核的质心），返回None则表示图形无效或非星形凸；
3. 该方法通过半平面交精确计算核，无随机性，能100%准确判断星形凸并找到有效star-center。

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