PavelK
@PavelK

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

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

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

Получится то получилось, но адцки медленно.
  • Вопрос задан
  • 1384 просмотра
Решения вопроса 3
Это можно сделать через 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
Ответ написан
Комментировать
@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). И если меньшая фигура имеет сложность примерно как у большей (т.е. не логарифм) — имеем выигрыш.
Ответ написан
lxsmkv
@lxsmkv
Test automation engineer
Вам нужен алгоритм пересечения отрезков. Это же это уже было решено до нас ;)
например, Алгоритм Бентли — Оттмана
ну и еще можно про велосипеды почитать
https://habrahabr.ru/post/267461/
https://habrahabr.ru/post/267037/
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы