java - android中如何检测两条路径是否相交？

Question

我正在做一个小sprouts应用程序，用户可以在点之间或在屏幕上绘制路径的路径。我创建路径坐标的数组列表，然后尝试一次比较它们四个点，看看它们是否与已绘制的路径相交。目前，它没有检测到任何碰撞。这是我到目前为止的一些代码:

//ArrayList of the currentPath that is being drawn
ArrayList<float[]> currentPath = new ArrayList<>();
//ArrayList of Paths that have been drawn so far
private ArrayList <ArrayList<float[]>> paths = new ArrayList<>();

public boolean checkPath() {
        if (paths.size() == 0) {
        return true;
    } else {
        boolean noCollisions = true;
        for (int i = 0; i < paths.size(); i++) {             //Loop through path array to compare each path
            for (int j = 0; j < paths.get(i).size() - 1; j++) {  //Loop through each path to compare points
                for (int k = 0; k < currentPath.size() - 1; k++) {
                    float end1Y = currentPath.get(k + 1)[1];
                    float start1Y = currentPath.get(k)[1];
                    float start1X = currentPath.get(k)[0];
                    float end1X = currentPath.get(k + 1)[0];

                    float end2Y = paths.get(i).get(j + 1)[1];
                    float start2Y = paths.get(i).get(j)[1];
                    float start2X = paths.get(i).get(j)[0];
                    float end2X = paths.get(i).get(j + 1)[0];

                    double A1 = end1Y - start1Y;
                    double B1 = start1X - end1X;
                    double C1 = A1 * start1X + B1 + start1Y;

                    double A2 = end2Y - start2Y;
                    double B2 = start2X - end2X;
                    double C2 = A2 * start2X + B2 * start2Y;

                    double det = (A1 * B2) - (A2 * B1);
                    if (det == 0) {
                        //Lines are either parallel, are collinear or overlapping partially
                        if ((A1 * start2X) + (B1 * start2Y) == C1) {
                            //they are the on the same line, check if they are in the same space
                            if ((Math.min(start1X, end1X) < start2X) && (Math.max(start1X, end1X) > start2X)) {
                                noCollisions = false;
                            }
                            //one end point is okay, now checking the other
                            if ((Math.min(start1X, end1X) < end2X) && (Math.max(start1X, end1X) > end2X)) {
                                noCollisions = false;
                            } else{
                                noCollisions = true;
                            }
                        }
                    } else {
                        //Lines intersect somewhere, but do the segments intersect?
                        double x = (B2 * C1 - B1 * C2) / det;
                        double y = (A1 * C2 - A2 * C1) / det;

                        //check to see if the intersection is within the bounding box of the segments.
                        if((x > Math.min(start1X, end1X) && x < Math.max(start1X, end1X)) && (y > Math.min(start1Y, end1Y) && y < Math.max(start1Y, end1Y))){
                            //We are within the bounding box of the first line segment, now check the second
                            if((x > Math.min(start2X, end2X) && x < Math.max(start2X, end2X)) && (y > Math.min(start2Y, end2Y) && y < Math.max(start2Y, end2Y))){
                                //the segments intersect
                                noCollisions = false;
                            }
                        } else {
                            noCollisions = true;
                        }
                    }

                }
            }
        }
        return noCollisions;
    }
}

我正在尝试使用矩阵和行列式来确定是否存在任何交集。

Answer 1

这不是更容易吗？

Region region1, region2;
boolean intersect;

Region clip = new Region(0, 0, screenWidth, screenHeight);
region1.setPath(path1, clip);
region2.setPath(path2, clip);

if (!region1.quickReject(region2))
 intersect = true;
else intersect = false;

(我知道我迟到了)