tracingBorders

边界追踪。。

    /**
     * Tracing contour borders of the grid data with undefined data. Grid data
     * are from left to right and from bottom to top. Grid data array: first
     * dimention is Y, second dimention is X.
     *
     * @param S0 input grid data
     * @param X x coordinate array
     * @param Y y coordinate array
     * @param S1 data flag array
     * @param undefData undefine data
     * @return borderline list
     */
    public static List tracingBorders(double[][] S0, double[] X, double[] Y, int[][] S1, double undefData) {
        List borderLines = new ArrayList<>();

        int m, n, i, j;
        m = S0.length;    //Y
        n = S0[0].length;    //X

        //S1 = new int[m][n];    //---- New array (0 with undefine data, 1 with data)
        for (i = 0; i < m; i++) {
            for (j = 0; j < n; j++) {
                if (doubleEquals(S0[i][j], undefData)) //Undefine data
                {
                    S1[i][j] = 0;
                } else {
                    S1[i][j] = 1;
                }
            }
        }

        //---- Border points are 1, undefine points are 0, inside data points are 2
        //l - Left; r - Right; b - Bottom; t - Top; lb - LeftBottom; rb - RightBottom; lt - LeftTop; rt - RightTop
        int l, r, b, t, lb, rb, lt, rt;
        for (i = 1; i < m - 1; i++) {
            for (j = 1; j < n - 1; j++) {
                if (S1[i][j] == 1) //data point
                {
                    l = S1[i][j - 1];
                    r = S1[i][j + 1];
                    b = S1[i - 1][j];
                    t = S1[i + 1][j];
                    lb = S1[i - 1][j - 1];
                    rb = S1[i - 1][j + 1];
                    lt = S1[i + 1][j - 1];
                    rt = S1[i + 1][j + 1];

                    if (l > 0 && r > 0 && b > 0 && t > 0 && lb > 0 && rb > 0 && lt > 0 && rt > 0) {
                        S1[i][j] = 2;    //Inside data point
                    }
                    if (l + r + b + t + lb + rb + lt + rt <= 2) {
                        S1[i][j] = 0;    //Data point, but not more than 3 continued data points together.
                    }                        //So they can't be traced as a border (at least 4 points together).

                }
            }
        }

        //---- Remove isolated data points (up, down, left and right points are all undefine data).
        boolean isContinue;
        while (true) {
            isContinue = false;
            for (i = 1; i < m - 1; i++) {
                for (j = 1; j < n - 1; j++) {
                    if (S1[i][j] == 1) //data point
                    {
                        l = S1[i][j - 1];
                        r = S1[i][j + 1];
                        b = S1[i - 1][j];
                        t = S1[i + 1][j];
                        lb = S1[i - 1][j - 1];
                        rb = S1[i - 1][j + 1];
                        lt = S1[i + 1][j - 1];
                        rt = S1[i + 1][j + 1];
                        if ((l == 0 && r == 0) || (b == 0 && t == 0)) //Up, down, left and right points are all undefine data
                        {
                            S1[i][j] = 0;
                            isContinue = true;
                        }
                        if ((lt == 0 && r == 0 && b == 0) || (rt == 0 && l == 0 && b == 0)
                                || (lb == 0 && r == 0 && t == 0) || (rb == 0 && l == 0 && t == 0)) {
                            S1[i][j] = 0;
                            isContinue = true;
                        }
                    }
                }
            }
            if (!isContinue) //untile no more isolated data point.
            {
                break;
            }
        }
        //Deal with grid data border points
        for (j = 0; j < n; j++) //Top and bottom border points
        {
            if (S1[0][j] == 1) {
                if (S1[1][j] == 0) //up point is undefine
                {
                    S1[0][j] = 0;
                } else if (j == 0) {
                    if (S1[0][j + 1] == 0) {
                        S1[0][j] = 0;
                    }
                } else if (j == n - 1) {
                    if (S1[0][n - 2] == 0) {
                        S1[0][j] = 0;
                    }
                } else if (S1[0][j - 1] == 0 && S1[0][j + 1] == 0) {
                    S1[0][j] = 0;
                }
            }
            if (S1[m - 1][j] == 1) {
                if (S1[m - 2][j] == 0) //down point is undefine
                {
                    S1[m - 1][j] = 0;
                } else if (j == 0) {
                    if (S1[m - 1][j + 1] == 0) {
                        S1[m - 1][j] = 0;
                    }
                } else if (j == n - 1) {
                    if (S1[m - 1][n - 2] == 0) {
                        S1[m - 1][j] = 0;
                    }
                } else if (S1[m - 1][j - 1] == 0 && S1[m - 1][j + 1] == 0) {
                    S1[m - 1][j] = 0;
                }
            }
        }
        for (i = 0; i < m; i++) //Left and right border points
        {
            if (S1[i][0] == 1) {
                if (S1[i][1] == 0) //right point is undefine
                {
                    S1[i][0] = 0;
                } else if (i == 0) {
                    if (S1[i + 1][0] == 0) {
                        S1[i][0] = 0;
                    }
                } else if (i == m - 1) {
                    if (S1[m - 2][0] == 0) {
                        S1[i][0] = 0;
                    }
                } else if (S1[i - 1][0] == 0 && S1[i + 1][0] == 0) {
                    S1[i][0] = 0;
                }
            }
            if (S1[i][n - 1] == 1) {
                if (S1[i][n - 2] == 0) //left point is undefine
                {
                    S1[i][n - 1] = 0;
                } else if (i == 0) {
                    if (S1[i + 1][n - 1] == 0) {
                        S1[i][n - 1] = 0;
                    }
                } else if (i == m - 1) {
                    if (S1[m - 2][n - 1] == 0) {
                        S1[i][n - 1] = 0;
                    }
                } else if (S1[i - 1][n - 1] == 0 && S1[i + 1][n - 1] == 0) {
                    S1[i][n - 1] = 0;
                }
            }
        }

        //---- Generate S2 array from S1, add border to S2 with undefine data.
        int[][] S2 = new int[m + 2][n + 2];
        for (i = 0; i < m + 2; i++) {
            for (j = 0; j < n + 2; j++) {
                if (i == 0 || i == m + 1) //bottom or top border
                {
                    S2[i][j] = 0;
                } else if (j == 0 || j == n + 1) //left or right border
                {
                    S2[i][j] = 0;
                } else {
                    S2[i][j] = S1[i - 1][j - 1];
                }
            }
        }

        //---- Using times number of each point during chacing process.
        int[][] UNum = new int[m + 2][n + 2];
        for (i = 0; i < m + 2; i++) {
            for (j = 0; j < n + 2; j++) {
                if (S2[i][j] == 1) {
                    l = S2[i][j - 1];
                    r = S2[i][j + 1];
                    b = S2[i - 1][j];
                    t = S2[i + 1][j];
                    lb = S2[i - 1][j - 1];
                    rb = S2[i - 1][j + 1];
                    lt = S2[i + 1][j - 1];
                    rt = S2[i + 1][j + 1];
                    //---- Cross point with two boder lines, will be used twice.
                    if (l == 1 && r == 1 && b == 1 && t == 1 && ((lb == 0 && rt == 0) || (rb == 0 && lt == 0))) {
                        UNum[i][j] = 2;
                    } else {
                        UNum[i][j] = 1;
                    }
                } else {
                    UNum[i][j] = 0;
                }
            }
        }

        //---- Tracing borderlines
        PointD aPoint;
        IJPoint aijPoint;
        BorderLine aBLine;
        List pointList;
        List ijPList;
        int sI, sJ, i1, j1, i2, j2, i3 = 0, j3 = 0;
        for (i = 1; i < m + 1; i++) {
            for (j = 1; j < n + 1; j++) {
                if (S2[i][j] == 1) //Tracing border from any border point
                {
                    pointList = new ArrayList<>();
                    ijPList = new ArrayList<>();
                    aPoint = new PointD();
                    aPoint.X = X[j - 1];
                    aPoint.Y = Y[i - 1];
                    aijPoint = new IJPoint();
                    aijPoint.I = i - 1;
                    aijPoint.J = j - 1;
                    pointList.add(aPoint);
                    ijPList.add(aijPoint);
                    sI = i;
                    sJ = j;
                    i2 = i;
                    j2 = j;
                    i1 = i2;
                    j1 = -1;    //Trace from left firstly                        

                    while (true) {
                        int[] ij3 = new int[2];
                        ij3[0] = i3;
                        ij3[1] = j3;
                        if (traceBorder(S2, i1, i2, j1, j2, ij3)) {
                            i3 = ij3[0];
                            j3 = ij3[1];
                            i1 = i2;
                            j1 = j2;
                            i2 = i3;
                            j2 = j3;
                            UNum[i3][j3] = UNum[i3][j3] - 1;
                            if (UNum[i3][j3] == 0) {
                                S2[i3][j3] = 3;    //Used border point
                            }
                        } else {
                            break;
                        }

                        aPoint = new PointD();
                        aPoint.X = X[j3 - 1];
                        aPoint.Y = Y[i3 - 1];
                        aijPoint = new IJPoint();
                        aijPoint.I = i3 - 1;
                        aijPoint.J = j3 - 1;
                        pointList.add(aPoint);
                        ijPList.add(aijPoint);
                        if (i3 == sI && j3 == sJ) {
                            break;
                        }
                    }
                    UNum[i][j] = UNum[i][j] - 1;
                    if (UNum[i][j] == 0) {
                        S2[i][j] = 3;    //Used border point
                    }                        //UNum[i][j] = UNum[i][j] - 1;
                    if (pointList.size() > 1) {
                        aBLine = new BorderLine();
                        aBLine.area = getExtentAndArea(pointList, aBLine.extent);
                        aBLine.isOutLine = true;
                        aBLine.isClockwise = true;
                        aBLine.pointList = pointList;
                        aBLine.ijPointList = ijPList;
                        borderLines.add(aBLine);
                    }
                }
            }
        }

        //---- Form borders
        List borders = new ArrayList<>();
        Border aBorder;
        BorderLine aLine, bLine;
        //---- Sort borderlines with area from small to big.
        //For inside border line analysis
        for (i = 1; i < borderLines.size(); i++) {
            aLine = borderLines.get(i);
            for (j = 0; j < i; j++) {
                bLine = borderLines.get(j);
                if (aLine.area > bLine.area) {
                    borderLines.remove(i);
                    borderLines.add(j, aLine);
                    break;
                }
            }
        }
        List lineList;
        if (borderLines.size() == 1) //Only one boder line
        {
            aLine = borderLines.get(0);
            if (!isClockwise(aLine.pointList)) {
                Collections.reverse(aLine.pointList);
                Collections.reverse(aLine.ijPointList);
            }
            aLine.isClockwise = true;
            lineList = new ArrayList<>();
            lineList.add(aLine);
            aBorder = new Border();
            aBorder.LineList = lineList;
            borders.add(aBorder);
        } else //muti border lines
        {
            for (i = 0; i < borderLines.size(); i++) {
                if (i == borderLines.size()) {
                    break;
                }

                aLine = borderLines.get(i);
                if (!isClockwise(aLine.pointList)) {
                    Collections.reverse(aLine.pointList);
                    Collections.reverse(aLine.ijPointList);
                }
                aLine.isClockwise = true;
                lineList = new ArrayList<>();
                lineList.add(aLine);
                //Try to find the boder lines are inside of aLine.
                for (j = i + 1; j < borderLines.size(); j++) {
                    if (j == borderLines.size()) {
                        break;
                    }

                    bLine = borderLines.get(j);
                    if (bLine.extent.xMin > aLine.extent.xMin && bLine.extent.xMax < aLine.extent.xMax
                            && bLine.extent.yMin > aLine.extent.yMin && bLine.extent.yMax < aLine.extent.yMax) {
                        aPoint = bLine.pointList.get(0);
                        if (pointInPolygon(aLine.pointList, aPoint)) //bLine is inside of aLine
                        {
                            bLine.isOutLine = false;
                            if (isClockwise(bLine.pointList)) {
                                Collections.reverse(bLine.pointList);
                                Collections.reverse(bLine.ijPointList);
                            }
                            bLine.isClockwise = false;
                            lineList.add(bLine);
                            borderLines.remove(j);
                            j = j - 1;
                        }
                    }
                }
                aBorder = new Border();
                aBorder.LineList = lineList;
                borders.add(aBorder);
            }
        }

        return borders;
    }

参考：https://blog.csdn.net/weixin_39633134/article/details/116031614

参考2：https://www.researchgate.net/profile/Yaqiang-Wang

参考3：https://github.com/2008nmj/wContour