检查线段是否与简单多边形相交的暴力方法

• 下载 simple_implementation.zip - 2.6 KB

介绍 

检查一条线段是否真的与多边形相交或位于多边形内部，对于程序员来说一直是一个难题。我们很难找到一个通用的线段-多边形相交检测算法。我的文章旨在提出一种测试线段是否与多边形相交的想法，该方法仅适用于简单的计算机图形多边形（包括凸多边形和凹多边形）。

背景

约定

本文中使用的伪代码是一种类似 Java 的语言。它是结构化编程和面向对象编程的混合体。假设点、线段（从现在开始我将使用“段”）和多边形都实现了基本方法，例如段-段相交、段包含点、多边形包含点、段的长度、中点……

致谢

当其一部分与多边形相交时，该线段即与多边形相交。当线段穿过多边形或位于多边形内部时，该线段即与多边形相交。当线段与多边形至少有一个非端点的交点时，该线段即穿过多边形。当线段的所有点都位于多边形内部时，该线段即位于多边形内部（线段的端点可以位于多边形边界上）。多边形的这些边不在此多边形内部。

新解决方案

想法

从致谢中，我们可以得出以下几点：

• 当线段穿过多边形或位于多边形内部时，该线段即与多边形相交。
• 当线段的所有点都位于多边形内部时，该线段即位于多边形内部。

结论是：如果线段的一部分位于多边形内部，则该线段与多边形相交。因此，我们的工作是将原始线段分割成更小的部分，以检查是否有部分位于多边形内部。

哪种线段可以位于多边形内部？

如果一个线段完全位于多边形内部或外部，那么它与多边形的所有边都没有交点（线段的端点可以位于多边形边界上）。我们只能确定这类线段是否位于多边形内部/外部。

如何分割线段？

对于每条线段，我们尝试找到它与待检测多边形一条边的交点。如果存在交点且该交点不是该线段的端点，则将线段分割成两部分：一部分从起点到交点，另一部分从交点到终点（起点和终点是线段的两个端点）。重复执行这些步骤，直到线段与多边形的边没有交点为止。

图 4 是一个很好的例子：线段 MN 与边 AB 相交，O 是交点。我们将 MN 分割成 MO 和 ON。

检查一部分是否在多边形内部

我们正在检测的线段 s 是一个大线段的小部分。条件是“线段 s 与多边形 p 没有交集”（如果线段 s 的端点位于多边形 p 的边界上，则没有问题）。

如果该部分是多边形的一条边，则它不在内部。否则，该部分的每个点都位于同一侧（端点可以位于多边形边界上）。我们可以选择任意一点（我选择了中点），整个部分将相对于该点位于同一侧。伪代码

public boolean Cover(Polygon p, Segment s)
{
    // if segment is a edge of this polygon
    for (int i=0; i< p.Edges.count; i++)
        if (s == p.Edges[i])
            return false;
    // segment cannot be spitted
    // so, if the midpoint is inside polygon, whole segment will inside
    Point mid = s.MidPoint();
    if (p.Contains(mid))
        return true;
    else
        return false;
}

检查线段是否与多边形相交

步骤 1：尝试将线段分割成两部分。如果可能，转到步骤 2，否则转到步骤 4。

步骤 2：递归检查第一部分是否与多边形相交。如果不相交，转到步骤 3，否则线段与多边形相交。停止算法。

步骤 3：递归检查第二部分是否与多边形相交。如果不相交，则线段不与多边形相交，否则线段与多边形相交。停止算法。

步骤 4：检查线段是否位于多边形内部。如果位于内部，则线段与多边形相交，否则不相交。停止算法。

伪代码

public boolean Cross(Segment s, Polygon p) {
    // split the big segment into parts
    Point split_point = null;
    for (int i=0; i< p.Edges.count; i++)
    {
        Segment edge = p.Edges[i];
        // find intersection that is not end point of segment
        split_point = s.InterSectionExceptThisEnds(edge);
        if (split_point != null)
            break;
    }
    // if we can split
    if (split_point != null) // then check each part
    {
        boolean first_part = Cross(new Segment(s.p1,split_point), p);
        // a part intersects means whole segment intersects
        if (first_part == true)
            return first_part;
        // if first part doesn't intersect, it depends on second one
        boolean second_part = Cross(new Segment(split_point,s.p2), p);
        return second_part;
    } 
    // cannot split this segment
    else
    {
        boolean result = Cover (p, s);
        return result;
    }
}

以图 4 为例，逐步进行。

1. 首先，我们将 MN 分割成 MO 和 ON。
2. 然后我们检查 MO。MO 无法分割，并且它位于多边形外部。
3. 所以我们必须检查 ON。
4. ON 可以分割成 OP 和 PN。
5. OP 无法分割，并且它位于多边形内部。
6. OP 是 ON 的一部分，因此 ON 与多边形相交。
7. ON 是 MN 的第二部分，然后我们确定 MN 与多边形相交。

结论

该算法可以检查线段是否与多边形相交，并且程序员可以修改它来确定线段是位于内部还是穿过多边形，并获取存在的交点。请勿将其应用于复杂多边形（自相交或有孔的多边形）。但程序员可以将自相交多边形分离成一些简单多边形，并将孔视为多边形，然后应用和修改此算法以满足他们的目的。我曾经花了很多时间在网上搜索几何算法，这非常耗时，所以我正在分享我的经验，希望对您有所帮助。我期待您的积极评论，以使文章更好。玩得开心。