summaryrefslogtreecommitdiffstats
path: root/src/livarot/sweep-event.cpp
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/livarot/sweep-event.cpp284
1 files changed, 284 insertions, 0 deletions
diff --git a/src/livarot/sweep-event.cpp b/src/livarot/sweep-event.cpp
new file mode 100644
index 0000000..bb9e4e7
--- /dev/null
+++ b/src/livarot/sweep-event.cpp
@@ -0,0 +1,284 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * TODO: insert short description here
+ *//*
+ * Authors: see git history
+ *
+ * Copyright (C) 2018 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <glib.h>
+#include "livarot/sweep-event-queue.h"
+#include "livarot/sweep-tree.h"
+#include "livarot/sweep-event.h"
+#include "livarot/Shape.h"
+
+SweepEventQueue::SweepEventQueue(int s) : nbEvt(0), maxEvt(s)
+{
+ /* FIXME: use new[] for this, but this causes problems when delete[]
+ ** calls the SweepEvent destructors.
+ */
+ events = (SweepEvent *) g_malloc(maxEvt * sizeof(SweepEvent));
+ inds = new int[maxEvt];
+}
+
+SweepEventQueue::~SweepEventQueue()
+{
+ g_free(events);
+ delete []inds;
+}
+
+SweepEvent *SweepEventQueue::add(SweepTree *iLeft, SweepTree *iRight, Geom::Point &px, double itl, double itr)
+{
+ if (nbEvt > maxEvt) {
+ return nullptr;
+ }
+
+ int const n = nbEvt++;
+ events[n].MakeNew (iLeft, iRight, px, itl, itr);
+
+ SweepTree *t[2] = { iLeft, iRight };
+ for (auto & i : t) {
+ Shape *s = i->src;
+ Shape::dg_arete const &e = s->getEdge(i->bord);
+ int const n = std::max(e.st, e.en);
+ s->pData[n].pending++;;
+ }
+
+ events[n].ind = n;
+ inds[n] = n;
+
+ int curInd = n;
+ while (curInd > 0) {
+ int const half = (curInd - 1) / 2;
+ int const no = inds[half];
+ if (px[1] < events[no].posx[1]
+ || (px[1] == events[no].posx[1] && px[0] < events[no].posx[0]))
+ {
+ events[n].ind = half;
+ events[no].ind = curInd;
+ inds[half] = n;
+ inds[curInd] = no;
+ } else {
+ break;
+ }
+
+ curInd = half;
+ }
+
+ return events + n;
+}
+
+
+
+bool SweepEventQueue::peek(SweepTree * &iLeft, SweepTree * &iRight, Geom::Point &px, double &itl, double &itr)
+{
+ if (nbEvt <= 0) {
+ return false;
+ }
+
+ SweepEvent const &e = events[inds[0]];
+
+ iLeft = e.sweep[LEFT];
+ iRight = e.sweep[RIGHT];
+ px = e.posx;
+ itl = e.tl;
+ itr = e.tr;
+
+ return true;
+}
+
+bool SweepEventQueue::extract(SweepTree * &iLeft, SweepTree * &iRight, Geom::Point &px, double &itl, double &itr)
+{
+ if (nbEvt <= 0) {
+ return false;
+ }
+
+ SweepEvent &e = events[inds[0]];
+
+ iLeft = e.sweep[LEFT];
+ iRight = e.sweep[RIGHT];
+ px = e.posx;
+ itl = e.tl;
+ itr = e.tr;
+ remove(&e);
+
+ return true;
+}
+
+
+void SweepEventQueue::remove(SweepEvent *e)
+{
+ if (nbEvt <= 1) {
+ e->MakeDelete ();
+ nbEvt = 0;
+ return;
+ }
+
+ int const n = e->ind;
+ int to = inds[n];
+ e->MakeDelete();
+ relocate(&events[--nbEvt], to);
+
+ int const moveInd = nbEvt;
+ if (moveInd == n) {
+ return;
+ }
+
+ to = inds[moveInd];
+
+ events[to].ind = n;
+ inds[n] = to;
+
+ int curInd = n;
+ Geom::Point const px = events[to].posx;
+ bool didClimb = false;
+ while (curInd > 0) {
+ int const half = (curInd - 1) / 2;
+ int const no = inds[half];
+ if (px[1] < events[no].posx[1]
+ || (px[1] == events[no].posx[1] && px[0] < events[no].posx[0]))
+ {
+ events[to].ind = half;
+ events[no].ind = curInd;
+ inds[half] = to;
+ inds[curInd] = no;
+ didClimb = true;
+ } else {
+ break;
+ }
+ curInd = half;
+ }
+
+ if (didClimb) {
+ return;
+ }
+
+ while (2 * curInd + 1 < nbEvt) {
+ int const child1 = 2 * curInd + 1;
+ int const child2 = child1 + 1;
+ int const no1 = inds[child1];
+ int const no2 = inds[child2];
+ if (child2 < nbEvt) {
+ if (px[1] > events[no1].posx[1]
+ || (px[1] == events[no1].posx[1]
+ && px[0] > events[no1].posx[0]))
+ {
+ if (events[no2].posx[1] > events[no1].posx[1]
+ || (events[no2].posx[1] == events[no1].posx[1]
+ && events[no2].posx[0] > events[no1].posx[0]))
+ {
+ events[to].ind = child1;
+ events[no1].ind = curInd;
+ inds[child1] = to;
+ inds[curInd] = no1;
+ curInd = child1;
+ } else {
+ events[to].ind = child2;
+ events[no2].ind = curInd;
+ inds[child2] = to;
+ inds[curInd] = no2;
+ curInd = child2;
+ }
+ } else {
+ if (px[1] > events[no2].posx[1]
+ || (px[1] == events[no2].posx[1]
+ && px[0] > events[no2].posx[0]))
+ {
+ events[to].ind = child2;
+ events[no2].ind = curInd;
+ inds[child2] = to;
+ inds[curInd] = no2;
+ curInd = child2;
+ } else {
+ break;
+ }
+ }
+ } else {
+ if (px[1] > events[no1].posx[1]
+ || (px[1] == events[no1].posx[1]
+ && px[0] > events[no1].posx[0]))
+ {
+ events[to].ind = child1;
+ events[no1].ind = curInd;
+ inds[child1] = to;
+ inds[curInd] = no1;
+ }
+
+ break;
+ }
+ }
+}
+
+
+
+
+void SweepEventQueue::relocate(SweepEvent *e, int to)
+{
+ if (inds[e->ind] == to) {
+ return; // j'y suis deja
+ }
+
+ events[to] = *e;
+
+ e->sweep[LEFT]->evt[RIGHT] = events + to;
+ e->sweep[RIGHT]->evt[LEFT] = events + to;
+ inds[e->ind] = to;
+}
+
+
+/*
+ * a simple binary heap
+ * it only contains intersection events
+ * the regular benley-ottman stuffs the segment ends in it too, but that not needed here since theses points
+ * are already sorted. and the binary heap is much faster with only intersections...
+ * the code sample on which this code is based comes from purists.org
+ */
+SweepEvent::SweepEvent()
+{
+ MakeNew (nullptr, nullptr, Geom::Point(0, 0), 0, 0);
+}
+
+SweepEvent::~SweepEvent()
+{
+ MakeDelete();
+}
+
+void SweepEvent::MakeNew(SweepTree *iLeft, SweepTree *iRight, Geom::Point const &px, double itl, double itr)
+{
+ ind = -1;
+ posx = px;
+ tl = itl;
+ tr = itr;
+ sweep[LEFT] = iLeft;
+ sweep[RIGHT] = iRight;
+ sweep[LEFT]->evt[RIGHT] = this;
+ sweep[RIGHT]->evt[LEFT] = this;
+}
+
+void SweepEvent::MakeDelete()
+{
+ for (int i = 0; i < 2; i++) {
+ if (sweep[i]) {
+ Shape *s = sweep[i]->src;
+ Shape::dg_arete const &e = s->getEdge(sweep[i]->bord);
+ int const n = std::max(e.st, e.en);
+ s->pData[n].pending--;
+ }
+
+ sweep[i]->evt[1 - i] = nullptr;
+ sweep[i] = nullptr;
+ }
+}
+
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-02 07:03:26 +0000