Как по имеющимся координатам начала и конца двух линий узнать пересекаются ли они? Аналог Line2D.intersectsLine на Android

#java #android #геометрия

Дано:

Координаты 4 (A, B, C, D) точек на плоскости (int x, int y). 

Задача:

Узнать пересекутся ли линии, A-B и C-D.

Проблема:

Как я понял из гугла, то в java есть класс Line2D, а у него метод intersectsLine(Line2D
line) возвращающий то, что надо. Но в андроиде нема пакета java.awt.geom. Нашёл на
gitHub порт библиотеки сей, но он древний и почти без звёзд и заброшен.

Вопрос:

Так таки есть ли готовые решения сей задачи или надо вспоминать геометрию и собирать
велосипед?
    

Ответы

Ответ 1

Вот вам код из java.awt.geom.Line2D.linesIntersect, он ссылается только на один метод
java.awt.geom.Line2D.relativeCCW

public static boolean linesIntersect(double x1, double y1, double x2, double y2, 
                                     double x3, double y3, double x4, double y4) {

    boolean r1 = relativeCCW(x1, y1, x2, y2, x3, y3) * 
                 relativeCCW(x1, y1, x2, y2, x4, y4) <= 0;

    boolean r2 = relativeCCW(x3, y3, x4, y4, x1, y1) * 
                 relativeCCW(x3, y3, x4, y4, x2, y2) <= 0;
    return r1 && r2;
}


public static int relativeCCW(double x1, double y1, double x2, double y2,
                              double px, double py) {
    x2 -= x1;
    y2 -= y1;
    px -= x1;
    py -= y1;
    double ccw = px * y2 - py * x2;
    if (ccw == 0.0) {
        ccw = px * x2 + py * y2;
        if (ccw > 0.0) {
            px -= x2;
            py -= y2;
            ccw = px * x2 + py * y2;
            if (ccw < 0.0) {
                ccw = 0.0;
            }
        }
    }
    return (ccw < 0.0) ? -1 : ((ccw > 0.0) ? 1 : 0);
}


Ответ 2

Если ничего не напутал, то 

boolean intersection(double x1, double y1, ... double x4, double y4){
    Double x=null;
    double y;
    Double a,a1=null,a2=null;
    Double b,b1=null,b2=null;
    if(x1==x2){
        if(x3==x4) return false;
        x=x1;
    }else{
        a1=(y1-y2)/(x1-x2);
        b1=y1-a1*x1;
    }

    if(x3==x4){
        x=x3;
    }else{
        a2=(y3-y4)/(x3-x4);
        b2=y3-a2*x3;
    }

    if(x==null){
        x=(b2-b1)/(a1-a2);
    }
    if(x==x1){
        a=a2;
        b=b2;
    }else{
        a=a1;
        b=b1;
    }
    if(x>Math.max(x1,x2)||x>Math.max(x3,x4)||x=Math.min(y1,y2)&&y<=Math.max(y1,y2)&&y>=Math.min(y3,y4)&&y<=Math.max(y3,y4);
}