Is there an algorithm for the fastest way to find out if one figure includes another?

Question

Algorithms

Приветствую!
Нужно наиболее быстрым способом найти включает ли полностью одна фигура другую на плоскости кроме как полным перебором.
Фигура задаётся множеством точек с координатами 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