如何判断一个多边形是否合法

2019-11-29 13:06:27

参考地址 如何判断一个多边形是否合法  

背景及问题分析

利用无人机对一片区域进行测绘前,我们会先在地图上框选一个区域,然后再规划飞行的路线,而需要测绘的这片区域往往是一个多边形。在 MeshKit 中,我们加入了多边形区域的编辑功能,其中就涉及判断用户所编辑出来的多边形是否合法的问题。

首先我们要确定一个标准:怎么样才算一个不合法的多边形 ?我们可以简单地通过下面这幅图来解释一下:


我们可以看出前面两个分别是凹多边形和凸多边形,而最后一张则是我们所说的不合法多边形,可以看出这个不合法的多边形的特征就是:它存在某条边与另外一条边相交的情况

那么要判断一个多边形是否合法,我们只要判断组成多边形的所有线段是否存在相交的情况即可,当然,我们这里所说的相交是 规范相交 ,即 交点不在线段的端点上

好了,那么现在的问题可以简化成:如何判断两条线段是否规范相交

算法解析

这里我们需要借助 向量的叉积 来进行判断。

叉积,又称向量积,是对三维空间中的两个向量的二元运算。

这里推荐 3Blue1Brown 的 视频 来快速回顾一下叉积的概念(下面的两幅截图来自此视频)。我们只需知道叉积的结果是有正负的,比如我们以向量  \vec{v} 为标准,如下图,向量  \vec{w}  在  \vec{v}顺时针方向,那么 \vec{v} \times \vec{w} < 0

如果向量 \vec{w}  在  \vec{v}逆时针方向,那么 \vec{v} \times \vec{w} > 0

那么我们如何利用叉积的特性运用到判断线段是否相交上呢?

我们先看下面最直接的一个线段相交的情况:


线段 P_1P_2 和 线段 Q_1Q_2 明显存在一个交点,从上面这张图我们可以做一个简单的结论:如果一条的线段的两个端点在另外一条线段两侧,那么这两条线段可能相交,注意这里说的是可能相交,稍后会讲到另外一种情况。

我们可以将上面的图转换为向量的情况来看:


是不是觉得似曾相识,这跟上面提到的叉积的情况是不是很类似?
向量  \vec{P_1Q_1}\vec{P_1P_2}
向量  \vec{P_1Q_2}\vec{P_1P_2} 的顺时针方向,那么:\vec{P_1P_2} \times \vec{P_1Q_2} < 0

用 A 表示 \vec{P_1P_2} \times \vec{P_1Q_1} 的叉积结果,用 B 表示 \vec{P_1P_2} \times \vec{P_1Q_2} 的叉积结果,那么 一条的线段的两个端点在另外一条线段两侧 这个几何现象可以用这个公式表示 :A{\times}B<0

我们前面提到 如果一条的线段的两个端点在另外一条线段两侧,那么这两条线段可能相交 ,为什么是可能相交呢?如果我们将 线段 Q_1Q_2 往右边移动一下,会存在下面这种情况:


从上图可以看出,线段  的两个端点在线段  两侧,但是它们并没有相交。


那么如何排除这种情况呢?其实很简单,我们之前都是以线段 P_1P_2 作为主视角,如果将主视角换成线段 Q_1Q_2,那么我们很容易看出 线段 P_1P_2 的两个端点并没有在 线段 Q_1Q_2 的两侧。所以我们再次看回上面相交的那幅图,为了能够充分的判断两条线段相交,这次以 Q_1Q_2 为主视角看待这个问题,求叉积:


向量   在  的逆时针方向,那么:
向量   在  的顺时针方向,那么:


综上,我们可以得出:
A = \vec{P_1P_2} \times \vec{P_1Q_1}
B = \vec{P_1P_2} \times \vec{P_1Q_2}
C = \vec{Q_1Q_2} \times \vec{Q_1P_1}
D = \vec{Q_1Q_2} \times \vec{Q_1P_2}
A{\times} B < 0 && C \times D < 0 的时候,两条线段规范相交。
至于向量的叉积如何运算,这里就不细写了,给出一张计算草稿给大家过目一下:


示例代码

根据计算草稿的内容,我们就很容易通过代码来实现了:

private func isIntersect(line1: (CGPoint, CGPoint), line2: (CGPoint, CGPoint)) -> Bool {
    let p1 = line1.0
    let p2 = line1.1
    let q1 = line2.0
    let q2 = line2.1

    let a1 = (p2.x - p1.x) * (q1.y - p1.y) - (q1.x - p1.x) * (p2.y - p1.y)
    let a2 = (p2.x - p1.x) * (q2.y - p1.y) - (q2.x - p1.x) * (p2.y - p1.y)
    
    let b1 = (q2.x - q1.x) * (p1.y - q1.y) - (p1.x - q1.x) * (q2.y - q1.y)
    let b2 = (q2.x - q1.x) * (p2.y - q1.y) - (p2.x - q1.x) * (q2.y - q1.y)
    
    if a1 * a2 < 0 && b1 * b2 < 0 {
        return true
    }
    return false}




  • 2020-11-21 20:41:51

    Kotlin Sealed class类详解

    Sealed class(密封类) 是一个有特定数量子类的类,看上去和枚举有点类似,所不同的是,在枚举中,我们每个类型只有一个对象(实例);而在密封类中,同一个类可以拥有几个对象。

  • 2020-11-22 20:53:43

    Dagger2之Kotlin写法

    修饰构造方法 修饰变量,在宿主类里,引入要注入的实例

  • 2020-11-22 20:56:13

    Dagger2使用详解

    简单的说,就是一个工厂模式,由Dagger负责创建工厂,帮忙生产instance。遵从Java规范JSR 330,可以使用这些注解。现在不研究Dagger2是如何根据注解去生成工厂的,先来看看工厂是什么东西,理解为什么可以实现了DI(Dependency Injection),如何创建IoC(Inverse of Control)容器。

  • 2020-11-22 21:00:28

    dagger.android--Fragment,BaseFragment

    1 使用Fragment参数来代替Activity参数 2 使用 @FragmentKey来代替@ActivityKey 3 使用HasFragmentInjector来代替@HasActivityInjector 4 AndroidInjection.inject(Fragment)方法,在Fragment的onAttach()中调用,而不是在onCreate()中 5 Fragment的Module添加位置,和Activity是不同的,它取决于Fragment需要的其他依赖注入

  • 2020-11-22 21:12:30

    Dependency Injection with Dagger2,Fragment

    標註@Provides的method若有parameter的話,Dagger會找出其擁有的該型態物件來使用。我們在Module內新增了DataModel將其列入Dagger的管理下,接著在provideFactory()增加parameter變成provideFactory(DataModel dataModel),Dagger就會找出其管理的DataModel給provideFactory使用。

  • 2020-11-22 22:58:52

    Android LiveData Transformations

    有时候有这样的需求,需要在LiveData将变化的数据通知给观察者前,改变数据的类型;或者是返回一个不一样的LiveData。

  • 2020-11-22 23:00:16

    androidx中的lifecycle组件

    Lifecycle-aware components生命周期感知组件执行操作,以响应另一个组件生命周期状态的更改,例如Activity和Fragment。这些组件可以帮助您生成更有组织、更容易维护的轻量级代码。

  • 2020-11-22 23:02:50

    Android数据存储之DataBase的Room

    Room是Google在AndroidX中提供的一个ORM(Object Relational Mapping,对象关系映射)库。它是在SQLite上提供的一个抽象层,可以使用SQLite的全部功能,同时可以更好更便捷流畅地访问数据库。(关于AndroidX可以参考