Есть ли алгоритм для наиболее быстрого нахождения включает ли одна фигура другую?

Question

[Pavel K]

Приветствую!
Нужно наиболее быстрым способом найти включает ли полностью одна фигура другую на плоскости кроме как полным перебором.
Фигура задаётся множеством точек с координатами X, Y по часовой стрелке.
Был бы рад, если бы алгоритм был на русском.

Пока что придумал только так: по кругу обходим фигуру, берём её точку, прокладываем от неё отрезок по оси OX, и считаем пересечения этого отрезка с каждым отрезком между соседними точками другой фигуры. Если нечётно - то внутри, если чётно, то снаружи. Если хоть одна оказалась снаружи, то прекращаем, иначе считаем дальше.

Получится то получилось, но адцки медленно.

Answer 1

[Александр]

Это можно сделать через 2 проекции: на оси 0x и 0y для каждой фигуры. В итоге получаем 4 отрезка. Сравниваем координаты двух отрезков на одной прямой, если обе проекции первой фигуры "поглощают" проекции второй, то значит фигура 2 находится внутри фигуры 1.

Примерный алгоритм

struct Plane {
    int px1 = 0;
    int px2 = 0;
    int py1 = 0;
    int py2 = 0;
};

Plane getPlane(const QPolygon &shape) {
    Plane plane;
    plane.px1 = shape.at(0).x();
    plane.px2 = plane.px1;
    plane.py1 = shape.at(0).y();
    plane.py2 = plane.py1;

    foreach (const QPoint &point, shape) {
        if(point.x() < plane.px1) plane.px1 = point.x();
        if(point.x() > plane.px2) plane.px2 = point.x();
        if(point.y() < plane.py1) plane.py1 = point.y();
        if(point.y() > plane.py2) plane.py2 = point.y();
    }

    return plane;
}

void test()
{
    QPolygon shapeA;
    shapeA.append(QPoint(100,100));
    shapeA.append(QPoint(120,90));
    shapeA.append(QPoint(150,110));
    shapeA.append(QPoint(150,130));
    shapeA.append(QPoint(120,140));
    shapeA.append(QPoint(90,130));

    QPolygon shapeB;
    shapeB.append(QPoint(100,120));
    shapeB.append(QPoint(110,110));
    shapeB.append(QPoint(140,120));
    shapeB.append(QPoint(120,130));
    shapeB.append(QPoint(100,190));

    Plane planeA = getPlane(shapeA);
    Plane planeB = getPlane(shapeB);

    if(planeA.px1 < planeB.px1
            && planeA.px2 > planeB.px2
            && planeA.py1 < planeB.py1
            && planeA.py2 > planeB.py2) {
        qDebug() << "Фигура B в фигуре A!";
    }
    else if(planeA.px1 > planeB.px1
            && planeA.px2 < planeB.px2
            && planeA.py1 > planeB.py1
            && planeA.py2 < planeB.py2) {
        qDebug() << "Фигура A в фигуре В!";
    }
    else {
        /* nothing */
    };
}

Можно его дополнить условиями на обнаружение неполных вхождений. Алгоритм очень легкий, но у него есть минус: он работает только с выпуклыми фигурами. Если фигура будет в форме подковы и в середине этой подковы будет другая фигура, алгоритм решит что фигуры лежат друг в друге.

Вот реализация с подробным описанием www.gamedev.ru/code/articles/?id=4195

Answer 2

[Mercury13]

1. Надо указывать не только то, что все точки первой фигуры внутри второй, но и то, что все точки второй фигуры снаружи первой.
2. Даже примитивный алгоритм даёт скорость O(mn). Сколько у вас примерно точек?
3. Можно воспользоваться эвристиками. Если охватывающий прямоугольник 1-й фигуры целиком во 2-й — ДА. Если вылезает из охватывающего прямоугольника 2-й — НЕТ.
4. Можно поступить так. Отсортируем все точки той фигуры, которую проверяем на точки, по X-координате. Также отсортируем все отрезки той фигуры, которую проверяем на отрезки, по X-координате левой точки. Указатель отрезков ставим в начало перечня отрезков. Заводим список активных отрезков. Проходимся по всем точкам, поступая так…
• Для всех отрезков в списке активных: если точка вышла из [X1, X2) — исключить из списка!
• Смотрим на тот отрезок, что под указателем. Если X точки >= X1 — идём по фигуре дальше; если заодно X < X2 и Y выше отрезка (X1,X2 — (Y1,Y2) — включаем отрезок в список.
При определённом устройстве списка (куча по X2) имеем O(n log n). И если меньшая фигура имеет сложность примерно как у большей (т.е. не логарифм) — имеем выигрыш.

Comments

[Pavel K]

1. в том агоритме, что есть - зачем, считаются ведь пересечения и так?
2. точек на данный момент 10 тысяч, но работать алгоритм должен быстро для обработки видео.
3. не всегда, к сожалению (например первая фигура по форме буквы С а вторая по форме квадрата, которая в аккурат влезает в неё)
4. нужно проверить, ибо я пока что не смотрел конкретно на формы фигур, знаю точно, что и есть как выпуклые, так и нет, но точно не самопересекающиеся. Но хочется уйти как можно дальше от перебора.

[Mercury13]

1. Есть контрпримеры — например, вогнутая «колючка»
2. Это серьёзно, n² не катит.
3. На то она и эвристика.

[Mercury13]

Слегка подправил алгоритм.

[Pavel K]

Mercury13:
1. мда, согласен. сложность ещё добавляется =(((

[Mercury13]

Я сказал «связанный список»? Нет, куча.

Answer 3

[Alexej Simakov]

Вам нужен алгоритм пересечения отрезков. Это же это уже было решено до нас ;)
например, Алгоритм Бентли — Оттмана
ну и еще можно про велосипеды почитать
https://habrahabr.ru/post/267461/
https://habrahabr.ru/post/267037/

Comments

[Pavel K]

Как вариант, спасибо.