Проверьте пересечение android.graphics.path с самим собой

Question

Я хотел бы проверить, если (и если да, где коллизия (x, y) - только для выделения), путь действительно пересекается.Также было бы очень интересно, как я проверяю, пересекается ли путь с другим путем.Вот скриншот, чтобы лучше объяснить, что я имею в виду:

http://i.stack.imgur.com/JrEmN.png

Answer 1

Самый простой способ - проверить, пересекается ли какой-либо отрезок с каким-либо другим отрезком.Сегмент линии состоит из пар соседних точек на пути.Путь с 10 точками имеет 9 отрезков.

Вот пример того, как можно это сделать.

import android.graphics.Point;
import java.util.List;

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, lineAEnd, lineBStart, lineBEnd)) {
                return true;
            }

        } // inner loop

   } // outer loop

}

static Boolean lineSegmentsIntersect(Point aInitial, Point aFinal, Point bInitial, Point bFinal) {
    // left as an exercise to the reader
}

См. Как определить, где пересекаются два отрезка?функция lineSegmentsIntersect.