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

    Это можно сделать через 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
    Ответ написан
    Комментировать