Цэгээс туяа татаж, хил хэдэн удаа давахыг тоолоод цэг олон өнцөгтийн дотор эсэхийг олдог арга.

IntermediateХугацаа: O(n)Санах ой: O(n)

Эхлээд жижиг бодлого

Дөрвөлжин (0, 0), (4, 0), (4, 4), (0, 4) ба Q (2, 2) цэг. Q цэгээс баруун тийш туяа татвал зөвхөн (4, 0)–(4, 4) ирмэгийг гатална.

1 удаа гатласан, сондгой тоо тул INSIDE. Q (5, 2) бол туяа нэг ч ирмэг гатлахгүй тул OUTSIDE. Q (4, 2) бол яг ирмэг дээр тул BOUNDARY.

Энгийн аргаас санаа руу

Энгийн арга: гүдгэр олон өнцөгтөд Q цэг бүх ирмэгийн зүүн талд байгаа эсэхийг cross product-аар шалгана. Гэтэл хотгор олон өнцөгтөд энэ ажиллахгүй.

Гол санаа (ray casting): Q цэгээс баруун тийш туяа татна. Туяа хилийг гатлах бүрт гадна, дотор ээлжлэн солигдоно. Төгсгөлд туяа олон өнцөгтөөс гадна гарсан байх тул сондгой удаа гатласан бол Q дотор байсан.

Нэр томьёо ба тэмдэглэгээ

туяа
Q цэгээс баруун тийш явах хэвтээ хагас шулуун.
in
Хил гатлах бүрт 0, 1 гэж солигдох тоо. Төгсгөлд 1 бол INSIDE.
(y[i] > qy) != (y[j] > qy)
Ирмэгийн хоёр үзүүр туяаны хоёр өөр талд байгаа эсэх.
c
Q цэг ирмэгийн шулууны аль талд байгааг заах cross product.
BOUNDARY
Q цэг яг ирмэг дээр: c = 0 бөгөөд ирмэгийн хүрээ дотор.
012345678910012345678910P0P1P2P3P4P5Q
in = 0огтолсон = 0

Q (2, 5) цэг олон өнцөгтийн дотор уу, гадна уу? Q цэгээс баруун тийш туяа татна. Туяа хилийг сондгой удаа давбал дотор, тэгш удаа бол гадна.

Алхам 1 / 11
Хурд
  • Q цэг
  • Туяа, одоогийн ирмэг
  • Туяа хил давсан цэг
  • Тоолохгүй
Слайд 1 / 6

Дотор уу, гадна уу?

Q цэг олон өнцөгтийн дотор байгаа эсэхийг яаж мэдэх вэ? Q цэгээс баруун тийш туяа татаад, хэдэн удаа хил давахыг тоолно.

point-in-polygon.cpp
#include <bits/stdc++.h>
using namespace std;
int n, j, in;
long long x[105], y[105], qx, qy, c;
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
cin >> qx >> qy;
for (int i = 0; i < n; i++) {
j = (i + 1) % n;
c = (x[j] - x[i]) * (qy - y[i]) - (y[j] - y[i]) * (qx - x[i]);
if (c == 0 && min(x[i], x[j]) <= qx && qx <= max(x[i], x[j]) && min(y[i], y[j]) <= qy && qy <= max(y[i], y[j])) {
cout << "BOUNDARY\n";
return 0;
}
if ((y[i] > qy) != (y[j] > qy)) {
if ((c > 0) == (y[j] > y[i])) {
in ^= 1;
}
}
}
cout << (in ? "INSIDE" : "OUTSIDE") << "\n";
}

Юунд хэрэгтэй вэ?

Q цэг олон өнцөгтийн дотор, гадна эсвэл яг хил дээр байгааг бүхэл тоогоор шийдэх. Хотгор олон өнцөгтөд ч ажиллана.

Яаж ажилладаг вэ?

1. Ирмэг бүрт эхлээд Q цэг тэр ирмэг дээр байгаа эсэхийг шалгана (cross product тэг, хүрээ дотор). Тийм бол BOUNDARY. 2. Q цэгээс баруун тийш хэвтээ туяа татна. Ирмэгийн нэг үзүүр туяанаас дээр, нөгөө нь доор эсвэл яг туяан дээр байвал ирмэг туяаны түвшинг огтолно. 3. Огтлох цэг Q цэгийн баруун талд байвал (cross product-ын тэмдгээр шалгана) туяа хил давна: in ^= 1. 4. Төгсгөлд in = 1 бол INSIDE, 0 бол OUTSIDE. Оролт: эхний мөрөнд n, дараагийн n мөрөнд оройнууд, сүүлийн мөрөнд Q цэг.

Яагаад зөв, хэр хурдан бэ?

Туяаны хамгийн алс үзүүр олон өнцөгтөөс гадна байна. Туяаг дагаад Q руу буцахад хил гатлах бүрт гадна, дотор солигдоно. Тиймээс гатлалтын тоо сондгой бол Q дотор.

Туяа оройг яг дайрвал тэр оройг хоёр удаа тоолох аюултай. y > qy гэсэн хатуу нөхцөл нь орой бүрийг туяанаас "дээр" эсвэл "доор" гэж нэг мөр шийддэг тул ийм алдаа гарахгүй. Огтлох цэг Q-гийн баруун талд байгааг c-ийн тэмдгээр бүхэл тоогоор шалгана. Хугацаа O(n).

Түгээмэл алдаа

  • Хил дээрх цэгийг тусад нь шалгахгүй байх. Тэгвэл хил дээрх Q заримдаа INSIDE, заримдаа OUTSIDE гарна.
  • Огтлох цэгийн x-ийг double-оор бодох. Бутархайн алдаанаас болж хилийн ойролцоо буруу хариулна.
  • Туяа оройг дайрахад хоёр ирмэгийг хоёуланг нь тоолох. Хатуу > нөхцөл үүнээс хамгаалдаг.
  • Хэвтээ ирмэгийг тоолох. Хоёр үзүүр нь ижил y утгатай тул нөхцөл худал болж автоматаар алгасагдана.

Хязгаарын тохиолдол

  • Q орой дээр: c = 0, хүрээ дотор тул BOUNDARY.
  • Q доод ирмэг дээр, (2, 0): BOUNDARY.
  • Хотгор олон өнцөгт (0, 0), (4, 0), (4, 3), (2, 1), (0, 3): Q (1, 1) INSIDE, Q (2, 2) хотгор хэсэгт тул OUTSIDE.
  • Q олон өнцөгтөөс зүүн талд, туяаны түвшинд орой байх, (−1, 4): OUTSIDE.

Өөрийгөө шалга

  1. Туяа хилийг 4 удаа гатлав. Q хаана байна вэ?

    Хариу харах

    Гадна. Тэгш тоо.

  2. Q (4, 2) цэг дөрвөлжин (0, 0)–(4, 4)-ийн хувьд юу хэвлэгдэх вэ?

    Хариу харах

    BOUNDARY. Баруун ирмэг дээр байна.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.Хотгор олон өнцөгт (0, 0), (4, 0), (4, 3), (2, 1), (0, 3) ба Q (2, 2). Ирмэг бүрийг туяатай шалгаад хариуг ол.

    Hint харах

    Туяа y = 2 түвшинд баруун тийш явна. Ямар ирмэгүүд энэ түвшинг дайрах вэ?

    Хариу ба тайлбар

    (4, 0)–(4, 3) ирмэгийг x = 4 цэгт, (4, 3)–(2, 1) ирмэгийг x = 3 цэгт гатална. (2, 1)–(0, 3) ба (0, 3)–(0, 0) ирмэг туяаны түвшинг x = 1 ба x = 0 цэгт огтлох боловч энэ нь Q-гийн зүүн талд. 2 удаа, тэгш тул OUTSIDE.

  2. 2.Олон Q цэгийн хариуг нэг дор хэвлэдэг болго.

    Hint харах

    Шалгалтыг функц болгоод q удаа дууд.

    Хариу ба тайлбар

    string where(qx, qy) функц бичиж, дотор нь loop-ыг шилжүүлнэ. q асуулт бол O(n · q).

  3. 3.Гүдгэр олон өнцөгтөд Q дотор эсэхийг O(log n) хугацаанд шалга.

    Hint харах

    Эхний оройгоос бусад орой руу татсан сумнууд олон өнцөгтийг гурвалжнуудад хуваана. Q аль гурвалжинд унахыг Binary Search-ээр ол.

    Хариу ба тайлбар

    p0 оройгоос cross product-аар Q аль хоёр сумны хооронд байгааг Binary Search хийж олно. Дараа нь тэр гурвалжинд Q дотор эсэхийг cross product-аар шалгана.

Жишээ

Оролт

6
1 1
9 1
9 8
6 4
4 8
1 8
2 5

Гаралт

INSIDE