Задать вопрос

Александр

Ответы пользователя по тегу Геометрия

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

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

  • Как узнать координаты точек (вершин)?

    @wxmaper Автор вопроса
    Включил мозг и разобрался =) грубо говоря, найти эти точки можно так:
    // псевдокод
frontPoint.x = cos ( body->rotation * PI / 180 ) * body->centerX() + body->width() / 2;
frontPoint.y = sin ( body->rotation * PI / 180 ) * body->centerY() + body->height() / 2;
rearPoint.x = cos ( body->rotation * PI / 180 ) * body->centerX() - body->width() / 2;
rearPoint.y = sin ( body->rotation * PI / 180 ) * body->centerY() - body->height() / 2;


    Если учесть все "опасные" углы, то получится так:
    // реализация на Qt
qint16 angle = qRound(body->rotation());
qint16 newFrontY, newRearY, newFrontX, newRearX;

if(angle == 0 || qAbs(angle) == 180) {
    newFrontY = qFloor((newY - body->height()/2.1) / mCellSize);
    newRearY =  qFloor((newY + body->height()/2.1) / mCellSize);
}
else {
    newFrontY = qAbs(qSin(angle * PI_DIFF_180) * newY - body->height()/2.1) / mCellSize;
    newRearY = qAbs(qSin(angle * PI_DIFF_180) * newY + body->height()/2.1) / mCellSize;
}

if(qAbs(angle) == 90 || qAbs(angle) == 270) {
    newFrontX = qFloor((newX - body->width()/2.1) / mCellSize);
    newRearX = qFloor((newX + body->width()/2.1) / mCellSize);
}
else {
    newFrontX = qAbs(qCos(angle * PI_DIFF_180) * newX - body->width()/2.1) / mCellSize;
    newRearX = qAbs(qCos(angle * PI_DIFF_180) * newX + body->width()/2.1) / mCellSize;
}
    Ответ написан
    1 комментарий
    1 комментарий