【图像处理】openCV中生成掩膜区域的参数(Point)处理：凸包算法_给定n个点 生成掩膜

背景描述

在上一篇文章使用openCV生成用户的ROI图片的需求，我们是自定义的mask的区域边界点，其实这些个边界点是有讲究了，边界点的顺序必须是顺时针或者逆时针，本文主要介绍使用凸包算法对输入边界点（MatOfPoint）进行校验处理，得到相对合理的区域。

Point的顺序规则

由之前的文章，我们知道了生成mask的point必须要保持同一个方向，即顺时针或逆时针。
参考链接

举个例子，如果将点的顺序变为如下方式，那么效果就会很奇怪。

        list.add(new Point(50, 50));
        list.add(new Point(200, 50));
        list.add(new Point(50, 200));
        list.add(new Point(200, 200));
1
2
3
4

究其原因，其底层的生成策略是按照list中点的顺序去构建一个图形，相当于就是一笔按顺序将所有点连接起来。

如果在具体的业务需求中，我们不可能让上面这种情况出现的，也就是说，我们需要将前端传入的这些点进行重新排序，使得所有点的顺序是按照顺时针（或逆时针）。

思路分析

我们需要对输入的所有坐标进行排序，排序的规则是使得这些点按照顺时针或逆时针的顺序。
看例子，如果点是按照如下的1、2、3、4、5的顺序输入，那么就会生成如下的区域

这里我们想一下，用户选择了这5个点，真正想看到的是哪个图形区域？
没错，用户心里想的是下面这张图的区域，我们需要把顺序调整为1、2、4、3，并且我们要舍弃第5个点，处理成这样，openCV才能正确的获取合理的mask区域。

其实，按照上面的策略，我们会发现生成的最终的区域永远是一个凸多边形，并且还是最大的凸多边形。
我们就是要找到n个坐标点中，任选k个点，使得这k个点围成最大的凸多边形，这也是一个经典的问题《凸包问题》

凸包问题

了解凸包之前，首先要先明确凸多边形的定义。什么是凸多边形？对于一个多边形，延长其任意一条边形成一条直线，它的其余各条边均在该条直线的同一边，那么该多边形就称为凸多边形。简单来说，凸多边形就是一个没有“凹陷”的多边形。

明确了凸多边形的定义后，就可以进一步说明凸包的定义。
凸包在计算几何中的定义为：在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。X的凸包可以用X内所有点(X1，…Xn)的凸组合来构造。
用更加通俗的话来讲，对于二维平面上的点集，最外层的点所连成的凸多边形就是该图的凸包，凸包包裹该点集的所有点。

	由于本方法的策略是按照角度从小到大排序遍历的，所以最后的结果就是沿着一个方向的，满足要求
1

代码如下：

import com.example.phenocam.entity.Point;

import java.util.ArrayList;
import java.util.List;

/**
 * @description: 凸包问题 时间复杂度：n^2
 * @author: ZW
 * @email:
 * @create: 2022-05-24 16:41
 **/

public class JarvisAlgorithm {
    public static List<Point> convexHull(List<Point> PointParams) {
        if (PointParams.size() < 3) //小于三个点的情况，直接返回
            return PointParams;
        List<Point> convexHullPointParams = new ArrayList<>();
        Point first = new Point(Double.MAX_VALUE, Double.MAX_VALUE);
        for (Point temp : PointParams){ //找到最左下角的点
            if (temp.getX() < first.getX() || (temp.getX().equals(first.getX()) && temp.getY() < first.getY())) {
                first = temp;
            }
        }
        convexHullPointParams.add(first); //加入到结果集合
        Point curPointParam = first, nextPointParam = null;
        double angle = 0, mincorner = 360, corner = 0, distance = 0;
        while (nextPointParam != first) { //没有回到起点，即没有结束
            for (Point temp : PointParams) { //遍历所有点
                //计算当前遍历的点与所处点的转角角度
                corner = calculateBearingToPointParam(angle, curPointParam.getX(),curPointParam.getY(), temp.getX(), temp.getY());
                //角度最小的情况
                if ((!convexHullPointParams.contains(temp) || (temp == first && curPointParam != first)) && corner < mincorner) {
                    mincorner = corner;
                    nextPointParam = temp;
                    distance = Math.sqrt((temp.getY() - curPointParam.getY()) * (temp.getY() - curPointParam.getY()) + (temp.getX() - curPointParam.getX()) * (temp.getX() - curPointParam.getX()));
                }
                //角度相等距离最远的情况
                if ((!convexHullPointParams.contains(temp) || (temp == first && curPointParam != first)) && corner == mincorner) {
                    if (Math.sqrt((temp.getY() - curPointParam.getY()) * (temp.getY() - curPointParam.getY()) + (temp.getX() - curPointParam.getX()) * (temp.getX() - curPointParam.getX())) > distance) {
                        nextPointParam = temp;
                        distance = Math.sqrt((temp.getY() - curPointParam.getY()) * (temp.getY() - curPointParam.getY()) + (temp.getX() - curPointParam.getX()) * (temp.getX() - curPointParam.getX()));
                    }
                }
            }
            convexHullPointParams.add(nextPointParam); //加入结果集合
            curPointParam = nextPointParam;
            angle += mincorner; //当前角度
            mincorner = 360;
        }
        return convexHullPointParams;
    }
    public static double calculateBearingToPointParam(double currentBearing, double currentX, double currentY,
                                                      double targetX, double targetY) {
        //运用三角函数计算夹角
        double angle = Math.atan2(targetY - currentY, targetX - currentX) * 180.0 / Math.PI;
        if (angle < 0)//处理小于零的情况
            angle += 360.0;
        //计算得到与y轴的夹角，并减去当前角
        double bearing = (360 - angle + 90 >= 360 ? 90 - angle : 360 - angle + 90) - currentBearing;
        //返回一个正值
        return bearing < 0 ? 360.0 + bearing : bearing;
    }

    public static void main(String[] args) {
        //找到凸包
        List<Point> points = new ArrayList<>();

        //数据1
        points.add(new Point(50.0, 50.0));
        points.add(new Point(250.0, 50.0));
        points.add(new Point(50.0, 360.0));
        points.add(new Point(230.0, 300.0));

        //数据2
//        points.add(new Point(50.0, 50.0));
//        points.add(new Point(250.0, 50.0));
//        points.add(new Point(280.0, 260.0));
//        points.add(new Point(230.0, 300.0));
//        points.add(new Point(50.0, 360.0));
//        points.add(new Point(70.0, 100.0));
//        points.add(new Point(200.0, 200.0));

        List<Point> pointParams = convexHull(points);
        for (Point Point : pointParams) {
            System.out.println(Point);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89