Гүдгэр олон өнцөгтийн Минковскийн нийлбэр¶

Тодорхойлолт¶

Хавтгай дээрх цэгүүдийн $A$ ба $B$ гэсэн хоёр олонлогийг авч үзье. Минковскийн нийлбэр $A + B$-г $\{a + b| a \in A, b \in B\}$ гэж тодорхойлно. Энд бид $A$ ба $B$ нь дотоод хэсгүүдийнхээ хамт $P$ ба $Q$ гүдгэр олон өнцөгтөөс бүрдэх тохиолдлыг авч үзнэ. Энэ өгүүлэлд бид олон өнцөгтүүдийг оройнуудынх нь эрэмбэлэгдсэн дараалалтай адилтгах ба ингэснээр $|P|$ эсвэл $P_i$ мэтийн тэмдэглэгээ утга учиртай болно. $P$ ба $Q$ гүдгэр олон өнцөгтийн нийлбэр нь хамгийн ихдээ $|P| + |Q|$ оройтой гүдгэр олон өнцөгт байдаг нь тогтоогддог.

Алгоритм¶

Энд бид олон өнцөгтүүдийг циклээр дугаарласан гэж үзнэ, өөрөөр хэлбэл $P_{|P|} = P_0,\ Q_{|Q|} = Q_0$ гэх мэт.

Нийлбэрийн хэмжээ анхны олон өнцөгтүүдийн хэмжээгээр шугаман байдаг тул бид шугаман хугацааны алгоритм олохыг зорих ёстой. Хоёр олон өнцөгт хоёулаа цагийн зүүний эсрэг эрэмбэлэгдсэн гэж үзье. Туйлын өнцгөөр эрэмбэлэгдсэн $\{\overrightarrow{P_iP_{i+1}}\}$ ба $\{\overrightarrow{Q_jQ_{j+1}}\}$ ирмэгүүдийн дарааллуудыг авч үзье. Бид $P + Q$-ийн ирмэгүүдийн дарааллыг эдгээр хоёр дарааллыг туйлын өнцгийн эрэмбийг хадгалан нийлүүлж, дараалсан ижил чиглэлтэй векторуудыг тэдгээрийн нийлбэрээр солих замаар авч болно гэж баталж байна. Энэ санааг шууд ашиглах нь шугаман хугацааны алгоритмд хүргэдэг боловч талуудын дарааллаас $P + Q$-ийн оройнуудыг сэргээхэд векторуудыг дахин дахин нэмэх шаардлагатай бөгөөд хэрэв бид хөвөгч цэгтэй координаттай ажиллаж байвал энэ нь хүсээгүй нарийвчлалын асуудал үүсгэж болзошгүй тул бид энэ санааны бага зэргийн өөрчлөлтийг тайлбарлана.

Эхлээд бид олон өнцөгт бүрийн эхний орой хамгийн бага y координаттай байхаар оройнуудыг дахин эрэмбэлэх ёстой (ийм хэд хэдэн орой байвал хамгийн бага x координаттайг нь сонго). Үүний дараа хоёр олон өнцөгтийн талууд туйлын өнцгөөр эрэмбэлэгдсэн болох тул тэдгээрийг гараар эрэмбэлэх шаардлагагүй. Одоо бид $i$ ($P$-ийн орой руу заасан) ба $j$ ($Q$-ийн орой руу заасан) гэсэн хоёр заагч үүсгэх ба хоёул эхэндээ 0 гэж тохируулагдана. $i < |P|$ эсвэл $j < |Q|$ байх хугацаанд бид дараах алхмуудыг давтана.

$P + Q$-д $P_i + Q_j$-г залга.
$\overrightarrow{P_iP_{i + 1}}$ ба $\overrightarrow{Q_jQ_{j+1}}$-ийн туйлын өнцгүүдийг харьцуул.
Хамгийн бага өнцөгт харгалзах заагчийг нэгээр нэмэгдүүл (хэрэв өнцгүүд тэнцүү бол хоёуланг нь нэмэгдүүл).

Дүрслэл¶

Энд юу болж байгааг ойлгоход тань туслах сайхан дүрслэл байна.

Хоёр олон өнцөгтийн хоорондох зай¶

Минковскийн нийлбэрийн хамгийн түгээмэл хэрэглээний нэг бол хоёр гүдгэр олон өнцөгтийн хоорондох зайг тооцоолох (эсвэл зүгээр л тэдгээр огтлолцож байгаа эсэхийг шалгах) явдал юм. $P$ ба $Q$ хоёр гүдгэр олон өнцөгтийн хоорондох зайг $\min\limits_{a \in P, b \in Q} ||a - b||$ гэж тодорхойлно. Зай нь үргэлж хоёр оройн хооронд, эсвэл орой ба ирмэгийн хооронд хүрдэг болохыг анзаарч болох тул бид зайг $O(|P||Q|)$-д хялбархан олж болно. Гэвч Минковскийн нийлбэрийг ухаалгаар ашигласнаар бид complexity-г $O(|P| + |Q|)$ болгон бууруулж чадна.

Хэрэв бид $Q$-г $(0, 0)$ цэгээр тусгаж $-Q$ олон өнцөгтийг авбал бодлого нь $P + (-Q)$ доторх цэг ба $(0, 0)$-ийн хоорондох хамгийн бага зайг олох болтол буурна. Бид тэр зайг дараах санааг ашиглан шугаман хугацаанд олж чадна. Хэрэв $(0, 0)$ олон өнцөгтийн дотор эсвэл зааг дээр байвал зай нь $0$, эс бөгөөс зай нь $(0, 0)$ ба олон өнцөгтийн ямар нэг орой эсвэл ирмэгийн хооронд хүрнэ. Минковскийн нийлбэрийг шугаман хугацаанд тооцоолж болдог тул бид хоёр гүдгэр олон өнцөгтийн хоорондох зайг олох шугаман хугацааны алгоритмыг авна.

Implementation¶

Below is the implementation of Minkowski sum for polygons with integer points. Note that in this case all computations can be done in integers since instead of computing polar angles and directly comparing them we can look at the sign of cross product of two vectors.

struct pt{
    long long x, y;
    pt operator + (const pt & p) const {
        return pt{x + p.x, y + p.y};
    }
    pt operator - (const pt & p) const {
        return pt{x - p.x, y - p.y};
    }
    long long cross(const pt & p) const {
        return x * p.y - y * p.x;
    }
};

void reorder_polygon(vector<pt> & P){
    size_t pos = 0;
    for(size_t i = 1; i < P.size(); i++){
        if(P[i].y < P[pos].y || (P[i].y == P[pos].y && P[i].x < P[pos].x))
            pos = i;
    }
    rotate(P.begin(), P.begin() + pos, P.end());
}

vector<pt> minkowski(vector<pt> P, vector<pt> Q){
    // the first vertex must be the lowest
    reorder_polygon(P);
    reorder_polygon(Q);
    // we must ensure cyclic indexing
    P.push_back(P[0]);
    P.push_back(P[1]);
    Q.push_back(Q[0]);
    Q.push_back(Q[1]);
    // main part
    vector<pt> result;
    size_t i = 0, j = 0;
    while(i < P.size() - 2 || j < Q.size() - 2){
        result.push_back(P[i] + Q[j]);
        auto cross = (P[i + 1] - P[i]).cross(Q[j + 1] - Q[j]);
        if(cross >= 0 && i < P.size() - 2)
            ++i;
        if(cross <= 0 && j < Q.size() - 2)
            ++j;
    }
    return result;
}