在Unity中用C#实现多边形内部顶点可见性连线（适配Dijkstra算法）

一、射线检测的正确实现方案（Unity适配） #

针对你之前射线检测失败的问题，核心是要处理顶点/边的误判问题，以下是可落地的步骤：

• 顶点坐标转换：从PolygonCollider2D获取的points是局部坐标，需先通过TransformPoint转换为世界坐标，确保射线检测空间统一。
• 两两顶点配对检测：遍历所有顶点对（A,B），执行以下逻辑：
  1. 对射线起点和终点做微小偏移（比如沿AB方向偏移0.01单位），避免射线刚好落在顶点或边上导致误触发碰撞。
  2. 使用Physics2D.RaycastAll发射从偏移后起点到偏移后终点的射线，限制检测距离为线段长度。
  3. 过滤碰撞结果：仅关注目标PolygonCollider2D的碰撞，若碰撞点仅为终点B（误差范围内），则判定连线合法；若存在其他碰撞点，说明连线穿出多边形，丢弃。
• 配置注意：确保目标PolygonCollider2D的isTrigger设为false，可通过Layer过滤避免检测到其他无关碰撞体。

示例代码 #

using UnityEngine;
using System.Collections.Generic;

public class VertexVisibilityChecker : MonoBehaviour
{
    public PolygonCollider2D targetPolygon;
    private const float OffsetDistance = 0.01f;
    private const float PositionTolerance = 0.02f;

    public List<(Vector2, Vector2)> GetValidInternalEdges()
    {
        var validEdges = new List<(Vector2, Vector2)>();
        var worldVertices = GetWorldVertices();
        int vertexCount = worldVertices.Length;

        for (int i = 0; i < vertexCount; i++)
        {
            for (int j = i + 1; j < vertexCount; j++)
            {
                Vector2 a = worldVertices[i];
                Vector2 b = worldVertices[j];
                if (IsValidInternalEdge(a, b))
                {
                    validEdges.Add((a, b));
                }
            }
        }
        return validEdges;
    }

    private bool IsValidInternalEdge(Vector2 a, Vector2 b)
    {
        Vector2 direction = (b - a).normalized;
        Vector2 rayStart = a + direction * OffsetDistance;
        Vector2 rayEnd = b - direction * OffsetDistance;
        float rayLength = Vector2.Distance(rayStart, rayEnd);

        RaycastHit2D[] hits = Physics2D.RaycastAll(rayStart, direction, rayLength);

        foreach (var hit in hits)
        {
            if (hit.collider != targetPolygon) continue;
            // 碰撞点不是终点B，说明连线穿过多边形边界
            if (Vector2.Distance(hit.point, b) > PositionTolerance)
            {
                return false;
            }
        }
        return true;
    }

    private Vector2[] GetWorldVertices()
    {
        Vector2[] localVertices = targetPolygon.points;
        Vector2[] worldVertices = new Vector2[localVertices.Length];
        for (int i = 0; i < localVertices.Length; i++)
        {
            worldVertices[i] = targetPolygon.transform.TransformPoint(localVertices[i]);
        }
        return worldVertices;
    }
}

二、纯数学方法（计算几何实现） #

不依赖Unity物理系统，通过计算几何规则直接判断线段合法性，核心逻辑分为两步：

• 线段无跨边交点：对顶点对(A,B)，检查线段AB是否与多边形的任意非邻边存在非端点交点（用跨立实验实现）。若存在，说明连线穿出多边形，不合法。
• 线段中点在多边形内部：用射线法判断AB中点是否在多边形内部（从中点向x轴正方向发射射线，统计与多边形边的交点数，奇数则在内部）。
• 优化点：可先跳过相邻顶点对（默认合法，属于多边形边），减少计算量。

核心计算函数示例 #

// 跨立实验判断两条线段是否存在非端点交点
private bool SegmentsCross(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2)
{
    float ccw1 = Cross(a2 - a1, b1 - a1);
    float ccw2 = Cross(a2 - a1, b2 - a1);
    float ccw3 = Cross(b2 - b1, a1 - b1);
    float ccw4 = Cross(b2 - b1, a2 - b1);

    // 两线段互相跨立，无共线情况
    return (ccw1 * ccw2 < 0) && (ccw3 * ccw4 < 0);
}

// 计算二维叉积
private float Cross(Vector2 v1, Vector2 v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

// 射线法判断点是否在多边形内部
private bool PointInsidePolygon(Vector2 point, Vector2[] polygonVertices)
{
    bool isInside = false;
    int vertexCount = polygonVertices.Length;
    for (int i = 0, j = vertexCount - 1; i < vertexCount; j = i++)
    {
        bool yCross = (polygonVertices[i].y > point.y) != (polygonVertices[j].y > point.y);
        bool xCross = point.x < (polygonVertices[j].x - polygonVertices[i].x) * (point.y - polygonVertices[i].y) / (polygonVertices[j].y - polygonVertices[i].y) + polygonVertices[i].x;
        if (yCross && xCross)
        {
            isInside = !isInside;
        }
    }
    return isInside;
}

方法对比 #

• 射线检测：Unity环境下快速落地，无需处理复杂计算几何边界，但依赖物理系统配置，精度受物理引擎影响。
• 纯数学方法：不依赖Unity环境，精度可控，但需处理浮点精度误差（可通过引入 tolerance 值解决），适合对性能或独立性要求高的场景。

内容的提问来源于stack exchange，提问作者Mike The Elf