354 inline const T &
top()
const {
return m_data.
first();}
356 static inline int parent(
int i) {
return (
i - 1) / 2;}
357 static inline int left(
int i) {
return 2 *
i + 1;}
358 static inline int right(
int i) {
return 2 *
i + 2;}
360 QDataBuffer<T> m_data;
366 int current =
m_data.size();
367 int parent = QMaxHeap::parent(current);
369 while (current != 0 &&
m_data.at(parent) <
x) {
372 parent = QMaxHeap::parent(current);
386 int left = QMaxHeap::left(current);
387 int right = QMaxHeap::right(current);
393 if (
m_data.at(greater) < back)
398 m_data.at(current) = back;
409 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 17, 27, 3,
410 1, 29, 3, 21, 7, 17, 15, 9, 43, 35, 15, 0, 0, 0, 0, 0
423 for (
int i = 0;
i < 5; ++
i) {
424 int mid = (high + low) / 2;
459 m_array =
new quint64[m_capacity];
466 int oldCapacity = m_capacity;
469 m_array =
new quint64[m_capacity];
471 for (
int i = 0;
i < oldCapacity; ++
i) {
472 if (oldArray[
i] != UNUSED)
481 if (m_count > 3 * m_capacity / 4)
484 for (
int i = 0;
i < m_capacity; ++
i) {
486 if (
index >= m_capacity)
490 if (m_array[
index] == UNUSED) {
496 Q_ASSERT_X(0,
"QInt64Hash<T>::insert",
"Hash set full.");
502 for (
int i = 0;
i < m_capacity; ++
i) {
504 if (
index >= m_capacity)
508 if (m_array[
index] == UNUSED)
516 for (
int i = 0;
i < m_capacity; ++
i)
538 : m_parent(parent), m_edges(0), m_events(0), m_splits(0), m_initialPointCount(0) { }
543 inline int &upper() {
return pointingUp ? to : from;}
544 inline int &lower() {
return pointingUp ? from : to;}
545 inline int upper()
const {
return pointingUp ? to : from;}
546 inline int lower()
const {
return pointingUp ? from : to;}
553 bool pointingUp, originallyPointingUp;
558 bool operator < (
const Intersection &
other)
const {
return other.intersectionPoint < intersectionPoint;}
583#ifdef Q_TRIANGULATOR_DEBUG
584 friend class DebugDialog;
586 class DebugDialog :
public QDialog
589 DebugDialog(ComplexToSimple *parent,
int currentVertex);
592 void wheelEvent(QWheelEvent *);
596 ComplexToSimple *m_parent;
604 bool calculateIntersection(
int left,
int right);
605 bool edgeIsLeftOfEdge(
int leftEdgeIndex,
int rightEdgeIndex)
const;
612 void sortEdgeList(
const QPodPoint eventPoint);
613 void fillPriorityQueue();
614 void calculateIntersections();
615 int splitEdge(
int splitIndex);
616 bool splitEdgesAtIntersections();
617 void insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges,
int i);
618 void removeUnwantedEdgesAndConnect();
619 void removeUnusedPoints();
622 QDataBuffer<Edge> m_edges;
623 QRBTree<int> m_edgeList;
624 QDataBuffer<Event> m_events;
625 QDataBuffer<Split> m_splits;
626 QMaxHeap<Intersection> m_topIntersection;
628 int m_initialPointCount;
630#ifdef Q_TRIANGULATOR_DEBUG
631 friend class ComplexToSimple::DebugDialog;
642 : m_parent(parent), m_edges(0), m_upperVertex(0), m_clockwiseOrder(
false) { }
645 enum VertexType {MergeVertex, EndVertex, RegularVertex, StartVertex, SplitVertex};
650 int helper, twin,
next, previous;
654 int upper()
const {
return (pointingUp ? to : from);}
655 int lower()
const {
return (pointingUp ? from : to);}
658 friend class CompareVertices;
659 class CompareVertices
663 bool operator () (
int i,
int j)
const;
668 void setupDataStructures();
669 void removeZeroLengthEdges();
670 void fillPriorityQueue();
671 bool edgeIsLeftOfEdge(
int leftEdgeIndex,
int rightEdgeIndex)
const;
676 void classifyVertex(
int i);
677 void classifyVertices();
679 bool pointIsInSector(
int vertex,
int sector);
680 int findSector(
int edge,
int vertex);
681 void createDiagonal(
int lower,
int upper);
682 void monotoneDecomposition();
685 QRBTree<int> m_edgeList;
686 QDataBuffer<Edge> m_edges;
687 QDataBuffer<int> m_upperVertex;
688 bool m_clockwiseOrder;
699 : m_parent(parent), m_first(0), m_length(0) { }
702 inline T
indices(
int index)
const {
return m_parent->m_indices.at(
index + m_first);}
704 inline int previous(
int index)
const {
return (
index + m_length - 1) % m_length;}
705 inline bool less(
int i,
int j)
const {
return m_parent->m_vertices.at((
qint32)
indices(
i)) < m_parent->m_vertices.at(
indices(
j));}
706 inline bool leftOfEdge(
int i,
int j,
int k)
const
712 QTriangulator<T> *m_parent;
718 : m_vertices(0), m_hint(0) { }
727 QVertexSet<T> triangulate();
728 QVertexSet<T> polyline();
730 QDataBuffer<QPodPoint> m_vertices;
742 for (
int i = 0;
i < m_vertices.size(); ++
i) {
760 result.indices = m_indices;
761 result.vertices.resize(2 * m_vertices.size());
762 for (
int i = 0;
i < m_vertices.size(); ++
i) {
772 for (
int i = 0;
i < m_vertices.size(); ++
i) {
786 result.indices = m_indices;
787 result.vertices.resize(2 * m_vertices.size());
788 for (
int i = 0;
i < m_vertices.size(); ++
i) {
799 m_vertices.resize(
count);
800 m_indices.resize(
count + 1);
808 m_indices[
count] = T(-1);
814 m_hint =
path.hints();
821 for (
int i = 0;
i <
path.elementCount(); ++
i, ++e,
p += 2) {
824 if (!m_indices.isEmpty())
825 m_indices.push_back(T(-1));
828 m_indices.push_back(T(m_vertices.size()));
829 m_vertices.resize(m_vertices.size() + 1);
838 for (
int i = 0;
i < 4; ++
i)
839 matrix.map(
p[2 *
i - 2],
p[2 *
i - 1], &pts[2 *
i + 0], &pts[2 *
i + 1]);
840 for (
int i = 0;
i < 8; ++
i)
845 for (
int j = 1;
j < poly.size(); ++
j) {
846 m_indices.
push_back(T(m_vertices.size()));
847 m_vertices.resize(m_vertices.size() + 1);
857 Q_ASSERT_X(0,
"QTriangulator::triangulate",
"Unexpected element type.");
862 for (
int i = 0;
i <
path.elementCount(); ++
i,
p += 2) {
863 m_indices.push_back(T(m_vertices.size()));
864 m_vertices.resize(m_vertices.size() + 1);
871 m_indices.push_back(T(-1));
886 m_initialPointCount = m_parent->m_vertices.size();
889 calculateIntersections();
890 }
while (splitEdgesAtIntersections());
892 removeUnwantedEdgesAndConnect();
893 removeUnusedPoints();
895 m_parent->m_indices.clear();
896 QBitArray processed(m_edges.size(),
false);
899 if (processed.
at(
first) || m_edges.at(
first).next == -1)
905 Q_ASSERT(m_edges.at(m_edges.at(
i).next).previous ==
i);
906 m_parent->m_indices.push_back(m_edges.at(
i).from);
908 i = m_edges.at(
i).next;
910 m_parent->m_indices.push_back(T(-1));
920 for (
int i = 0;
i < m_parent->m_indices.size(); ++
i) {
921 if (m_parent->m_indices.at(
i) == T(-1)) {
922 if (m_edges.size() !=
first)
923 m_edges.last().to = m_edges.at(
first).from;
924 first = m_edges.size();
926 Q_ASSERT(
i + 1 < m_parent->m_indices.size());
928 Edge edge = {
nullptr, int(m_parent->m_indices.at(
i)), int(m_parent->m_indices.at(
i + 1)), -1, -1, 0,
true,
false,
false};
932 if (
first != m_edges.size())
933 m_edges.last().to = m_edges.at(
first).from;
934 for (
int i = 0;
i < m_edges.size(); ++
i) {
935 m_edges.at(
i).originallyPointingUp = m_edges.at(
i).pointingUp =
936 m_parent->m_vertices.at(m_edges.at(
i).to) < m_parent->m_vertices.at(m_edges.at(
i).from);
944 const Edge &e1 = m_edges.at(
left);
945 const Edge &e2 = m_edges.at(
right);
955 if (m_processedEdgePairs.contains(
key))
957 m_processedEdgePairs.insert(
key);
959 Intersection intersection;
960 intersection.leftEdge =
left;
961 intersection.rightEdge =
right;
964 if (!intersection.intersectionPoint.isValid())
967 Q_ASSERT(intersection.intersectionPoint.isOnLine(
u1,
u2));
968 Q_ASSERT(intersection.intersectionPoint.isOnLine(
v1,
v2));
970 intersection.vertex = m_parent->m_vertices.size();
971 m_topIntersection.push(intersection);
972 m_parent->m_vertices.add(intersection.intersectionPoint.round());
979 const Edge &leftEdge = m_edges.at(leftEdgeIndex);
980 const Edge &rightEdge = m_edges.at(rightEdgeIndex);
981 const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper());
982 const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower());
983 const QPodPoint &upper = m_parent->m_vertices.at(leftEdge.upper());
1001 if (edgeIsLeftOfEdge(edgeIndex, current->
data)) {
1002 current = current->
left;
1005 current = current->
right;
1011template <
typename T>
1014 if (!m_edgeList.root)
1017 QRBTree<int>::Node *current = (after ? m_edgeList.next(after) : m_edgeList.front(m_edgeList.root));
1019 if (edgeIsLeftOfEdge(edgeIndex, current->
data))
1022 current = m_edgeList.next(current);
1027template <
typename T>
1033 const QPodPoint &
v1 = m_parent->m_vertices.at(m_edges.at(current->
data).lower());
1034 const QPodPoint &
v2 = m_parent->m_vertices.at(m_edges.at(current->
data).upper());
1040 current = (
d < 0 ? current->
left : current->
right);
1042 if (current ==
nullptr)
1047 const QPodPoint &
v1 = m_parent->m_vertices.at(m_edges.at(current->
data).lower());
1048 const QPodPoint &
v2 = m_parent->m_vertices.at(m_edges.at(current->
data).upper());
1053 current = current->
left;
1055 current = current->
right;
1061 const QPodPoint &
v1 = m_parent->m_vertices.at(m_edges.at(current->
data).lower());
1062 const QPodPoint &
v2 = m_parent->m_vertices.at(m_edges.at(current->
data).upper());
1067 current = current->
right;
1069 current = current->
left;
1076template <
typename T>
1083 const QPodPoint &
v1 = m_parent->m_vertices.at(m_edges.at(current->
data).lower());
1084 const QPodPoint &
v2 = m_parent->m_vertices.at(m_edges.at(current->
data).upper());
1090 current = current->
left;
1093 current = current->
right;
1102 current = mid->
left;
1104 const QPodPoint &
v1 = m_parent->m_vertices.at(m_edges.at(current->
data).lower());
1105 const QPodPoint &
v2 = m_parent->m_vertices.at(m_edges.at(current->
data).upper());
1109 current = current->
left;
1112 current = current->
right;
1116 current = mid->
right;
1118 const QPodPoint &
v1 = m_parent->m_vertices.at(m_edges.at(current->
data).lower());
1119 const QPodPoint &
v2 = m_parent->m_vertices.at(m_edges.at(current->
data).upper());
1123 current = current->
right;
1126 current = current->
left;
1133template <
typename T>
1140 const QPodPoint &u = m_parent->m_vertices.at(m_edges.at(leftmost->data).from);
1141 const QPodPoint &
v = m_parent->m_vertices.at(m_edges.at(leftmost->data).to);
1145 m_splits.add(
split);
1146 if (leftmost == rightmost)
1148 leftmost = m_edgeList.next(leftmost);
1152template <
typename T>
1161 while (leftmost != rightmost) {
1162 Edge &
left = m_edges.at(leftmost->data);
1163 Edge &
right = m_edges.at(rightmost->data);
1165 qSwap(leftmost->data, rightmost->data);
1166 leftmost = m_edgeList.next(leftmost);
1167 if (leftmost == rightmost)
1169 rightmost = m_edgeList.previous(rightmost);
1172 rightmost = m_edgeList.next(storeRightmost);
1173 leftmost = m_edgeList.previous(storeLeftmost);
1175 calculateIntersection(leftmost->data, storeLeftmost->data);
1177 calculateIntersection(storeRightmost->data, rightmost->data);
1180template <
typename T>
1184 while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint < eventPoint2) {
1185 Intersection intersection = m_topIntersection.pop();
1188 int currentVertex = intersection.vertex;
1197 const Edge &edge = m_edges.at(previous->
data);
1200 if (!currentIntersectionPoint.isOnLine(u,
v)) {
1201 Q_ASSERT(!currentIntersectionPoint.isAccurate() ||
qCross(currentIntersectionPoint.upperLeft - u,
v - u) != 0);
1204 leftmost = previous;
1211 const Edge &edge = m_edges.at(
next->data);
1214 if (!currentIntersectionPoint.isOnLine(u,
v)) {
1215 Q_ASSERT(!currentIntersectionPoint.isAccurate() ||
qCross(currentIntersectionPoint.upperLeft - u,
v - u) != 0);
1222 splitEdgeListRange(leftmost, rightmost, currentVertex, currentIntersectionPoint);
1223 reorderEdgeListRange(leftmost, rightmost);
1225 while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= currentIntersectionPoint)
1226 m_topIntersection.pop();
1228#ifdef Q_TRIANGULATOR_DEBUG
1229 DebugDialog
dialog(
this, intersection.vertex);
1236template <
typename T>
1240 m_events.reserve(m_edges.size() * 2);
1241 for (
int i = 0;
i < m_edges.size(); ++
i) {
1242 Q_ASSERT(m_edges.at(
i).previous == -1 && m_edges.at(
i).next == -1);
1243 Q_ASSERT(m_edges.at(
i).node ==
nullptr);
1244 Q_ASSERT(m_edges.at(
i).pointingUp == m_edges.at(
i).originallyPointingUp);
1245 Q_ASSERT(m_edges.at(
i).pointingUp == (m_parent->m_vertices.at(m_edges.at(
i).to) < m_parent->m_vertices.at(m_edges.at(
i).from)));
1247 if (m_parent->m_vertices.at(m_edges.at(
i).to) != m_parent->m_vertices.at(m_edges.at(
i).from)) {
1248 QPodPoint upper = m_parent->m_vertices.at(m_edges.at(
i).upper());
1249 QPodPoint lower = m_parent->m_vertices.at(m_edges.at(
i).lower());
1250 Event upperEvent = {{upper.
x, upper.
y}, Event::Upper,
i};
1251 Event lowerEvent = {{lower.
x, lower.
y}, Event::Lower,
i};
1252 m_events.add(upperEvent);
1253 m_events.add(lowerEvent);
1257 std::sort(m_events.data(), m_events.data() + m_events.size());
1260template <
typename T>
1263 fillPriorityQueue();
1265 Q_ASSERT(m_topIntersection.empty());
1266 Q_ASSERT(m_edgeList.root ==
nullptr);
1269 while (!m_events.isEmpty()) {
1270 Event event = m_events.last();
1271 sortEdgeList(
event.point);
1276 int vertex = (
event.type == Event::Upper ? m_edges.at(
event.edge).upper() : m_edges.at(
event.edge).lower());
1279 if (
range.first !=
nullptr) {
1280 splitEdgeListRange(
range.first,
range.second, vertex, eventPoint);
1281 reorderEdgeListRange(
range.first,
range.second);
1285 while (!m_events.isEmpty() && m_events.last().point ==
event.point) {
1286 event = m_events.last();
1287 m_events.pop_back();
1290 if (m_edges.at(
i).node) {
1295 m_edgeList.deleteNode(m_edges.at(
i).node);
1298 calculateIntersection(
left->data,
right->data);
1303 m_edgeList.attachAfter(
left, m_edges.at(
i).node = m_edgeList.newNode());
1304 m_edges.at(
i).node->data =
i;
1307 calculateIntersection(
left->data,
i);
1309 calculateIntersection(
i,
right->data);
1312 while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= eventPoint)
1313 m_topIntersection.pop();
1314#ifdef Q_TRIANGULATOR_DEBUG
1315 DebugDialog
dialog(
this, vertex);
1319 m_processedEdgePairs.clear();
1326template <
typename T>
1329 const Split &
split = m_splits.at(splitIndex);
1330 Edge &lowerEdge = m_edges.at(
split.edge);
1331 Q_ASSERT(lowerEdge.node ==
nullptr);
1332 Q_ASSERT(lowerEdge.previous == -1 && lowerEdge.next == -1);
1334 if (lowerEdge.from ==
split.vertex)
1336 if (lowerEdge.to ==
split.vertex)
1337 return lowerEdge.next;
1343 Edge upperEdge = lowerEdge;
1344 upperEdge.mayIntersect |= !
split.accurate;
1345 lowerEdge.mayIntersect = !
split.accurate;
1346 if (lowerEdge.pointingUp) {
1347 lowerEdge.to = upperEdge.from =
split.vertex;
1348 m_edges.add(upperEdge);
1349 return m_edges.size() - 1;
1351 lowerEdge.from = upperEdge.to =
split.vertex;
1352 m_edges.add(upperEdge);
1357template <
typename T>
1360 for (
int i = 0;
i < m_edges.size(); ++
i)
1361 m_edges.at(
i).mayIntersect =
false;
1362 bool checkForNewIntersections =
false;
1363 for (
int i = 0;
i < m_splits.size(); ++
i) {
1365 checkForNewIntersections |= !m_splits.at(
i).accurate;
1367 for (
int i = 0;
i < m_edges.size(); ++
i) {
1368 m_edges.at(
i).originallyPointingUp = m_edges.at(
i).pointingUp =
1369 m_parent->m_vertices.at(m_edges.at(
i).to) < m_parent->m_vertices.at(m_edges.at(
i).from);
1372 return checkForNewIntersections;
1375template <
typename T>
1379 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(
i).from) != m_parent->m_vertices.at(m_edges.at(
i).to));
1382 int windingNumber = m_edges.at(
i).winding;
1383 if (m_edges.at(
i).originallyPointingUp)
1393 if (!orderedEdges.isEmpty()) {
1394 int j = orderedEdges[orderedEdges.size() - 1];
1396 if (m_edges.at(
j).next == -1 && m_edges.at(
j).previous == -1
1397 && (m_parent->m_vertices.at(m_edges.at(
i).from) == m_parent->m_vertices.at(m_edges.at(
j).to))
1398 && (m_parent->m_vertices.at(m_edges.at(
i).to) == m_parent->m_vertices.at(m_edges.at(
j).from))) {
1399 orderedEdges.removeLast();
1403 orderedEdges.append(
i);
1406template <
typename T>
1409 Q_ASSERT(m_edgeList.root ==
nullptr);
1411 fillPriorityQueue();
1413 ShortArray orderedEdges;
1415 while (!m_events.isEmpty()) {
1416 Event event = m_events.last();
1417 int edgeIndex =
event.edge;
1426 orderedEdges.clear();
1428 if (m_edgeList.root) {
1429 QRBTree<int>::Node *current = (
b.first ? m_edgeList.next(
b.first) : m_edgeList.front(m_edgeList.root));
1431 while (current !=
b.second) {
1435 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(current->
data).from) ==
event.point || m_parent->m_vertices.at(m_edges.at(current->
data).to) ==
event.point);
1436 insertEdgeIntoVectorIfWanted(orderedEdges, current->
data);
1437 current = m_edgeList.next(current);
1443 event = m_events.last();
1444 m_events.pop_back();
1445 edgeIndex =
event.edge;
1448 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(edgeIndex).from) != m_parent->m_vertices.at(m_edges.at(edgeIndex).to));
1450 if (m_edges.at(edgeIndex).node) {
1453 m_edgeList.deleteNode(m_edges.at(edgeIndex).node);
1458 m_edgeList.attachAfter(
left, m_edges.at(edgeIndex).node = m_edgeList.newNode());
1459 m_edges.at(edgeIndex).node->data = edgeIndex;
1461 }
while (!m_events.isEmpty() && m_events.last().point ==
event.point);
1463 if (m_edgeList.root) {
1464 QRBTree<int>::Node *current = (
b.first ? m_edgeList.next(
b.first) : m_edgeList.front(m_edgeList.root));
1467 int currentWindingNumber = (
b.first ? m_edges.at(
b.first->data).winding : 0);
1468 while (current !=
b.second) {
1471 int i = current->
data;
1472 Q_ASSERT(m_edges.at(
i).node == current);
1475 int ccwWindingNumber = m_edges.at(
i).winding = currentWindingNumber;
1476 if (m_edges.at(
i).originallyPointingUp) {
1477 --m_edges.at(
i).winding;
1479 ++m_edges.at(
i).winding;
1482 currentWindingNumber = m_edges.at(
i).winding;
1485 if ((ccwWindingNumber & 1) == 0) {
1486 Q_ASSERT(m_edges.at(
i).previous == -1 && m_edges.at(
i).next == -1);
1487 qSwap(m_edges.at(
i).from, m_edges.at(
i).to);
1488 m_edges.at(
i).pointingUp = !m_edges.at(
i).pointingUp;
1491 current = m_edgeList.next(current);
1495 current = (
b.second ? m_edgeList.previous(
b.second) : m_edgeList.back(m_edgeList.root));
1496 while (current !=
b.first) {
1499 insertEdgeIntoVectorIfWanted(orderedEdges, current->
data);
1500 current = m_edgeList.previous(current);
1503 if (orderedEdges.isEmpty())
1506 Q_ASSERT((orderedEdges.size() & 1) == 0);
1511 if (m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).from) ==
event.point) {
1513 int copy = orderedEdges[0];
1514 orderedEdges.append(
copy);
1516 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).to) ==
event.point);
1521 int pointIndex = INT_MAX;
1522 for (
int j =
i;
j < orderedEdges.size();
j += 2) {
1524 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[
j]).to) ==
event.point);
1525 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[
j + 1]).from) ==
event.point);
1526 if (m_edges.at(orderedEdges[
j]).to < pointIndex)
1527 pointIndex = m_edges.at(orderedEdges[
j]).to;
1528 if (m_edges.at(orderedEdges[
j + 1]).from < pointIndex)
1529 pointIndex = m_edges.at(orderedEdges[
j + 1]).from;
1532 for (;
i < orderedEdges.size();
i += 2) {
1534 m_edges.at(orderedEdges[
i]).to = m_edges.at(orderedEdges[
i + 1]).from = pointIndex;
1536 Q_ASSERT(m_edges.at(orderedEdges[
i]).pointingUp || m_edges.at(orderedEdges[
i]).previous != -1);
1537 Q_ASSERT(!m_edges.at(orderedEdges[
i + 1]).pointingUp || m_edges.at(orderedEdges[
i + 1]).next != -1);
1539 m_edges.at(orderedEdges[
i]).next = orderedEdges[
i + 1];
1540 m_edges.at(orderedEdges[
i + 1]).previous = orderedEdges[
i];
1545template <
typename T>
1547 QBitArray used(m_parent->m_vertices.size(),
false);
1548 for (
int i = 0;
i < m_edges.size(); ++
i) {
1549 Q_ASSERT((m_edges.at(
i).previous == -1) == (m_edges.at(
i).next == -1));
1550 if (m_edges.at(
i).next != -1)
1551 used.setBit(m_edges.at(
i).from);
1553 QDataBuffer<quint32> newMapping(m_parent->m_vertices.size());
1554 newMapping.resize(m_parent->m_vertices.size());
1556 for (
int i = 0;
i < m_parent->m_vertices.size(); ++
i) {
1558 m_parent->m_vertices.at(
count) = m_parent->m_vertices.at(
i);
1559 newMapping.at(
i) =
count;
1563 m_parent->m_vertices.resize(
count);
1564 for (
int i = 0;
i < m_edges.size(); ++
i) {
1565 m_edges.at(
i).from = newMapping.at(m_edges.at(
i).from);
1566 m_edges.at(
i).to = newMapping.at(m_edges.at(
i).to);
1570template <
typename T>
1573 if (point ==
other.point)
1575 return other.point < point;
1582#ifdef Q_TRIANGULATOR_DEBUG
1583template <
typename T>
1585 : m_parent(parent), m_vertex(currentVertex)
1587 QDataBuffer<QPodPoint> &vertices = m_parent->m_parent->m_vertices;
1588 if (vertices.isEmpty())
1592 minX =
maxX = vertices.at(0).x;
1594 for (
int i = 1;
i < vertices.size(); ++
i) {
1595 minX =
qMin(minX, vertices.at(
i).x);
1600 int w =
maxX - minX;
1606template <
typename T>
1612 QDataBuffer<QPodPoint> &vertices = m_parent->m_parent->m_vertices;
1613 if (vertices.isEmpty())
1616 qreal halfPointSize =
qMin(m_window.width(), m_window.height()) / 300.0;
1617 p.setWindow(m_window.toRect());
1621 QDataBuffer<Edge> &edges = m_parent->m_edges;
1622 for (
int i = 0;
i < edges.size(); ++
i) {
1625 p.drawLine(u.
x, u.
y,
v.x,
v.y);
1628 for (
int i = 0;
i < vertices.size(); ++
i) {
1630 p.fillRect(
QRectF(
q.x - halfPointSize,
q.y - halfPointSize, 2 * halfPointSize, 2 * halfPointSize),
Qt::red);
1636 if (m_parent->m_edgeList.root) {
1642 p.drawLine(u.
x, u.
y,
v.x,
v.y);
1643 current = m_parent->m_edgeList.next(current);
1649 p.fillRect(
QRectF(
q.x - halfPointSize,
q.y - halfPointSize, 2 * halfPointSize, 2 * halfPointSize),
Qt::green);
1652 QDataBuffer<Split> &splits = m_parent->m_splits;
1653 for (
int i = 0;
i < splits.size(); ++
i) {
1655 QPodPoint u = vertices.at(edges.at(splits.at(
i).edge).from) -
q;
1656 QPodPoint v = vertices.at(edges.at(splits.at(
i).edge).to) -
q;
1660 u.
x *= 2 * halfPointSize / uLen;
1661 u.
y *= 2 * halfPointSize / uLen;
1664 v.x *= 2 * halfPointSize / vLen;
1665 v.y *= 2 * halfPointSize / vLen;
1669 p.drawLine(u.
x, u.
y,
v.x,
v.y);
1673template <
typename T>
1679 m_window =
QRectF(center - delta, center + delta);
1684template <
typename T>
1688 QPointF delta =
event->pos() - m_lastMousePos;
1689 delta.
setX(delta.
x() * m_window.width() /
width());
1690 delta.
setY(delta.
y() * m_window.height() /
height());
1691 m_window.translate(-delta.
x(), -delta.
y());
1692 m_lastMousePos =
event->pos();
1698template <
typename T>
1702 m_lastMousePos =
event->pos();
1712template <
typename T>
1715 setupDataStructures();
1716 removeZeroLengthEdges();
1717 monotoneDecomposition();
1719 m_parent->m_indices.clear();
1720 QBitArray processed(m_edges.size(),
false);
1727 Q_ASSERT(m_edges.at(m_edges.at(
i).next).previous ==
i);
1728 m_parent->m_indices.push_back(m_edges.at(
i).from);
1730 i = m_edges.at(
i).next;
1732 if (m_parent->m_indices.size() > 0 && m_parent->m_indices.back() != T(-1))
1733 m_parent->m_indices.push_back(T(-1));
1737template <
typename T>
1745 while (
i + 3 <= m_parent->m_indices.size()) {
1746 int start = m_edges.size();
1749 e.from = m_parent->m_indices.at(
i);
1750 e.type = RegularVertex;
1751 e.next = m_edges.size() + 1;
1752 e.previous = m_edges.size() - 1;
1755 Q_ASSERT(i < m_parent->m_indices.size());
1756 }
while (m_parent->m_indices.at(
i) != T(-1));
1758 m_edges.last().next =
start;
1759 m_edges.at(
start).previous = m_edges.size() - 1;
1763 for (
i = 0;
i < m_edges.size(); ++
i) {
1764 m_edges.at(
i).to = m_edges.at(m_edges.at(
i).next).from;
1765 m_edges.at(
i).pointingUp = m_parent->m_vertices.at(m_edges.at(
i).to) < m_parent->m_vertices.at(m_edges.at(
i).from);
1766 m_edges.at(
i).helper = -1;
1770template <
typename T>
1773 for (
int i = 0;
i < m_edges.size(); ++
i) {
1774 if (m_parent->m_vertices.at(m_edges.at(
i).from) == m_parent->m_vertices.at(m_edges.at(
i).to)) {
1775 m_edges.at(m_edges.at(
i).previous).next = m_edges.at(
i).next;
1776 m_edges.at(m_edges.at(
i).next).previous = m_edges.at(
i).previous;
1777 m_edges.at(m_edges.at(
i).next).from = m_edges.at(
i).from;
1778 m_edges.at(
i).next = -1;
1782 QDataBuffer<int> newMapping(m_edges.size());
1783 newMapping.resize(m_edges.size());
1785 for (
int i = 0;
i < m_edges.size(); ++
i) {
1786 if (m_edges.at(
i).next != -1) {
1787 m_edges.at(
count) = m_edges.at(
i);
1788 newMapping.at(
i) =
count;
1792 m_edges.resize(
count);
1793 for (
int i = 0;
i < m_edges.size(); ++
i) {
1794 m_edges.at(
i).next = newMapping.at(m_edges.at(
i).next);
1795 m_edges.at(
i).previous = newMapping.at(m_edges.at(
i).previous);
1799template <
typename T>
1802 m_upperVertex.reset();
1803 m_upperVertex.reserve(m_edges.size());
1804 for (
int i = 0;
i < m_edges.size(); ++
i)
1805 m_upperVertex.add(
i);
1806 CompareVertices cmp(
this);
1807 std::sort(m_upperVertex.data(), m_upperVertex.data() + m_upperVertex.size(), cmp);
1813template <
typename T>
1816 const Edge &leftEdge = m_edges.at(leftEdgeIndex);
1817 const Edge &rightEdge = m_edges.at(rightEdgeIndex);
1818 const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper());
1819 const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower());
1828template <
typename T>
1834 if (edgeIsLeftOfEdge(edgeIndex, current->
data)) {
1835 current = current->
left;
1838 current = current->
right;
1845template <
typename T>
1851 const QPodPoint &
p1 = m_parent->m_vertices.at(m_edges.at(current->
data).lower());
1852 const QPodPoint &
p2 = m_parent->m_vertices.at(m_edges.at(current->
data).upper());
1855 current = current->
left;
1858 current = current->
right;
1864template <
typename T>
1867 Edge &e2 = m_edges.at(
i);
1868 const Edge &e1 = m_edges.at(e2.previous);
1870 bool startOrSplit = (e1.pointingUp && !e2.pointingUp);
1871 bool endOrMerge = (!e1.pointingUp && e2.pointingUp);
1873 const QPodPoint &
p1 = m_parent->m_vertices.at(e1.from);
1874 const QPodPoint &
p2 = m_parent->m_vertices.at(e2.from);
1875 const QPodPoint &p3 = m_parent->m_vertices.at(e2.to);
1877 Q_ASSERT(
d != 0 || (!startOrSplit && !endOrMerge));
1879 e2.type = RegularVertex;
1881 if (m_clockwiseOrder) {
1883 e2.type = (
d < 0 ? SplitVertex : StartVertex);
1884 else if (endOrMerge)
1885 e2.type = (
d < 0 ? MergeVertex : EndVertex);
1888 e2.type = (
d > 0 ? SplitVertex : StartVertex);
1889 else if (endOrMerge)
1890 e2.type = (
d > 0 ? MergeVertex : EndVertex);
1894template <
typename T>
1897 for (
int i = 0;
i < m_edges.size(); ++
i)
1901template <
typename T>
1908 return leftOfPreviousEdge && leftOfNextEdge;
1910 return leftOfPreviousEdge || leftOfNextEdge;
1913template <
typename T>
1916 const QPodPoint &
center = m_parent->m_vertices.at(m_edges.at(sector).from);
1918 while (m_parent->m_vertices.at(m_edges.at(vertex).from) == center)
1919 vertex = m_edges.at(vertex).next;
1920 int next = m_edges.at(sector).next;
1921 while (m_parent->m_vertices.at(m_edges.at(
next).from) == center)
1923 int previous = m_edges.at(sector).previous;
1924 while (m_parent->m_vertices.at(m_edges.at(previous).from) == center)
1925 previous = m_edges.at(previous).previous;
1927 const QPodPoint &
p = m_parent->m_vertices.at(m_edges.at(vertex).from);
1928 const QPodPoint &
v1 = m_parent->m_vertices.at(m_edges.at(previous).from);
1930 if (m_clockwiseOrder)
1931 return pointIsInSector(
p,
v3, center,
v1);
1933 return pointIsInSector(
p,
v1, center,
v3);
1936template <
typename T>
1939 while (!pointIsInSector(vertex, edge)) {
1940 edge = m_edges.at(m_edges.at(edge).previous).twin;
1946template <
typename T>
1949 lower = findSector(lower, upper);
1950 upper = findSector(upper, lower);
1952 int prevLower = m_edges.at(lower).previous;
1953 int prevUpper = m_edges.at(upper).previous;
1957 e.twin = m_edges.size() + 1;
1959 e.previous = prevLower;
1960 e.from = m_edges.at(lower).from;
1961 e.to = m_edges.at(upper).from;
1962 m_edges.at(upper).previous = m_edges.at(prevLower).next = int(m_edges.size());
1965 e.twin = m_edges.size() - 1;
1967 e.previous = prevUpper;
1968 e.from = m_edges.at(upper).from;
1969 e.to = m_edges.at(lower).from;
1970 m_edges.at(lower).previous = m_edges.at(prevUpper).next = int(m_edges.size());
1974template <
typename T>
1977 if (m_edges.isEmpty())
1981 QDataBuffer<QPair<int, int> > diagonals(m_upperVertex.size());
1985 if (m_parent->m_vertices.at(m_edges.at(
index).from) < m_parent->m_vertices.at(m_edges.at(
i).from))
1989 int j = m_edges.at(
i).previous;
1992 m_parent->m_vertices.at((
quint32)m_edges.at(
j).from), m_parent->m_vertices.at((
quint32)m_edges.at(
i).to));
1995 fillPriorityQueue();
2001 while (!m_upperVertex.isEmpty()) {
2002 i = m_upperVertex.last();
2004 m_upperVertex.pop_back();
2005 j = m_edges.at(
i).previous;
2010 switch (m_edges.at(
i).type) {
2013 if (m_edges.at(
i).pointingUp == m_clockwiseOrder) {
2014 if (m_edges.at(
i).node) {
2016 if (m_edges.at(m_edges.at(
i).helper).type == MergeVertex)
2017 diagonals.add(QPair<int, int>(
i, m_edges.at(
i).helper));
2018 m_edges.at(
j).node = m_edges.at(
i).node;
2019 m_edges.at(
i).node =
nullptr;
2020 m_edges.at(
j).node->data =
j;
2021 m_edges.at(
j).helper =
i;
2022 }
else if (m_edges.at(
j).node) {
2024 if (m_edges.at(m_edges.at(
j).helper).type == MergeVertex)
2025 diagonals.add(QPair<int, int>(
i, m_edges.at(
j).helper));
2026 m_edges.at(
i).node = m_edges.at(
j).node;
2027 m_edges.at(
j).node =
nullptr;
2028 m_edges.at(
i).node->data =
i;
2029 m_edges.at(
i).helper =
i;
2031 qWarning(
"Inconsistent polygon. (#1)");
2034 leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(
i).from);
2036 if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex)
2037 diagonals.add(QPair<int, int>(
i, m_edges.at(leftEdgeNode->data).helper));
2038 m_edges.at(leftEdgeNode->data).helper =
i;
2040 qWarning(
"Inconsistent polygon. (#2)");
2045 leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(
i).from);
2047 diagonals.add(QPair<int, int>(
i, m_edges.at(leftEdgeNode->data).helper));
2048 m_edges.at(leftEdgeNode->data).helper =
i;
2050 qWarning(
"Inconsistent polygon. (#3)");
2054 if (m_clockwiseOrder) {
2055 leftEdgeNode = searchEdgeLeftOfEdge(
j);
2058 m_edges.at(
j).node = node;
2059 m_edges.at(
j).helper =
i;
2060 m_edgeList.attachAfter(leftEdgeNode, node);
2063 leftEdgeNode = searchEdgeLeftOfEdge(
i);
2066 m_edges.at(
i).node = node;
2067 m_edges.at(
i).helper =
i;
2068 m_edgeList.attachAfter(leftEdgeNode, node);
2073 leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(
i).from);
2075 if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex)
2076 diagonals.add(QPair<int, int>(
i, m_edges.at(leftEdgeNode->data).helper));
2077 m_edges.at(leftEdgeNode->data).helper =
i;
2079 qWarning(
"Inconsistent polygon. (#4)");
2083 if (m_clockwiseOrder) {
2084 if (m_edges.at(m_edges.at(
i).helper).type == MergeVertex)
2085 diagonals.add(QPair<int, int>(
i, m_edges.at(
i).helper));
2086 if (m_edges.at(
i).node) {
2087 m_edgeList.deleteNode(m_edges.at(
i).node);
2090 qWarning(
"Inconsistent polygon. (#5)");
2093 if (m_edges.at(m_edges.at(
j).helper).type == MergeVertex)
2094 diagonals.add(QPair<int, int>(
i, m_edges.at(
j).helper));
2095 if (m_edges.at(
j).node) {
2096 m_edgeList.deleteNode(m_edges.at(
j).node);
2099 qWarning(
"Inconsistent polygon. (#6)");
2106 for (
int i = 0;
i < diagonals.size(); ++
i)
2107 createDiagonal(diagonals.at(
i).first, diagonals.at(
i).second);
2110template <
typename T>
2113 if (m_parent->m_edges.at(
i).from == m_parent->m_edges.at(
j).from)
2114 return m_parent->m_edges.at(
i).type > m_parent->m_edges.at(
j).type;
2115 return m_parent->m_parent->m_vertices.
at(m_parent->m_edges.at(
i).from) >
2116 m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(
j).from);
2122template <
typename T>
2126 QDataBuffer<int> stack(m_parent->m_indices.size());
2129 while (m_first + 3 <= m_parent->m_indices.size()) {
2131 while (m_parent->m_indices.at(m_first + m_length) != T(-1)) {
2133 Q_ASSERT(m_first + m_length < m_parent->m_indices.size());
2136 m_first += m_length + 1;
2141 while (less(
next(minimum), minimum))
2142 minimum =
next(minimum);
2143 while (less(previous(minimum), minimum))
2144 minimum = previous(minimum);
2148 int left = previous(minimum);
2150 bool stackIsOnLeftSide;
2151 bool clockwiseOrder = leftOfEdge(minimum,
left,
right);
2156 stackIsOnLeftSide =
true;
2160 stackIsOnLeftSide =
false;
2167 if (stackIsOnLeftSide ==
false) {
2168 for (
int i = 0;
i + 1 < stack.size(); ++
i) {
2173 stack.first() = stack.last();
2176 while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(
left, stack.at(stack.size() - 2), stack.last()))) {
2185 stackIsOnLeftSide =
true;
2187 if (stackIsOnLeftSide ==
true) {
2188 for (
int i = 0;
i + 1 < stack.size(); ++
i) {
2193 stack.first() = stack.last();
2196 while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(
right, stack.last(), stack.at(stack.size() - 2)))) {
2205 stackIsOnLeftSide =
false;
2209 m_first += m_length + 1;
2211 m_parent->m_indices =
result;
2220 bool allowUintIndices)
2223 if (allowUintIndices) {
2224 QTriangulator<quint32> triangulator;
2226 QVertexSet<quint32> vertexSet = triangulator.triangulate();
2227 triangleSet.
vertices = vertexSet.vertices;
2228 triangleSet.indices.setDataUint(vertexSet.indices);
2231 QTriangulator<quint16> triangulator;
2233 QVertexSet<quint16> vertexSet = triangulator.triangulate();
2234 triangleSet.vertices = vertexSet.vertices;
2235 triangleSet.indices.setDataUshort(vertexSet.indices);
2247 if (allowUintIndices) {
2248 QTriangulator<quint32> triangulator;
2250 QVertexSet<quint32> vertexSet = triangulator.triangulate();
2251 triangleSet.
vertices = vertexSet.vertices;
2252 triangleSet.indices.setDataUint(vertexSet.indices);
2254 QTriangulator<quint16> triangulator;
2256 QVertexSet<quint16> vertexSet = triangulator.triangulate();
2257 triangleSet.vertices = vertexSet.vertices;
2258 triangleSet.indices.setDataUshort(vertexSet.indices);
2267 if (allowUintIndices) {
2268 QTriangulator<quint32> triangulator;
2270 QVertexSet<quint32> vertexSet = triangulator.triangulate();
2271 triangleSet.
vertices = vertexSet.vertices;
2272 triangleSet.indices.setDataUint(vertexSet.indices);
2274 QTriangulator<quint16> triangulator;
2276 QVertexSet<quint16> vertexSet = triangulator.triangulate();
2277 triangleSet.vertices = vertexSet.vertices;
2278 triangleSet.indices.setDataUshort(vertexSet.indices);
2287 if (allowUintIndices) {
2288 QTriangulator<quint32> triangulator;
2290 QVertexSet<quint32> vertexSet = triangulator.polyline();
2291 polyLineSet.
vertices = vertexSet.vertices;
2292 polyLineSet.indices.setDataUint(vertexSet.indices);
2294 QTriangulator<quint16> triangulator;
2296 QVertexSet<quint16> vertexSet = triangulator.polyline();
2297 polyLineSet.vertices = vertexSet.vertices;
2298 polyLineSet.indices.setDataUshort(vertexSet.indices);
2307 if (allowUintIndices) {
2308 QTriangulator<quint32> triangulator;
2310 QVertexSet<quint32> vertexSet = triangulator.polyline();
2311 polyLineSet.
vertices = vertexSet.vertices;
2312 polyLineSet.indices.setDataUint(vertexSet.indices);
2314 QTriangulator<quint16> triangulator;
2316 QVertexSet<quint16> vertexSet = triangulator.polyline();
2317 polyLineSet.vertices = vertexSet.vertices;
2318 polyLineSet.indices.setDataUshort(vertexSet.indices);
2325#undef Q_FIXED_POINT_SCALE