Android任意多边形以任意条边画平分线切割图形算法

作者：ERIC
日期：2017.1.3

• 实现需求分析
• 实现方案解决
• 代码实现

实现需求分析

转眼就217年了，回想走过的一年，学习到了许多，成长了许多。也弄丢了曾经最珍贵的东西。但是这些都已经过去，今天我们来说说这个算法问题。

对于任意多边形的切割问题，我们可以这样来思考，多边形是有直线组成，所以我们可以看成对直线方程的求解，我们知道初中时学过的直线方程有很多的表现形式，但是一般式是瞒足所有直线的直线方程。所以在我们采用一般式来解决问题。

• 一般式Ax+By+c=0
• 斜截式 Kx+c=0

如图所示，我们只要知道ABCDE每个点在屏幕坐标系中的坐标就可以求出每天直线的直线方程，例如AB直线：设A(X1,Y1),B(X2,Y2);
A=Y2-Y1;
B=X1-X2;
C=Y1*X2-Y2*X1;

代码如下

 /** * 计算线段的直线方程 * * @param landPoint1 * @param landPoint2 * @return */
    public static LineSlope calculateSignleSlope(LandPoint landPoint1, LandPoint landPoint2) {
        double A = landPoint2.getyPoint() - landPoint1.getyPoint();
        double B = landPoint1.getxPoint() - landPoint2.getxPoint();
        double C = landPoint1.getyPoint() * landPoint2.getxPoint() - landPoint1.getxPoint() * landPoint2.getyPoint();
        System.out.println("A=" + A + "B=" + B + "C==" + C);
        return new LineSlope(A, B, C, landPoint1, landPoint2);
    }

这里我们只需写一个循环将所有直线的abc都求出来。
然后我么指定一条边作为参考边，可以将所有距离这条直线d的直线方程求解出来，然后求出平行线线与其他两条边的焦点，在求解焦点之前我们我们知道，与一条平行线距离为d的直线方程有两条，那么我们求出的焦点就会有4个，两个在多边形外，两个在多边形里面。所以我们需要知道正确的平行线方程。
求解代码如下：

/** * 获取平行线移动分割方向 * * @param xielv0 * @param xielv1 * @param xielv2 * @param distance * @return */
    public static int getDirection(LineSlope xielv0, LineSlope xielv1, LineSlope xielv2, double distance) {
        BigDecimal A = new BigDecimal(xielv1.getA()).multiply(new BigDecimal(xielv1.getA()));
        BigDecimal B = new BigDecimal(xielv1.getB()).multiply(new BigDecimal(xielv1.getB()));
        BigDecimal add = A.add(B);
        double c = new BigDecimal(xielv1.getC()).add(new BigDecimal(distance).multiply(new BigDecimal(1)).multiply(new BigDecimal(StrictMath.sqrt(add.doubleValue())))).doubleValue();
        double xPoint = (new BigDecimal(xielv2.getC()).multiply(new BigDecimal(xielv1.getB())).subtract(new BigDecimal(c).multiply(new BigDecimal(xielv2.getB()))))
                .divide((new BigDecimal(xielv1.getA()).multiply(new BigDecimal(xielv2.getB())).subtract(new BigDecimal(xielv1.getB()).multiply(new BigDecimal(xielv2.getA())))), 20, BigDecimal.ROUND_HALF_DOWN).doubleValue();
        double yPoint = (new BigDecimal(xielv1.getA()).multiply(new BigDecimal(xielv2.getC())).subtract(new BigDecimal(c).multiply(new BigDecimal(xielv2.getA()))))
                .divide((new BigDecimal(xielv1.getB()).multiply(new BigDecimal(xielv2.getA())).subtract(new BigDecimal(xielv1.getA()).multiply(new BigDecimal(xielv2.getB())))), 20, BigDecimal.ROUND_HALF_DOWN).doubleValue();
        LandPoint landPoint = new LandPoint(xPoint, yPoint);
        double a = xielv2.getPoint1().getxPoint() > xielv2.getPoint2().getxPoint() ? xielv2.getPoint1().getxPoint() : xielv2.getPoint2().getxPoint();
        double a1 = xielv2.getPoint1().getxPoint() .getPoint2().getxPoint() ? xielv2.getPoint1().getxPoint() : xielv2.getPoint2().getxPoint();
        double b = xielv2.getPoint1().getyPoint() > xielv2.getPoint2().getyPoint() ? xielv2.getPoint1().getyPoint() : xielv2.getPoint2().getyPoint();
        double b1 = xielv2.getPoint1().getyPoint() .getPoint2().getyPoint() ? xielv2.getPoint1().getyPoint() : xielv2.getPoint2().getyPoint();
        if (landPoint.getxPoint() <= a && landPoint.getxPoint() >= a1 && landPoint.getyPoint() <= b && landPoint.getyPoint() >= b1) {
            System.out.println(landPoint.getxPoint() + "__Point__" + landPoint.getyPoint());
            return 1;
        } else {
            double c1 = new BigDecimal(xielv1.getC()).add(new BigDecimal(distance).multiply(new BigDecimal(1)).multiply(new BigDecimal(StrictMath.sqrt(new BigDecimal(xielv1.getA()).multiply(new BigDecimal(xielv1.getA())).add(new BigDecimal(xielv1.getB()).multiply(new BigDecimal(xielv1.getB()))).doubleValue())))).doubleValue();
            double xPoint1 = (new BigDecimal(xielv0.getC()).multiply(new BigDecimal(xielv1.getB())).subtract(new BigDecimal(c1).multiply(new BigDecimal(xielv0.getB()))))
                    .divide((new BigDecimal(xielv1.getA()).multiply(new BigDecimal(xielv0.getB())).subtract(new BigDecimal(xielv1.getB()).multiply(new BigDecimal(xielv0.getA())))), 20, BigDecimal.ROUND_HALF_DOWN).doubleValue();
            double yPoint1 = (new BigDecimal(xielv1.getA()).multiply(new BigDecimal(xielv0.getC())).subtract(new BigDecimal(c1).multiply(new BigDecimal(xielv0.getA()))))
                    .divide((new BigDecimal(xielv1.getB()).multiply(new BigDecimal(xielv0.getA())).subtract(new BigDecimal(xielv1.getA()).multiply(new BigDecimal(xielv0.getB())))), 20, BigDecimal.ROUND_HALF_DOWN).doubleValue();
            LandPoint landPoint1 = new LandPoint(xPoint1, yPoint1);
            double a11 = xielv0.getPoint1().getxPoint() > xielv0.getPoint2().getxPoint() ? xielv0.getPoint1().getxPoint() : xielv0.getPoint2().getxPoint();
            double a12 = xielv0.getPoint1().getxPoint() .getPoint2().getxPoint() ? xielv0.getPoint1().getxPoint() : xielv0.getPoint2().getxPoint();
            double b11 = xielv0.getPoint1().getyPoint() > xielv0.getPoint2().getyPoint() ? xielv0.getPoint1().getyPoint() : xielv0.getPoint2().getyPoint();
            double b12 = xielv0.getPoint1().getyPoint() .getPoint2().getyPoint() ? xielv0.getPoint1().getyPoint() : xielv0.getPoint2().getyPoint();
            if (landPoint1.getxPoint() <= a11 && landPoint1.getxPoint() >= a12 && landPoint1.getyPoint() <= b11 && landPoint1.getyPoint() >= b12) {
                System.out.println(landPoint1.getxPoint() + "__Point__" + landPoint1.getyPoint());
                return 1;
            } else {
                return 0;
            }
        }
    }

现在我们就可以去求解每条平行线与每条边的正确焦点。知道焦点后我们就可以很容易的将两个点连接起来组成一条直线。
求解所有平行线与每条边的焦点代码

 /** * 获取所有的平行线端点 * * @param position * @param xielvs * @param distance * @return */
    public static ArrayList getAllLinePoints(int position, ArrayList xielvs, double distance) {
        ArrayList landPointArrayLists = new ArrayList<>();
        int direction;
        final double D = xielvs.get(position).getC();
        double C = xielvs.get(position).getC();
        int j = 1;
        boolean isComputeing = true;
        if (position == xielvs.size() - 1) {
            direction = getDirection(xielvs.get(position - 1), xielvs.get(position), xielvs.get(0), distance);
        } else if (position == 0) {
            direction = getDirection(xielvs.get(xielvs.size() - 1), xielvs.get(position), xielvs.get(position + 1), distance);
        } else {
            direction = getDirection(xielvs.get(position - 1), xielvs.get(position), xielvs.get(position + 1), distance);
        }
        LineSlope xielvOld = new LineSlope(xielvs.get(position).getA(), xielvs.get(position).getB(), xielvs.get(position).getC(), xielvs.get(position).getPoint1(), xielvs.get(position).getPoint2());
        xielvs.remove(position);
        while (isComputeing) {
            LandPointArrayList landPointArrayList = new LandPointArrayList();
            switch (direction) {
                case 0:
                    C = new BigDecimal(D).subtract(new BigDecimal(distance).multiply(new BigDecimal(j)).multiply(new BigDecimal(StrictMath.sqrt(new BigDecimal(xielvOld.getA()).multiply(new BigDecimal(xielvOld.getA())).add(new BigDecimal(xielvOld.getB()).multiply(new BigDecimal(xielvOld.getB()))).doubleValue())))).doubleValue();
                    break;
                case 1:
                    C = new BigDecimal(D).add(new BigDecimal(distance).multiply(new BigDecimal(j)).multiply(new BigDecimal(StrictMath.sqrt(new BigDecimal(xielvOld.getA()).multiply(new BigDecimal(xielvOld.getA())).add(new BigDecimal(xielvOld.getB()).multiply(new BigDecimal(xielvOld.getB()))).doubleValue())))).doubleValue();
                    break;
            }
            xielvOld.setC(C);
            for (int i = 0; i 
                double xPoint = (new BigDecimal(xielvs.get(i).getC()).multiply(new BigDecimal(xielvOld.getB())).subtract(new BigDecimal(xielvOld.getC()).multiply(new BigDecimal(xielvs.get(i).getB()))))
                        .divide((new BigDecimal(xielvOld.getA()).multiply(new BigDecimal(xielvs.get(i).getB())).subtract(new BigDecimal(xielvOld.getB()).multiply(new BigDecimal(xielvs.get(i).getA())))), 20, BigDecimal.ROUND_HALF_DOWN).doubleValue();
                double yPoint = (new BigDecimal(xielvOld.getA()).multiply(new BigDecimal(xielvs.get(i).getC())).subtract(new BigDecimal(xielvOld.getC()).multiply(new BigDecimal(xielvs.get(i).getA()))))
                        .divide((new BigDecimal(xielvOld.getB()).multiply(new BigDecimal(xielvs.get(i).getA())).subtract(new BigDecimal(xielvOld.getA()).multiply(new BigDecimal(xielvs.get(i).getB())))), 20, BigDecimal.ROUND_HALF_DOWN).doubleValue();
                LandPoint landPoint = new LandPoint(xPoint, yPoint);
                double a = xielvs.get(i).getPoint1().getxPoint() > xielvs.get(i).getPoint2().getxPoint() ? xielvs.get(i).getPoint1().getxPoint() : xielvs.get(i).getPoint2().getxPoint();
                double a1 = xielvs.get(i).getPoint1().getxPoint() .get(i).getPoint2().getxPoint() ? xielvs.get(i).getPoint1().getxPoint() : xielvs.get(i).getPoint2().getxPoint();
                double b = xielvs.get(i).getPoint1().getyPoint() > xielvs.get(i).getPoint2().getyPoint() ? xielvs.get(i).getPoint1().getyPoint() : xielvs.get(i).getPoint2().getyPoint();
                double b1 = xielvs.get(i).getPoint1().getyPoint() .get(i).getPoint2().getyPoint() ? xielvs.get(i).getPoint1().getyPoint() : xielvs.get(i).getPoint2().getyPoint();
                if (landPoint.getxPoint() <= a && landPoint.getxPoint() >= a1 && landPoint.getyPoint() <= b && landPoint.getyPoint() >= b1) {
                    System.out.println(landPoint.getxPoint() + "__Point__" + landPoint.getyPoint());
                    if (landPointArrayList.getLandPointStart() == null) {
                        landPointArrayList.setLandPointStart(landPoint);
                    } else {
                        landPointArrayList.setLandPointEnd(landPoint);
                    }

                }

            }
            if (landPointArrayList.getLandPointStart() == null || landPointArrayList.getLandPointEnd() == null) {
                isComputeing = false;
            } else {
                landPointArrayLists.add(landPointArrayList);
            }
            j = j + 1;
        }
        return landPointArrayLists;
    }

最后以每条平行线的中点计算箭头直线，由于需求是每相邻的两条平行线方向相反。

   /** * @param landPointArrayLists 平行线的两个端点 * @param lineLong 箭头长度 * @return 箭头点 */
    public ArrayList getArrow(ArrayList landPointArrayLists, int lineLong) {
        double number = StrictMath.sqrt(3);
        ArrayList arrowList = new ArrayList();
        boolean right = true;
        for (LandPointArrayList landPointArrayList : landPointArrayLists) {
            double centerPointLineX = (new BigDecimal(landPointArrayList.getLandPointStart().getxPoint()).add(new BigDecimal(landPointArrayList.getLandPointEnd().getxPoint()))).divide(new BigDecimal("2")).doubleValue();
            double centerPointLineY = (new BigDecimal(landPointArrayList.getLandPointStart().getyPoint()).add(new BigDecimal(landPointArrayList.getLandPointEnd().getyPoint()))).divide(new BigDecimal("2")).doubleValue();
            double A = landPointArrayList.getLandPointEnd().getyPoint() - landPointArrayList.getLandPointStart().getyPoint();
            double B = landPointArrayList.getLandPointStart().getxPoint() - landPointArrayList.getLandPointEnd().getxPoint();
            double C = landPointArrayList.getLandPointStart().getyPoint() * landPointArrayList.getLandPointEnd().getxPoint() - landPointArrayList.getLandPointStart().getxPoint() * landPointArrayList.getLandPointEnd().getyPoint();
            double v = Math.atan(-new BigDecimal(A).divide(new BigDecimal(B), 20, BigDecimal.ROUND_HALF_DOWN).doubleValue()) * 180 / Math.PI;
            double K = Math.tan((v + 30) * Math.PI / 180);
            double cnum = new BigDecimal(centerPointLineY).subtract(new BigDecimal(centerPointLineX).multiply(new BigDecimal(K))).doubleValue();
            BigDecimal add = new BigDecimal("1").add(new BigDecimal(K).multiply(new BigDecimal(K)));
            BigDecimal bigDecimal = new BigDecimal(StrictMath.sqrt(add.doubleValue()));
            double arrowX1 = new BigDecimal(centerPointLineX).subtract(new BigDecimal(lineLong).divide(bigDecimal, 20, BigDecimal.ROUND_HALF_DOWN)).doubleValue();
            double arrowX2 = new BigDecimal(centerPointLineX).add(new BigDecimal(lineLong).divide(new BigDecimal(StrictMath.sqrt(new BigDecimal("1").add(new BigDecimal(K).multiply(new BigDecimal(K))).doubleValue())), 20, BigDecimal.ROUND_HALF_DOWN)).doubleValue();
            double arrowY1 = new BigDecimal(K).multiply(new BigDecimal(arrowX1)).add(new BigDecimal(cnum)).doubleValue();
            double arrowY2 = new BigDecimal(K).multiply(new BigDecimal(arrowX2)).add(new BigDecimal(cnum)).doubleValue();

            double K2 = Math.tan((v - 30) * Math.PI / 180);
            double cnum2 = new BigDecimal(centerPointLineY).subtract(new BigDecimal(centerPointLineX).multiply(new BigDecimal(K2))).doubleValue();
            double arrowX21 = new BigDecimal(centerPointLineX).subtract(new BigDecimal(lineLong).divide(new BigDecimal(StrictMath.sqrt(new BigDecimal("1").add(new BigDecimal(K2).multiply(new BigDecimal(K2))).doubleValue())), 20, BigDecimal.ROUND_HALF_DOWN)).doubleValue();
            double arrowX22 = new BigDecimal(centerPointLineX).add(new BigDecimal(lineLong).divide(new BigDecimal(StrictMath.sqrt(new BigDecimal("1").add(new BigDecimal(K2).multiply(new BigDecimal(K2))).doubleValue())), 20, BigDecimal.ROUND_HALF_DOWN)).doubleValue();
            double arrowY21 = new BigDecimal(K2).multiply(new BigDecimal(arrowX21)).add(new BigDecimal(cnum2)).doubleValue();
            double arrowY22 = new BigDecimal(K2).multiply(new BigDecimal(arrowX22)).add(new BigDecimal(cnum2)).doubleValue();


            Log.e("aaaaa", "cnum" + cnum + "cnum2" + cnum2 + "---" + "arrowX1" + arrowX1 + "arrowY1" + arrowY1 + "---" + "arrowX2" + arrowX2 + "arrowY2" + arrowY2 + "---" + "arrowX21" + arrowX21 + "arrowY21" + arrowY21 + "---" + "arrowX22" + arrowX22 + "arrowY22" + arrowY22);
            double maxX1 = Math.max(arrowX1, arrowX2);
            double maxX2 = Math.max(arrowX21, arrowX22);
            double maxY1 = new BigDecimal(K).multiply(new BigDecimal(maxX1)).add(new BigDecimal(cnum)).doubleValue();
            double maxY2 = new BigDecimal(K2).multiply(new BigDecimal(maxX2)).add(new BigDecimal(cnum2)).doubleValue();

            double minX1 = Math.min(arrowX1, arrowX2);
            double minX2 = Math.min(arrowX21, arrowX22);
            double minY1 = new BigDecimal(K).multiply(new BigDecimal(minX1)).add(new BigDecimal(cnum)).doubleValue();
            double minY2 = new BigDecimal(K2).multiply(new BigDecimal(minX2)).add(new BigDecimal(cnum2)).doubleValue();
            LandPoint startPoint;
            LandPoint endPoint;
            LandPoint maxEndPoint;
            LandPoint maxStartPoint;
            LandPoint minStartPoint;
            LandPoint minEndPoint;

            double divide = new BigDecimal(-A).divide(new BigDecimal(B), 20, BigDecimal.ROUND_HALF_DOWN).doubleValue();

            double maxY3 = Math.max(arrowY1, arrowY2);
            double maxY4 = Math.max(arrowY21, arrowY22);

            if (arrowY1 > arrowY2) {
                maxStartPoint = new LandPoint(arrowX1, arrowY1);
                minStartPoint = new LandPoint(arrowX2, arrowY2);
            } else {
                maxStartPoint = new LandPoint(arrowX2, arrowY2);
                minStartPoint = new LandPoint(arrowX1, arrowY1);
            }

            if (arrowY21 > arrowY22) {
                maxEndPoint = new LandPoint(arrowX21, arrowY21);
                minEndPoint = new LandPoint(arrowX22, arrowY22);
            } else {
                maxEndPoint = new LandPoint(arrowX22, arrowY22);
                minEndPoint = new LandPoint(arrowX21, arrowY21);
            }

            if (divide <-number || divide > number) {
                if (right) {
                    startPoint = maxStartPoint;
                    endPoint = maxEndPoint;
                    right = false;
                } else {
                    startPoint = minStartPoint;
                    endPoint = minEndPoint;
                    right = true;
                }
            } else {
                if (right) {
                    startPoint = new LandPoint(maxX1, maxY1);
                    endPoint = new LandPoint(maxX2, maxY2);
                    right = false;
                } else {
                    startPoint = new LandPoint(minX1, minY1);
                    endPoint = new LandPoint(minX2, minY2);
                    right = true;
                }

            }
            arrowList.add(new ArrowPoint(startPoint, new LandPoint(centerPointLineX, centerPointLineY), endPoint));


        }
        return arrowList;
    }

只要求出这些点就可以轻松使用Android Paint画出来。

如需源码请联系我：447334683@qq.com