Цэгийн байршлыг $O(log n)$-д олох¶
Дараах бодлогыг авч үзье: танд нэг ба тэг зэрэгтэй орой огт байхгүй хавтгай хуваалт ба олон асуулга өгөгдсөн.
Асуулга бүр нь цэг бөгөөд түүний хувьд бид хуваалтын аль нүүрэнд харьяалагдахыг тодорхойлох ёстой.
Бид асуулга бүрд $O(\log n)$-д офлайнаар хариулна.
Энэ бодлого танд Воронойн диаграм эсвэл ямар нэг энгийн олон өнцөгт дэх зарим цэгийн байршлыг олох шаардлагатай үед гарч ирж болно.
Алгоритм¶
Эхлээд асуулгын $p\ (x_0, y_0)$ цэг бүрийн хувьд бид дараах ирмэгийг олохыг хүсэж байна: хэрэв цэг ямар нэг ирмэгт харьяалагдаж байвал цэг бидний олсон ирмэг дээр орших, эс бөгөөс энэ ирмэг $x = x_0$ шулууныг $y < y_0$ байх ямар нэг цор ганц $(x_0, y)$ цэгт огтлох ба энэ $y$ нь ийм бүх ирмэгийн дундаас хамгийн их байна. Дараах зураг хоёр тохиолдлыг хоёуланг нь харуулж байна.
Бид энэ бодлогыг шүүрдэх шулууны алгоритм ашиглан офлайнаар бодно. Асуулгын цэгүүд ба ирмэгүүдийн үзүүрийн цэгүүдийн x координатыг өсөх дарааллаар тойрч, ирмэгүүдийн $s$ олонлогийг хөтөлье. x координат бүрийн хувьд бид зарим үйл явдлыг урьдчилан нэмнэ.
Үйл явдлууд дөрвөн төрөлтэй байна: add, remove, vertical, get. Босоо ирмэг бүрийн хувьд (хоёр үзүүрийн цэг ижил x координаттай) бид харгалзах x координатын хувьд нэг vertical үйл явдал нэмнэ. Бусад ирмэг бүрийн хувьд бид үзүүрийн цэгүүдийн x координатуудын хамгийн багад нь нэг add үйл явдал, x координатуудын хамгийн ихэд нь нэг remove үйл явдал нэмнэ. Эцэст нь асуулгын цэг бүрийн хувьд бид түүний x координатын хувьд нэг get үйл явдал нэмнэ.
x координат бүрийн хувьд бид үйл явдлуудыг төрлөөр нь (vertical, get, remove, add) дарааллаар эрэмбэлнэ. Дараах зураг x координат бүрийн хувьд бүх үйл явдлыг эрэмбэлэгдсэн дарааллаар харуулж байна.
Шүүрдэх шулууны явцад бид хоёр олонлог хөтөлнө. Босоо биш бүх ирмэгийн хувьд $t$ олонлог, мөн тусгайлан босоо ирмэгүүдийн хувьд $vert$ олонлог. Бид x координат бүрийг боловсруулж эхлэхэд $vert$ олонлогийг цэвэрлэнэ.
Одоо тогтмол x координатын хувьд үйл явдлуудыг боловсруулъя.
- Хэрэв бид vertical үйл явдал авбал бид зүгээр л харгалзах ирмэгийн үзүүрийн цэгүүдийн хамгийн бага y координатыг $vert$-д оруулна.
- Хэрэв бид remove эсвэл add үйл явдал авбал бид харгалзах ирмэгийг $t$-ээс хасах эсвэл $t$-д нэмнэ.
- Эцэст нь get үйл явдал бүрийн хувьд бид $vert$-д хоёртын хайлт хийж, цэг ямар нэг босоо ирмэг дээр орших эсэхийг шалгах ёстой. Хэрэв цэг ямар ч босоо ирмэг дээр оршихгүй бол бид энэ асуулгын хариултыг $t$-ээс олох ёстой. Үүний тулд бид дахин хоёртын хайлт хийнэ. Зарим degenerate case-ийг (жишээ нь $(0,~0)$ цэгээр асуулга хийхэд $(0,~0)$, $(0,~2)$, $(1, 1)$ гурвалжны тохиолдол) боловсруулахын тулд бид энэ x координатын бүх үйл явдлыг боловсруулсны дараа бүх get үйл явдалд дахин хариулж, хоёр хариултын хамгийн сайныг сонгох ёстой.
Одоо $t$ олонлогийн харьцуулагчийг сонгоё.
Энэ харьцуулагч нэг ирмэг тэдгээрийн хамрах x координат бүрийн хувьд нөгөөгөөсөө дээш оршихгүй эсэхийг шалгах ёстой. Бидэнд $(a, b)$ ба $(c, d)$ гэсэн хоёр ирмэг байна гэж үзье. Тэгвэл харьцуулагч нь (псевдокод хэлбэрээр):
$val = sgn((b - a)\times(c - a)) + sgn((b - a)\times(d - a))$
if $val \neq 0$
then return $val > 0$
$val = sgn((d - c)\times(a - c)) + sgn((d - c)\times(b - c))$
return $val < 0$
Одоо асуулга бүрийн хувьд бидэнд харгалзах ирмэг байна. Нүүрийг хэрхэн олох вэ? Хэрэв бид ирмэгийг олж чадаагүй бол цэг гадна нүүрэнд байна гэсэн үг. Хэрэв цэг бидний олсон ирмэгт харьяалагдаж байвал нүүр давтагдашгүй биш. Эс бөгөөс хоёр нэр дэвшигч байна — энэ ирмэгээр хүрээлэгдсэн нүүрнүүд. Аль нь хариулт болохыг хэрхэн шалгах вэ? Ирмэг босоо биш гэдгийг анхаарна уу. Тэгвэл хариулт нь энэ ирмэгээс дээш байгаа нүүр юм. Босоо биш ирмэг бүрийн хувьд ийм нүүрийг олъё. Нүүр бүрийн цагийн зүүний эсрэг тойролтыг авч үзье. Хэрэв энэ тойролтын явцад бид ирмэгээр дамжин өнгөрөхдөө x координатыг ихэсгэсэн бол энэ нүүр нь бидний энэ ирмэгийн хувьд олох шаардлагатай нүүр юм.
Тэмдэглэл¶
Үнэндээ persistent модуудтай бол энэ аргыг асуулгад онлайнаар хариулахад ашиглаж болно.
Implementation¶
The following code is implemented for integers, but it can be easily modified to work with doubles (by changing the compare methods and the point type).
This implementation assumes that the subdivision is correctly stored inside a DCEL and the outer face is numbered $-1$.
For each query a pair $(1, i)$ is returned if the point lies strictly inside the face number $i$, and a pair $(0, i)$ is returned if the point lies on the edge number $i$.
typedef long long ll;
bool ge(const ll& a, const ll& b) { return a >= b; }
bool le(const ll& a, const ll& b) { return a <= b; }
bool eq(const ll& a, const ll& b) { return a == b; }
bool gt(const ll& a, const ll& b) { return a > b; }
bool lt(const ll& a, const ll& b) { return a < b; }
int sgn(const ll& x) { return le(x, 0) ? eq(x, 0) ? 0 : -1 : 1; }
struct pt {
ll x, y;
pt() {}
pt(ll _x, ll _y) : x(_x), y(_y) {}
pt operator-(const pt& a) const { return pt(x - a.x, y - a.y); }
ll dot(const pt& a) const { return x * a.x + y * a.y; }
ll dot(const pt& a, const pt& b) const { return (a - *this).dot(b - *this); }
ll cross(const pt& a) const { return x * a.y - y * a.x; }
ll cross(const pt& a, const pt& b) const { return (a - *this).cross(b - *this); }
bool operator==(const pt& a) const { return a.x == x && a.y == y; }
};
struct Edge {
pt l, r;
};
bool edge_cmp(Edge* edge1, Edge* edge2)
{
const pt a = edge1->l, b = edge1->r;
const pt c = edge2->l, d = edge2->r;
int val = sgn(a.cross(b, c)) + sgn(a.cross(b, d));
if (val != 0)
return val > 0;
val = sgn(c.cross(d, a)) + sgn(c.cross(d, b));
return val < 0;
}
enum EventType { DEL = 2, ADD = 3, GET = 1, VERT = 0 };
struct Event {
EventType type;
int pos;
bool operator<(const Event& event) const { return type < event.type; }
};
vector<Edge*> sweepline(vector<Edge*> planar, vector<pt> queries)
{
using pt_type = decltype(pt::x);
// collect all x-coordinates
auto s =
set<pt_type, std::function<bool(const pt_type&, const pt_type&)>>(lt);
for (pt p : queries)
s.insert(p.x);
for (Edge* e : planar) {
s.insert(e->l.x);
s.insert(e->r.x);
}
// map all x-coordinates to ids
int cid = 0;
auto id =
map<pt_type, int, std::function<bool(const pt_type&, const pt_type&)>>(
lt);
for (auto x : s)
id[x] = cid++;
// create events
auto t = set<Edge*, decltype(*edge_cmp)>(edge_cmp);
auto vert_cmp = [](const pair<pt_type, int>& l,
const pair<pt_type, int>& r) {
if (!eq(l.first, r.first))
return lt(l.first, r.first);
return l.second < r.second;
};
auto vert = set<pair<pt_type, int>, decltype(vert_cmp)>(vert_cmp);
vector<vector<Event>> events(cid);
for (int i = 0; i < (int)queries.size(); i++) {
int x = id[queries[i].x];
events[x].push_back(Event{GET, i});
}
for (int i = 0; i < (int)planar.size(); i++) {
int lx = id[planar[i]->l.x], rx = id[planar[i]->r.x];
if (lx > rx) {
swap(lx, rx);
swap(planar[i]->l, planar[i]->r);
}
if (lx == rx) {
events[lx].push_back(Event{VERT, i});
} else {
events[lx].push_back(Event{ADD, i});
events[rx].push_back(Event{DEL, i});
}
}
// perform sweep line algorithm
vector<Edge*> ans(queries.size(), nullptr);
for (int x = 0; x < cid; x++) {
sort(events[x].begin(), events[x].end());
vert.clear();
for (Event event : events[x]) {
if (event.type == DEL) {
t.erase(planar[event.pos]);
}
if (event.type == VERT) {
vert.insert(make_pair(
min(planar[event.pos]->l.y, planar[event.pos]->r.y),
event.pos));
}
if (event.type == ADD) {
t.insert(planar[event.pos]);
}
if (event.type == GET) {
auto jt = vert.upper_bound(
make_pair(queries[event.pos].y, planar.size()));
if (jt != vert.begin()) {
--jt;
int i = jt->second;
if (ge(max(planar[i]->l.y, planar[i]->r.y),
queries[event.pos].y)) {
ans[event.pos] = planar[i];
continue;
}
}
Edge* e = new Edge;
e->l = e->r = queries[event.pos];
auto it = t.upper_bound(e);
if (it != t.begin())
ans[event.pos] = *(--it);
delete e;
}
}
for (Event event : events[x]) {
if (event.type != GET)
continue;
if (ans[event.pos] != nullptr &&
eq(ans[event.pos]->l.x, ans[event.pos]->r.x))
continue;
Edge* e = new Edge;
e->l = e->r = queries[event.pos];
auto it = t.upper_bound(e);
delete e;
if (it == t.begin())
e = nullptr;
else
e = *(--it);
if (ans[event.pos] == nullptr) {
ans[event.pos] = e;
continue;
}
if (e == nullptr)
continue;
if (e == ans[event.pos])
continue;
if (id[ans[event.pos]->r.x] == x) {
if (id[e->l.x] == x) {
if (gt(e->l.y, ans[event.pos]->r.y))
ans[event.pos] = e;
}
} else {
ans[event.pos] = e;
}
}
}
return ans;
}
struct DCEL {
struct Edge {
pt origin;
Edge* nxt = nullptr;
Edge* twin = nullptr;
int face;
};
vector<Edge*> body;
};
vector<pair<int, int>> point_location(DCEL planar, vector<pt> queries)
{
vector<pair<int, int>> ans(queries.size());
vector<Edge*> planar2;
map<intptr_t, int> pos;
map<intptr_t, int> added_on;
int n = planar.body.size();
for (int i = 0; i < n; i++) {
if (planar.body[i]->face > planar.body[i]->twin->face)
continue;
Edge* e = new Edge;
e->l = planar.body[i]->origin;
e->r = planar.body[i]->twin->origin;
added_on[(intptr_t)e] = i;
pos[(intptr_t)e] =
lt(planar.body[i]->origin.x, planar.body[i]->twin->origin.x)
? planar.body[i]->face
: planar.body[i]->twin->face;
planar2.push_back(e);
}
auto res = sweepline(planar2, queries);
for (int i = 0; i < (int)queries.size(); i++) {
if (res[i] == nullptr) {
ans[i] = make_pair(1, -1);
continue;
}
pt p = queries[i];
pt l = res[i]->l, r = res[i]->r;
if (eq(p.cross(l, r), 0) && le(p.dot(l, r), 0)) {
ans[i] = make_pair(0, added_on[(intptr_t)res[i]]);
continue;
}
ans[i] = make_pair(1, pos[(intptr_t)res[i]]);
}
for (auto e : planar2)
delete e;
return ans;
}