检查Android中的路径是否与自身相交

Question

我有问题。

如何检查Android中的路径是否与自身相交？

我有这个课：

public class GameView extends SurfaceView implements Runnable {
    Thread gameThread = null;
    SurfaceHolder surfaceHolder;
    volatile boolean playing;
    Canvas canvas;
    private final static int MAX_FPS = 60;
    private final static int FRAME_PERIOD =  1000 / MAX_FPS;
    ArrayList<Point> points = new ArrayList<>();
    private Context ctx;
    Path path;
    public static final int DEFAULT_COLOR = Color.RED;
    public static final int DEFAULT_BG_COLOR = Color.WHITE;
    private static final float TOUCH_TOLERANCE = 4;
    private float mX, mY;
    private Path mPath;
    private Paint mPaint;
    private int backgroundColor = DEFAULT_BG_COLOR;

    public GameView(Context context) {
        super(context);
        ctx = context;
        surfaceHolder = getHolder();
        surfaceHolder.setFormat(PixelFormat.RGBA_8888);
        path = new Path();

        playing = true;
        mPaint = new Paint();
        mPaint.setAntiAlias(true);
        mPaint.setDither(true);
        mPaint.setColor(DEFAULT_COLOR);
        mPaint.setStyle(Paint.Style.STROKE);
        mPaint.setStrokeJoin(Paint.Join.ROUND);
        mPaint.setStrokeCap(Paint.Cap.ROUND);
        mPaint.setXfermode(null);
        mPaint.setAlpha(0xff);
        mPaint.setStrokeWidth(12);
    }

    static Boolean isPathComplex(List<Point> path) {
        if (path == null || path.size() <= 2) {
            return false;
        }
        int len = path.size();
        for (int i = 1; i < len; i++) {
            Point lineAStart = path.get(i - 1);
            Point lineAEnd = path.get(i);
            for (int j = i + 1; j < len; j++) {
                Point lineBStart = path.get(j - 1);
                Point lineBEnd = path.get(j);
                if (lineSegmentsIntersect(lineAStart.x,lineAStart.y,
                        lineAEnd.x,lineAEnd.y,
                        lineBStart.x,lineBStart.y,
                        lineBEnd.x,lineBEnd.y)) {
                    return true;
                }
            } // inner loop
        } // outer loop
        return false;
    }

    static Boolean lineSegmentsIntersect(float p0_x, float p0_y, float p1_x, float p1_y,
                                         float p2_x, float p2_y, float p3_x, float p3_y) {
        float s1_x, s1_y, s2_x, s2_y;
        s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
        s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;
        float s, t;
        s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
        t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);
        if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
        {
            // Collision detected
            return true;
        }
        return false; // No collision
    }

    public void update(){
        isPathComplex(points);
    }

    public void draw(){
        if(surfaceHolder.getSurface().isValid()){
            canvas = surfaceHolder.lockCanvas();
            if(canvas != null) {
                canvas.drawColor(backgroundColor);
                if (mPath != null) {
                    canvas.drawPath(mPath, mPaint);
                }
                surfaceHolder.unlockCanvasAndPost(canvas);
            }
        }
    }

    @Override
    public void run() {
        while(playing){
            long started = System.currentTimeMillis();
            float deltaTime = (System.currentTimeMillis() - started);
            int sleepTime = (int) (FRAME_PERIOD - deltaTime);
            update();
            draw();
            if (sleepTime > 0) {
                try {
                    Thread.sleep(sleepTime);
                }
                catch (InterruptedException e) {
                }
            }
            while (sleepTime < 0) {
                update();
                draw();
                sleepTime += FRAME_PERIOD;
            }
        }
    }  

   private void touchStart(float x, float y) {
        mPath = new Path();
        points.add(new Point((int)x,(int)y));
        mPath.reset();
        mPath.moveTo(x, y);
        mX = x;
        mY = y;
    }

    private void touchMove(float x, float y) {
        float dx = Math.abs(x - mX);
        float dy = Math.abs(y - mY);
        points.add(new Point((int)x,(int)y));
        if (dx >= TOUCH_TOLERANCE || dy >= TOUCH_TOLERANCE) {
            mPath.quadTo(mX, mY, (x + mX) / 2, (y + mY) / 2);
            mX = x;
            mY = y;
        }
    }

    private void touchUp() {
        mPath.lineTo(mX, mY);
    }

    @Override
    public boolean onTouchEvent(MotionEvent event) {
        float x = event.getX();
        float y = event.getY();
        switch(event.getAction()) {
            case MotionEvent.ACTION_DOWN :
                touchStart(x, y);
                break;
            case MotionEvent.ACTION_MOVE :
                touchMove(x, y);
                break;
            case MotionEvent.ACTION_UP :
                touchUp();
                break;
        }
        return true;
    }

    public void pause() {
        playing = false;
        try {
            gameThread.join();
        } catch (InterruptedException e) {
            Log.e("Error:", "joining thread");
        }
    }

    public void resume(Context context) {
        playing = true;
        gameThread = new Thread(this);
        gameThread.start();
    }
}

请您知道这个问题的解决方案吗？

我尝试了很多，但没有任何帮助我解决问题。

我要实现的是检测到这样的相交

我尝试了使用check android.graphics.path交点的点的解决方案，但似乎对我不起作用。

我也可能做错了什么，因为我是Android开发和编程的新手:)。

预先感谢您！

编辑：

要检测Intersect我遵循上述解决方案并修改了此功能https://stackoverflow.com/a/1968345/9339525，但即使路径没有越过自身，它也几乎返回了所有时间。

所有用于检测交叉点的代码：

static Boolean isPathComplex(List<Point> path) {
    if (path == null || path.size() <= 2) {
        return false;
    }
    int len = path.size();
    for (int i = 1; i < len; i++) {
        Point lineAStart = path.get(i - 1);
        Point lineAEnd = path.get(i);
        for (int j = i + 1; j < len; j++) {
            Point lineBStart = path.get(j - 1);
            Point lineBEnd = path.get(j);
            if (lineSegmentsIntersect(lineAStart.x,lineAStart.y,
                    lineAEnd.x,lineAEnd.y,
                    lineBStart.x,lineBStart.y,
                    lineBEnd.x,lineBEnd.y)) {
                return true;
            }
        } // inner loop
    } // outer loop
    return false;
}

static Boolean lineSegmentsIntersect(float p0_x, float p0_y, float p1_x, float p1_y,
                                     float p2_x, float p2_y, float p3_x, float p3_y) {
    float s1_x, s1_y, s2_x, s2_y;
    s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
    s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;
    float s, t;
    s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);
    if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
        // Collision detected
        return true;
    }
    return false; // No collision
}

编辑：

我修改了我的类游戏视图，并添加了检测交叉点的方法。

Answer 1

我无法忍受这么困难，所以我打开了计算机并编码了一些东西。

我只尝试了几个值，不知道如果段的开始点重合会发生什么。

请尝试。

static boolean lineSegmentsDoIntersect(
          float Ax, float Ay
        , float Bx, float By
        , float Cx, float Cy
        , float Dx, float Dy) {
    // two line segments: AB and CD
    // segment AB intersects segment CD
    // if  A and B on different sides of line through C and D
    // AND C and D on different sides of line through A and B
    // note the difference between line and  segment!
    if ( ! pointsOnDifferentSidesOfLineThrough(Ax, Ay, Bx, By, Cx, Cy, Dx, Dy) )
        return false;
    if ( ! pointsOnDifferentSidesOfLineThrough(Cx, Cy, Dx, Dy, Ax, Ay, Bx, By) )
        return false;
    return true;
}
static boolean pointsOnDifferentSidesOfLineThrough(
          float Ax, float Ay
        , float Bx, float By
        , float x1, float y1
        , float x2, float y2) {
    // determine equation of line through C and D
    // y = ax + b
    // a = (y2-y1)/(x2-x1)   but.. ( x2-x1) not equal to zero
    // y-y1 = a (x-x1)
    // y = a (x-x1) + y1
    // y = ax -ax1 + y1
    // b = -ax1 + y1
    //but.. (x2-x1) not 0
    if ( x2==x1)
    {
        if ( Ax > x1 && Bx > x1 )
            return false;
        if ( Ax < x1 && Bx < x1 )
            return false;
        return true;
    }
    float a = (y2-y1)/(x2-x1);
    float b = -a * x1 + y1;
    float yA = a * Ax + b;
    float yB = a * Bx + b;
    if ( yA > Ay && yB > By )
        return false;
    if ( yA < Ay && yB < By )
        return false;
    return true;
}