44 #include <QtGui/qdialog.h> 45 #include <QtGui/qevent.h> 46 #include <QtGui/qpainter.h> 47 #include <QtGui/qpainterpath.h> 48 #include <QtGui/private/qbezier_p.h> 49 #include <QtGui/private/qdatabuffer_p.h> 50 #include <QtCore/qbitarray.h> 51 #include <QtCore/qvarlengtharray.h> 52 #include <QtCore/qqueue.h> 53 #include <QtCore/qglobal.h> 54 #include <QtCore/qpoint.h> 55 #include <QtCore/qalgorithms.h> 60 #include <private/qgl_p.h> 66 #define Q_FIXED_POINT_SCALE 32 69 template <
class T,
class LessThan>
70 #ifdef Q_CC_RVCT // RVCT 2.2 doesn't see recursive _static_ template function 77 const int INSERTION_SORT_LIMIT = 7;
78 if (count <= INSERTION_SORT_LIMIT) {
79 for (
int i = 1; i < count; ++i) {
82 while (j > 0 &&
lessThan(temp, array[j - 1])) {
83 array[j] = array[j - 1];
94 if (
lessThan(array[mid], array[low]))
95 qSwap(array[mid], array[low]);
96 if (
lessThan(array[high], array[mid]))
97 qSwap(array[high], array[mid]);
98 if (
lessThan(array[mid], array[low]))
99 qSwap(array[mid], array[low]);
103 qSwap(array[mid], array[high]);
107 while (low <= high) {
108 while (!
lessThan(array[pivot], array[low])) {
113 while (!
lessThan(array[high], array[pivot])) {
118 qSwap(array[low], array[high]);
124 qSwap(array[pivot], array[low]);
125 sort(array, low, lessThan);
126 sort(array + low + 1, count - low - 1, lessThan);
132 void sort(T *array,
int count)
134 static void sort(T *array,
int count)
138 const int INSERTION_SORT_LIMIT = 25;
139 if (count <= INSERTION_SORT_LIMIT) {
140 for (
int i = 1; i < count; ++i) {
143 while (j > 0 && (temp < array[j - 1])) {
144 array[j] = array[j - 1];
152 int high = count - 1;
155 if ((array[mid] < array[low]))
156 qSwap(array[mid], array[low]);
157 if ((array[high] < array[mid]))
158 qSwap(array[high], array[mid]);
159 if ((array[mid] < array[low]))
160 qSwap(array[mid], array[low]);
164 qSwap(array[mid], array[high]);
168 while (low <= high) {
169 while (!(array[pivot] < array[low])) {
174 while (!(array[high] < array[pivot])) {
179 qSwap(array[low], array[high]);
185 qSwap(array[pivot], array[low]);
187 sort(array + low + 1, count - low - 1);
217 inline bool isValid()
const {
return denominator != 0;}
235 return (a > b) - (a < b);
246 if (b < LIMIT && d < LIMIT)
249 if (a == 0 || c == 0)
255 if (b_div_a != d_div_c)
256 return compare(d_div_c, b_div_a);
337 return qCross(v2 - v1, p - v1);
368 inline bool isValid()
const {
return xOffset.isValid() && yOffset.isValid();}
370 inline bool isAccurate()
const {
return xOffset.numerator == 0 && yOffset.numerator == 0;}
433 if (d1 >= 0 || d2 <= 0 || d3 <= 0 || d4 >= 0)
466 if (2 * xOffset.numerator >= xOffset.denominator)
468 if (2 * yOffset.numerator >= yOffset.denominator)
478 return yOffset < other.
yOffset;
481 return xOffset < other.
xOffset;
495 bool isHorizontal = p.
y == 0 && yOffset.numerator == 0;
496 bool isVertical = p.
x == 0 && xOffset.numerator == 0;
497 if (isHorizontal && isVertical)
510 if (((q.
x < 0) == (q.
y < 0)) != ((p.
x < 0) == (p.
y < 0)))
516 nx =
quint64(-p.
x) * xOffset.denominator - xOffset.numerator;
518 nx =
quint64(p.
x) * xOffset.denominator + xOffset.numerator;
520 ny =
quint64(-p.
y) * yOffset.denominator - yOffset.numerator;
522 ny =
quint64(p.
y) * yOffset.denominator + yOffset.numerator;
536 inline int size()
const {
return m_data.size();}
537 inline bool empty()
const {
return m_data.isEmpty();}
538 inline bool isEmpty()
const {
return m_data.isEmpty();}
539 void push(
const T &x);
541 inline const T &
top()
const {
return m_data.first();}
543 static inline int parent(
int i) {
return (i - 1) / 2;}
544 static inline int left(
int i) {
return 2 * i + 1;}
545 static inline int right(
int i) {
return 2 * i + 2;}
553 int current = m_data.size();
556 while (current != 0 && m_data.at(parent) < x) {
557 m_data.at(current) = m_data.at(parent);
561 m_data.at(current) = x;
567 T result = m_data.first();
568 T back = m_data.last();
570 if (!m_data.isEmpty()) {
575 if (left >= m_data.size())
578 if (right < m_data.size() && m_data.at(left) < m_data.at(right))
580 if (m_data.at(greater) < back)
582 m_data.at(current) = m_data.at(greater);
585 m_data.at(current) = back;
613 void attachBefore(
Node *parent,
Node *child);
614 void attachAfter(
Node *parent,
Node *child);
616 inline Node *front(
Node *node)
const;
617 inline Node *back(
Node *node)
const;
621 inline void deleteNode(
Node *&node);
622 inline Node *newNode();
627 inline bool validate()
const;
630 void rotateLeft(
Node *node);
631 void rotateRight(
Node *node);
632 void update(
Node *node);
634 inline void attachLeft(
Node *parent,
Node *child);
635 inline void attachRight(
Node *parent,
Node *child);
637 int blackDepth(
Node *top)
const;
638 bool checkRedBlackProperty(
Node *top)
const;
641 void detach(
Node *node);
644 void rebalance(
Node *node);
658 Node *next = freeList->right;
683 Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
685 node->right->parent = node->parent;
694 node->right = ref->left;
696 ref->left->parent = node;
724 Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
726 node->left->parent = node->parent;
728 node->left = ref->right;
730 ref->right->parent = node;
740 Node *parent = node->parent;
753 Node *grandpa = parent->parent;
756 Node *uncle = (parent == grandpa->left ? grandpa->right : grandpa->left);
757 if (uncle && uncle->red) {
769 if (node == parent->right && parent == grandpa->left)
770 rotateLeft(node = parent);
771 else if (node == parent->left && parent == grandpa->right)
772 rotateRight(node = parent);
773 parent = node->parent;
775 if (parent == grandpa->left) {
776 rotateRight(grandpa);
792 parent->left = child;
793 child->parent = parent;
801 parent->right = child;
802 child->parent = parent;
810 update(root = child);
812 attachRight(back(root), child);
813 else if (parent->left)
814 attachRight(back(parent->left), child);
816 attachLeft(parent, child);
823 update(root = child);
825 attachLeft(front(root), child);
826 else if (parent->right)
827 attachLeft(front(parent->right), child);
829 attachRight(parent, child);
836 if (n1->parent == n2) {
837 n1->parent = n2->parent;
839 }
else if (n2->parent == n1) {
840 n2->parent = n1->parent;
843 qSwap(n1->parent, n2->parent);
846 qSwap(n1->left, n2->left);
847 qSwap(n1->right, n2->right);
848 qSwap(n1->red, n2->red);
851 if (n1->parent->left == n2)
852 n1->parent->left = n1;
854 n1->parent->right = n1;
860 if (n2->parent->left == n1)
861 n2->parent->left = n2;
863 n2->parent->right = n2;
869 n1->left->parent = n1;
871 n1->right->parent = n1;
874 n2->left->parent = n2;
876 n2->right->parent = n2;
883 swapNodes(node, front(node->right));
885 Node *child = (node->left ? node->left : node->right);
888 if (child && child->red)
894 Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
897 child->parent = node->parent;
898 node->left = node->right = node->parent = 0;
911 Node *sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
915 sibling->red =
false;
916 node->parent->red =
true;
917 if (node == node->parent->left)
918 rotateLeft(node->parent);
920 rotateRight(node->parent);
921 sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
928 if ((!sibling->left || !sibling->left->red) && (!sibling->right || !sibling->right->red)) {
929 bool parentWasRed = node->parent->red;
931 node->parent->red =
false;
940 if (node == node->parent->left) {
941 if (!sibling->right || !sibling->right->red) {
944 sibling->left->red =
false;
945 rotateRight(sibling);
947 sibling = sibling->parent;
950 sibling->red = node->parent->red;
951 node->parent->red =
false;
954 sibling->right->red =
false;
955 rotateLeft(node->parent);
957 if (!sibling->left || !sibling->left->red) {
960 sibling->right->red =
false;
963 sibling = sibling->parent;
966 sibling->red = node->parent->red;
967 node->parent->red =
false;
970 sibling->left->red =
false;
971 rotateRight(node->parent);
997 return front(node->right);
998 while (node->parent && node == node->parent->right)
1000 return node->parent;
1007 return back(node->left);
1008 while (node->parent && node == node->parent->left)
1009 node = node->parent;
1010 return node->parent;
1018 int leftDepth = blackDepth(top->left);
1019 int rightDepth = blackDepth(top->right);
1020 if (leftDepth != rightDepth)
1032 if (top->left && !checkRedBlackProperty(top->left))
1034 if (top->right && !checkRedBlackProperty(top->right))
1036 return !(top->red && ((top->left && top->left->red) || (top->right && top->right->red)));
1042 return checkRedBlackProperty(root) && blackDepth(root) != -1;
1050 node->right = freeList;
1059 Node *node = freeList;
1060 freeList = freeList->right;
1061 node->parent = node->left = node->right = 0;
1081 left = left->parent;
1085 right = right->parent;
1089 while (!leftAncestors.
empty() && !rightAncestors.
empty() && leftAncestors.
back() == rightAncestors.
back()) {
1094 if (!leftAncestors.
empty())
1095 return (leftAncestors.
back() == leftAncestors.
back()->parent->left ? -1 : 1);
1097 if (!rightAncestors.
empty())
1098 return (rightAncestors.
back() == rightAncestors.
back()->parent->right ? -1 : 1);
1111 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3,
1112 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0
1118 return (1 << numBits) + prime_deltas[numBits];
1125 for (
int i = 0; i < 5; ++i) {
1126 int mid = (high + low) / 2;
1127 if (count >= 1 << mid)
1144 bool contains(
quint64 key)
const;
1145 inline void clear();
1147 bool rehash(
int capacity);
1161 m_array =
new quint64[m_capacity];
1171 int oldCapacity = m_capacity;
1173 m_capacity = capacity;
1174 m_array =
new quint64[m_capacity];
1178 for (
int i = 0; i < oldCapacity; ++i) {
1179 if (oldArray[i] != UNUSED)
1180 insert(oldArray[i]);
1186 m_capacity = oldCapacity;
1194 if (m_count > 3 * m_capacity / 4)
1196 Q_ASSERT_X(m_array,
"QInt64Hash<T>::insert",
"Hash set not allocated.");
1197 int index = int(key % m_capacity);
1198 for (
int i = 0; i < m_capacity; ++i) {
1200 if (index >= m_capacity)
1201 index -= m_capacity;
1202 if (m_array[index] == key)
1204 if (m_array[index] == UNUSED) {
1210 Q_ASSERT_X(0,
"QInt64Hash<T>::insert",
"Hash set full.");
1215 Q_ASSERT_X(m_array,
"QInt64Hash<T>::contains",
"Hash set not allocated.");
1216 int index = int(key % m_capacity);
1217 for (
int i = 0; i < m_capacity; ++i) {
1219 if (index >= m_capacity)
1220 index -= m_capacity;
1221 if (m_array[index] == key)
1223 if (m_array[index] == UNUSED)
1231 Q_ASSERT_X(m_array,
"QInt64Hash<T>::clear",
"Hash set not allocated.");
1232 for (
int i = 0; i < m_capacity; ++i)
1233 m_array[i] = UNUSED;
1246 inline QRingBuffer() : m_array(0), m_head(0), m_size(0), m_capacity(0) { }
1248 bool reallocate(
int capacity);
1249 inline const T &
head()
const {
Q_ASSERT(m_size > 0);
return m_array[m_head];}
1250 inline const T &dequeue();
1251 inline void enqueue(
const T &x);
1263 T *oldArray = m_array;
1264 m_array =
new T[capacity];
1267 if (m_head + m_size > m_capacity) {
1268 memcpy(m_array, oldArray + m_head, (m_capacity - m_head) *
sizeof(T));
1269 memcpy(m_array + (m_capacity - m_head), oldArray, (m_head + m_size - m_capacity) *
sizeof(T));
1271 memcpy(m_array, oldArray + m_head, m_size *
sizeof(T));
1275 m_capacity = capacity;
1291 if (++m_head >= m_capacity)
1292 m_head -= m_capacity;
1294 return m_array[
index];
1300 if (m_size == m_capacity)
1301 reallocate(
qMax(2 * m_capacity, 64));
1302 int index = m_head + m_size;
1303 if (index >= m_capacity)
1304 index -= m_capacity;
1315 template<
typename T>
1329 m_edges(0), m_events(0), m_splits(0) { }
1334 inline int &
upper() {
return pointingUp ? to : from;}
1335 inline int &
lower() {
return pointingUp ? from : to;}
1336 inline int upper()
const {
return pointingUp ? to : from;}
1337 inline int lower()
const {
return pointingUp ? from : to;}
1352 bool operator () (
int i,
int j)
const;
1384 #ifdef Q_TRIANGULATOR_DEBUG 1385 friend class DebugDialog;
1387 class DebugDialog :
public QDialog 1405 bool calculateIntersection(
int left,
int right);
1406 bool edgeIsLeftOfEdge(
int leftEdgeIndex,
int rightEdgeIndex)
const;
1413 void sortEdgeList(
const QPodPoint eventPoint);
1414 void fillPriorityQueue();
1415 void calculateIntersections();
1416 int splitEdge(
int splitIndex);
1417 bool splitEdgesAtIntersections();
1418 void insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges,
int i);
1419 void removeUnwantedEdgesAndConnect();
1420 void removeUnusedPoints();
1431 #ifdef Q_TRIANGULATOR_DEBUG 1432 friend class ComplexToSimple::DebugDialog;
1445 enum VertexType {MergeVertex, EndVertex, RegularVertex, StartVertex, SplitVertex};
1454 int upper()
const {
return (pointingUp ? to : from);}
1455 int lower()
const {
return (pointingUp ? from : to);}
1463 bool operator () (
int i,
int j)
const;
1468 void setupDataStructures();
1469 void removeZeroLengthEdges();
1470 void fillPriorityQueue();
1471 bool edgeIsLeftOfEdge(
int leftEdgeIndex,
int rightEdgeIndex)
const;
1476 void classifyVertex(
int i);
1477 void classifyVertices();
1479 bool pointIsInSector(
int vertex,
int sector);
1480 int findSector(
int edge,
int vertex);
1481 void createDiagonal(
int lower,
int upper);
1482 void monotoneDecomposition();
1501 inline T
indices(
int index)
const {
return m_parent->m_indices.at(index + m_first);}
1502 inline int next(
int index)
const {
return (index + 1) % m_length;}
1503 inline int previous(
int index)
const {
return (index + m_length - 1) % m_length;}
1537 template <
typename T>
1540 for (
int i = 0; i < m_vertices.size(); ++i) {
1560 for (
int i = 0; i < m_vertices.size(); ++i) {
1567 template <
typename T>
1573 for (
int i = 0; i < m_vertices.size(); ++i) {
1580 template <
typename T>
1584 m_vertices.resize(count);
1585 m_indices.resize(count + 1);
1586 for (
int i = 0; i < count; ++i) {
1588 matrix.
map(polygon[2 * i + 0], polygon[2 * i + 1], &x, &y);
1590 m_vertices.at(i).y =
qRound(y * Q_FIXED_POINT_SCALE);
1593 m_indices[count] = T(-1);
1596 template <
typename T>
1599 m_hint = path.
hints();
1606 for (
int i = 0; i < path.
elementCount(); ++i, ++e, p += 2) {
1609 if (!m_indices.isEmpty())
1610 m_indices.push_back(T(-1));
1613 m_indices.push_back(T(m_vertices.size()));
1614 m_vertices.resize(m_vertices.size() + 1);
1616 matrix.
map(p[0], p[1], &x, &y);
1618 m_vertices.last().y =
qRound(y * Q_FIXED_POINT_SCALE);
1623 for (
int i = 0; i < 4; ++i)
1624 matrix.
map(p[2 * i - 2], p[2 * i - 1], &pts[2 * i + 0], &pts[2 * i + 1]);
1625 for (
int i = 0; i < 8; ++i)
1630 for (
int j = 1; j < poly.
size(); ++j) {
1631 m_indices.
push_back(T(m_vertices.size()));
1632 m_vertices.resize(m_vertices.size() + 1);
1633 m_vertices.last().x =
qRound(poly.
at(j).
x() * Q_FIXED_POINT_SCALE / lod);
1634 m_vertices.last().y =
qRound(poly.
at(j).
y() * Q_FIXED_POINT_SCALE / lod);
1642 Q_ASSERT_X(0,
"QTriangulator::triangulate",
"Unexpected element type.");
1647 for (
int i = 0; i < path.
elementCount(); ++i, p += 2) {
1648 m_indices.push_back(T(m_vertices.size()));
1649 m_vertices.resize(m_vertices.size() + 1);
1651 matrix.
map(p[0], p[1], &x, &y);
1653 m_vertices.last().y =
qRound(y * Q_FIXED_POINT_SCALE);
1656 m_indices.push_back(T(-1));
1659 template <
typename T>
1668 template <
typename T>
1671 m_initialPointCount = m_parent->m_vertices.size();
1674 calculateIntersections();
1675 }
while (splitEdgesAtIntersections());
1677 removeUnwantedEdgesAndConnect();
1678 removeUnusedPoints();
1680 m_parent->m_indices.clear();
1681 QBitArray processed(m_edges.size(),
false);
1682 for (
int first = 0; first < m_edges.size(); ++first) {
1684 if (processed.at(first) || m_edges.at(first).next == -1)
1690 Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i);
1691 m_parent->m_indices.push_back(m_edges.at(i).from);
1692 processed.setBit(i);
1693 i = m_edges.at(i).next;
1694 }
while (i != first);
1695 m_parent->m_indices.push_back(T(-1));
1699 template <
typename T>
1705 for (
int i = 0; i < m_parent->m_indices.size(); ++i) {
1706 if (m_parent->m_indices.at(i) == T(-1)) {
1707 if (m_edges.size() != first)
1708 m_edges.last().to = m_edges.at(first).from;
1709 first = m_edges.size();
1711 Q_ASSERT(i + 1 < m_parent->m_indices.size());
1713 Edge edge = {0, int(m_parent->m_indices.at(i)),
int(m_parent->m_indices.at(i + 1)), -1, -1, 0,
true,
false,
false};
1717 if (first != m_edges.size())
1718 m_edges.last().
to = m_edges.at(first).from;
1719 for (
int i = 0; i < m_edges.size(); ++i) {
1720 m_edges.at(i).originallyPointingUp = m_edges.at(i).pointingUp =
1721 m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from);
1726 template <
typename T>
1729 const Edge &e1 = m_edges.at(left);
1730 const Edge &e2 = m_edges.at(right);
1740 if (m_processedEdgePairs.contains(key))
1742 m_processedEdgePairs.insert(key);
1755 intersection.
vertex = m_parent->m_vertices.size();
1756 m_topIntersection.push(intersection);
1761 template <
typename T>
1764 const Edge &leftEdge = m_edges.at(leftEdgeIndex);
1765 const Edge &rightEdge = m_edges.at(rightEdgeIndex);
1768 const QPodPoint &upper = m_parent->m_vertices.at(leftEdge.
upper());
1780 template <
typename T>
1786 if (edgeIsLeftOfEdge(edgeIndex, current->data)) {
1787 current = current->left;
1790 current = current->right;
1796 template <
typename T>
1799 if (!m_edgeList.root)
1804 if (edgeIsLeftOfEdge(edgeIndex, current->data))
1807 current = m_edgeList.
next(current);
1812 template <
typename T>
1818 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
1819 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
1825 current = (d < 0 ? current->left : current->right);
1830 current = result.
first->left;
1832 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
1833 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
1837 result.
first = current;
1838 current = current->left;
1840 current = current->right;
1844 current = result.
second->right;
1846 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
1847 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
1852 current = current->right;
1854 current = current->left;
1861 template <
typename T>
1868 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
1869 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
1875 current = current->left;
1877 result.
first = current;
1878 current = current->right;
1887 current = mid->left;
1889 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
1890 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
1894 current = current->left;
1896 result.
first = current;
1897 current = current->right;
1901 current = mid->right;
1903 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
1904 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
1908 current = current->right;
1911 current = current->left;
1918 template <
typename T>
1925 const QPodPoint &
u = m_parent->m_vertices.at(m_edges.at(leftmost->data).from);
1926 const QPodPoint &v = m_parent->m_vertices.at(m_edges.at(leftmost->data).to);
1930 m_splits.add(split);
1931 if (leftmost == rightmost)
1933 leftmost = m_edgeList.
next(leftmost);
1937 template <
typename T>
1946 while (leftmost != rightmost) {
1947 Edge &
left = m_edges.at(leftmost->data);
1948 Edge &
right = m_edges.at(rightmost->data);
1950 qSwap(leftmost->data, rightmost->data);
1951 leftmost = m_edgeList.
next(leftmost);
1952 if (leftmost == rightmost)
1954 rightmost = m_edgeList.
previous(rightmost);
1957 rightmost = m_edgeList.
next(storeRightmost);
1958 leftmost = m_edgeList.
previous(storeLeftmost);
1960 calculateIntersection(leftmost->data, storeLeftmost->data);
1962 calculateIntersection(storeRightmost->data, rightmost->data);
1965 template <
typename T>
1969 while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint < eventPoint2) {
1973 int currentVertex = intersection.
vertex;
1982 const Edge &edge = m_edges.at(previous->data);
1985 if (!currentIntersectionPoint.
isOnLine(u, v)) {
1989 leftmost = previous;
1996 const Edge &edge = m_edges.at(next->data);
1999 if (!currentIntersectionPoint.
isOnLine(u, v)) {
2007 splitEdgeListRange(leftmost, rightmost, currentVertex, currentIntersectionPoint);
2008 reorderEdgeListRange(leftmost, rightmost);
2010 while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= currentIntersectionPoint)
2011 m_topIntersection.pop();
2013 #ifdef Q_TRIANGULATOR_DEBUG 2014 DebugDialog dialog(
this, intersection.
vertex);
2021 template <
typename T>
2025 m_events.reserve(m_edges.size() * 2);
2026 for (
int i = 0; i < m_edges.size(); ++i) {
2027 Q_ASSERT(m_edges.at(i).previous == -1 && m_edges.at(i).next == -1);
2029 Q_ASSERT(m_edges.at(i).pointingUp == m_edges.at(i).originallyPointingUp);
2030 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)));
2032 if (m_parent->m_vertices.at(m_edges.at(i).to) != m_parent->m_vertices.at(m_edges.at(i).from)) {
2033 QPodPoint upper = m_parent->m_vertices.at(m_edges.at(i).upper());
2034 QPodPoint lower = m_parent->m_vertices.at(m_edges.at(i).lower());
2035 Event upperEvent = {{upper.
x, upper.
y}, Event::Upper, i};
2036 Event lowerEvent = {{lower.
x, lower.
y}, Event::Lower, i};
2037 m_events.add(upperEvent);
2038 m_events.add(lowerEvent);
2042 sort(m_events.data(), m_events.size());
2045 template <
typename T>
2048 fillPriorityQueue();
2050 Q_ASSERT(m_topIntersection.empty());
2054 while (!m_events.isEmpty()) {
2055 Event event = m_events.last();
2056 sortEdgeList(
event.point);
2061 int vertex = (
event.type == Event::Upper ? m_edges.at(
event.edge).upper() : m_edges.at(
event.edge).lower());
2064 if (range.
first != 0) {
2065 splitEdgeListRange(range.
first, range.
second, vertex, eventPoint);
2070 while (!m_events.isEmpty() && m_events.last().point ==
event.point) {
2071 event = m_events.last();
2072 m_events.pop_back();
2075 if (m_edges.at(i).node) {
2080 m_edgeList.deleteNode(m_edges.at(i).node);
2081 if (!left || !right)
2083 calculateIntersection(left->data, right->data);
2088 m_edgeList.attachAfter(left, m_edges.at(i).node = m_edgeList.
newNode());
2089 m_edges.at(i).node->data = i;
2092 calculateIntersection(left->data, i);
2094 calculateIntersection(i, right->data);
2097 while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= eventPoint)
2098 m_topIntersection.pop();
2099 #ifdef Q_TRIANGULATOR_DEBUG 2100 DebugDialog dialog(
this, vertex);
2104 m_processedEdgePairs.clear();
2111 template <
typename T>
2114 const Split &
split = m_splits.at(splitIndex);
2115 Edge &lowerEdge = m_edges.at(split.
edge);
2122 return lowerEdge.
next;
2128 Edge upperEdge = lowerEdge;
2133 m_edges.add(upperEdge);
2134 return m_edges.size() - 1;
2137 m_edges.add(upperEdge);
2142 template <
typename T>
2145 for (
int i = 0; i < m_edges.size(); ++i)
2146 m_edges.at(i).mayIntersect =
false;
2147 bool checkForNewIntersections =
false;
2148 for (
int i = 0; i < m_splits.size(); ++i) {
2150 checkForNewIntersections |= !m_splits.at(i).accurate;
2152 for (
int i = 0; i < m_edges.size(); ++i) {
2153 m_edges.at(i).originallyPointingUp = m_edges.at(i).pointingUp =
2154 m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from);
2157 return checkForNewIntersections;
2160 template <
typename T>
2164 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(i).from) != m_parent->m_vertices.at(m_edges.at(i).to));
2167 int windingNumber = m_edges.at(i).winding;
2168 if (m_edges.at(i).originallyPointingUp)
2178 if (!orderedEdges.
isEmpty()) {
2179 int j = orderedEdges[orderedEdges.
size() - 1];
2181 if (m_edges.at(j).next == -1 && m_edges.at(j).previous == -1
2182 && (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(j).to))
2183 && (m_parent->m_vertices.at(m_edges.at(i).to) == m_parent->m_vertices.at(m_edges.at(j).from))) {
2191 template <
typename T>
2196 fillPriorityQueue();
2200 while (!m_events.isEmpty()) {
2201 Event event = m_events.last();
2202 int edgeIndex =
event.
edge;
2211 orderedEdges.
clear();
2213 if (m_edgeList.root) {
2216 while (current != b.
second) {
2218 Q_ASSERT(m_edges.at(current->data).node == current);
2220 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);
2221 insertEdgeIntoVectorIfWanted(orderedEdges, current->data);
2222 current = m_edgeList.
next(current);
2228 event = m_events.last();
2229 m_events.pop_back();
2230 edgeIndex =
event.edge;
2233 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(edgeIndex).from) != m_parent->m_vertices.at(m_edges.at(edgeIndex).to));
2235 if (m_edges.at(edgeIndex).node) {
2238 m_edgeList.deleteNode(m_edges.at(edgeIndex).node);
2243 m_edgeList.attachAfter(left, m_edges.at(edgeIndex).node = m_edgeList.
newNode());
2244 m_edges.at(edgeIndex).node->data = edgeIndex;
2246 }
while (!m_events.isEmpty() && m_events.last().point ==
event.point);
2248 if (m_edgeList.root) {
2252 int currentWindingNumber = (b.
first ? m_edges.at(b.
first->data).winding : 0);
2253 while (current != b.
second) {
2256 int i = current->data;
2257 Q_ASSERT(m_edges.at(i).node == current);
2260 int ccwWindingNumber = m_edges.at(i).winding = currentWindingNumber;
2261 if (m_edges.at(i).originallyPointingUp) {
2262 --m_edges.at(i).winding;
2264 ++m_edges.at(i).winding;
2267 currentWindingNumber = m_edges.at(i).winding;
2270 if ((ccwWindingNumber & 1) == 0) {
2271 Q_ASSERT(m_edges.at(i).previous == -1 && m_edges.at(i).next == -1);
2272 qSwap(m_edges.at(i).from, m_edges.at(i).to);
2273 m_edges.at(i).pointingUp = !m_edges.at(i).pointingUp;
2276 current = m_edgeList.
next(current);
2280 current = (b.
second ? m_edgeList.previous(b.
second) : m_edgeList.back(m_edgeList.root));
2281 while (current != b.
first) {
2283 Q_ASSERT(m_edges.at(current->data).node == current);
2284 insertEdgeIntoVectorIfWanted(orderedEdges, current->data);
2285 current = m_edgeList.
previous(current);
2296 if (m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).from) ==
event.point) {
2298 int copy = orderedEdges[0];
2299 orderedEdges.
append(copy);
2301 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).to) ==
event.point);
2307 for (
int j = i; j < orderedEdges.
size(); j += 2) {
2309 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[j]).to) ==
event.point);
2310 Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[j + 1]).from) ==
event.point);
2311 if (m_edges.at(orderedEdges[j]).to < pointIndex)
2312 pointIndex = m_edges.at(orderedEdges[j]).to;
2313 if (m_edges.at(orderedEdges[j + 1]).from < pointIndex)
2314 pointIndex = m_edges.at(orderedEdges[j + 1]).from;
2317 for (; i < orderedEdges.
size(); i += 2) {
2319 m_edges.at(orderedEdges[i]).to = m_edges.at(orderedEdges[i + 1]).from = pointIndex;
2321 Q_ASSERT(m_edges.at(orderedEdges[i]).pointingUp || m_edges.at(orderedEdges[i]).previous != -1);
2322 Q_ASSERT(!m_edges.at(orderedEdges[i + 1]).pointingUp || m_edges.at(orderedEdges[i + 1]).next != -1);
2324 m_edges.at(orderedEdges[i]).next = orderedEdges[i + 1];
2325 m_edges.
at(orderedEdges[i + 1]).previous = orderedEdges[i];
2330 template <
typename T>
2332 QBitArray used(m_parent->m_vertices.size(),
false);
2333 for (
int i = 0; i < m_edges.size(); ++i) {
2334 Q_ASSERT((m_edges.at(i).previous == -1) == (m_edges.at(i).next == -1));
2335 if (m_edges.at(i).next != -1)
2336 used.setBit(m_edges.at(i).from);
2339 newMapping.
resize(m_parent->m_vertices.size());
2341 for (
int i = 0; i < m_parent->m_vertices.size(); ++i) {
2343 m_parent->m_vertices.at(count) = m_parent->m_vertices.at(i);
2344 newMapping.at(i) = count;
2348 m_parent->m_vertices.resize(count);
2349 for (
int i = 0; i < m_edges.size(); ++i) {
2350 m_edges.at(i).from = newMapping.at(m_edges.at(i).from);
2351 m_edges.at(i).to = newMapping.at(m_edges.at(i).to);
2355 template <
typename T>
2358 int cmp =
comparePoints(m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).from),
2359 m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).from));
2361 cmp =
comparePoints(m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).to),
2362 m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).to));
2367 template <
typename T>
2370 if (point == other.
point)
2372 return other.
point < point;
2379 #ifdef Q_TRIANGULATOR_DEBUG 2380 template <
typename T>
2382 : m_parent(parent), m_vertex(currentVertex)
2388 int minX, maxX, minY, maxY;
2389 minX = maxX = vertices.
at(0).
x;
2390 minY = maxY = vertices.
at(0).
y;
2391 for (
int i = 1; i < vertices.
size(); ++i) {
2392 minX =
qMin(minX, vertices.
at(i).
x);
2393 maxX =
qMax(maxX, vertices.
at(i).
x);
2394 minY =
qMin(minY, vertices.
at(i).
y);
2395 maxY =
qMax(maxY, vertices.
at(i).
y);
2397 int w = maxX - minX;
2398 int h = maxY - minY;
2400 m_window =
QRectF(minX - border, minY - border, (maxX - minX + 2 * border), (maxY - minY + 2 * border));
2403 template <
typename T>
2413 qreal halfPointSize =
qMin(m_window.width(), m_window.height()) / 300.0;
2419 for (
int i = 0; i < edges.
size(); ++i) {
2425 for (
int i = 0; i < vertices.
size(); ++i) {
2433 if (m_parent->m_edgeList.root) {
2436 p.
setPen(colors[count++ % 6]);
2440 current = m_parent->m_edgeList.
next(current);
2450 for (
int i = 0; i < splits.
size(); ++i) {
2457 u.
x *= 2 * halfPointSize / uLen;
2458 u.
y *= 2 * halfPointSize / uLen;
2461 v.
x *= 2 * halfPointSize / vLen;
2462 v.
y *= 2 * halfPointSize / vLen;
2470 template <
typename T>
2476 m_window =
QRectF(center - delta, center + delta);
2481 template <
typename T>
2485 QPointF delta =
event->pos() - m_lastMousePos;
2486 delta.
setX(delta.
x() * m_window.width() / width());
2487 delta.
setY(delta.
y() * m_window.height() / height());
2488 m_window.translate(-delta.
x(), -delta.
y());
2489 m_lastMousePos =
event->pos();
2495 template <
typename T>
2499 m_lastMousePos = event->
pos();
2509 template <
typename T>
2512 setupDataStructures();
2513 removeZeroLengthEdges();
2514 monotoneDecomposition();
2516 m_parent->m_indices.clear();
2517 QBitArray processed(m_edges.size(),
false);
2518 for (
int first = 0; first < m_edges.size(); ++first) {
2519 if (processed.at(first))
2524 Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i);
2525 m_parent->m_indices.push_back(m_edges.at(i).from);
2526 processed.setBit(i);
2527 i = m_edges.at(i).next;
2528 }
while (i != first);
2529 if (m_parent->m_indices.size() > 0 && m_parent->m_indices.back() != T(-1))
2530 m_parent->m_indices.push_back(T(-1));
2534 template <
typename T>
2542 while (i + 3 <= m_parent->m_indices.size()) {
2543 int start = m_edges.size();
2546 e.
from = m_parent->m_indices.at(i);
2547 e.
type = RegularVertex;
2548 e.
next = m_edges.size() + 1;
2552 Q_ASSERT(i < m_parent->m_indices.size());
2553 }
while (m_parent->m_indices.at(i) != T(-1));
2555 m_edges.last().next = start;
2556 m_edges.at(start).previous = m_edges.size() - 1;
2560 for (i = 0; i < m_edges.size(); ++i) {
2561 m_edges.at(i).to = m_edges.at(m_edges.at(i).next).from;
2562 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);
2563 m_edges.at(i).helper = -1;
2567 template <
typename T>
2570 for (
int i = 0; i < m_edges.size(); ++i) {
2571 if (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(i).to)) {
2572 m_edges.at(m_edges.at(i).previous).next = m_edges.at(i).next;
2573 m_edges.at(m_edges.at(i).next).previous = m_edges.at(i).previous;
2574 m_edges.at(m_edges.at(i).next).from = m_edges.at(i).from;
2575 m_edges.at(i).next = -1;
2580 newMapping.
resize(m_edges.size());
2582 for (
int i = 0; i < m_edges.size(); ++i) {
2583 if (m_edges.at(i).next != -1) {
2584 m_edges.at(count) = m_edges.at(i);
2585 newMapping.at(i) = count;
2589 m_edges.resize(count);
2590 for (
int i = 0; i < m_edges.size(); ++i) {
2591 m_edges.at(i).next = newMapping.at(m_edges.at(i).next);
2592 m_edges.at(i).previous = newMapping.at(m_edges.at(i).previous);
2596 template <
typename T>
2599 m_upperVertex.reset();
2600 m_upperVertex.reserve(m_edges.size());
2601 for (
int i = 0; i < m_edges.size(); ++i)
2602 m_upperVertex.add(i);
2605 sort(m_upperVertex.data(), m_upperVertex.size(),
cmp);
2611 template <
typename T>
2614 const Edge &leftEdge = m_edges.at(leftEdgeIndex);
2615 const Edge &rightEdge = m_edges.at(rightEdgeIndex);
2626 template <
typename T>
2632 if (edgeIsLeftOfEdge(edgeIndex, current->data)) {
2633 current = current->left;
2636 current = current->right;
2643 template <
typename T>
2649 const QPodPoint &p1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
2650 const QPodPoint &p2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
2653 current = current->left;
2656 current = current->right;
2662 template <
typename T>
2665 Edge &e2 = m_edges.at(i);
2673 const QPodPoint &p3 = m_parent->m_vertices.at(e2.
to);
2675 Q_ASSERT(d != 0 || (!startOrSplit && !endOrMerge));
2677 e2.
type = RegularVertex;
2679 if (m_clockwiseOrder) {
2681 e2.
type = (d < 0 ? SplitVertex : StartVertex);
2682 else if (endOrMerge)
2683 e2.
type = (d < 0 ? MergeVertex : EndVertex);
2686 e2.
type = (d > 0 ? SplitVertex : StartVertex);
2687 else if (endOrMerge)
2688 e2.
type = (d > 0 ? MergeVertex : EndVertex);
2692 template <
typename T>
2695 for (
int i = 0; i < m_edges.size(); ++i)
2699 template <
typename T>
2706 return leftOfPreviousEdge && leftOfNextEdge;
2708 return leftOfPreviousEdge || leftOfNextEdge;
2711 template <
typename T>
2714 const QPodPoint &
center = m_parent->m_vertices.at(m_edges.at(sector).from);
2716 while (m_parent->m_vertices.at(m_edges.at(vertex).from) == center)
2717 vertex = m_edges.at(vertex).next;
2718 int next = m_edges.at(sector).next;
2719 while (m_parent->m_vertices.at(m_edges.at(next).from) == center)
2720 next = m_edges.at(next).next;
2721 int previous = m_edges.at(sector).previous;
2722 while (m_parent->m_vertices.at(m_edges.at(previous).from) == center)
2723 previous = m_edges.at(previous).previous;
2725 const QPodPoint &p = m_parent->m_vertices.at(m_edges.at(vertex).from);
2726 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(previous).from);
2727 const QPodPoint &v3 = m_parent->m_vertices.at(m_edges.at(next).from);
2728 if (m_clockwiseOrder)
2729 return pointIsInSector(p, v3, center, v1);
2731 return pointIsInSector(p, v1, center, v3);
2734 template <
typename T>
2737 while (!pointIsInSector(vertex, edge)) {
2738 edge = m_edges.at(m_edges.at(edge).previous).twin;
2744 template <
typename T>
2747 lower = findSector(lower, upper);
2748 upper = findSector(upper, lower);
2750 int prevLower = m_edges.at(lower).previous;
2751 int prevUpper = m_edges.at(upper).previous;
2755 e.
twin = m_edges.size() + 1;
2758 e.
from = m_edges.at(lower).from;
2759 e.
to = m_edges.at(upper).from;
2760 m_edges.at(upper).previous = m_edges.at(prevLower).next = int(m_edges.size());
2763 e.
twin = m_edges.size() - 1;
2766 e.
from = m_edges.at(upper).from;
2767 e.
to = m_edges.at(lower).from;
2768 m_edges.at(lower).previous = m_edges.at(prevUpper).next = int(m_edges.size());
2772 template <
typename T>
2775 if (m_edges.isEmpty())
2783 if (m_parent->m_vertices.at(m_edges.at(
index).from) < m_parent->m_vertices.at(m_edges.at(i).from))
2787 int j = m_edges.at(i).previous;
2790 m_parent->m_vertices.at((
quint32)m_edges.at(j).from), m_parent->m_vertices.at((
quint32)m_edges.at(i).to));
2793 fillPriorityQueue();
2799 while (!m_upperVertex.isEmpty()) {
2800 i = m_upperVertex.
last();
2802 m_upperVertex.pop_back();
2803 j = m_edges.at(i).previous;
2808 switch (m_edges.at(i).type) {
2811 if (m_edges.at(i).pointingUp == m_clockwiseOrder) {
2812 if (m_edges.at(i).node) {
2814 if (m_edges.at(m_edges.at(i).helper).
type == MergeVertex)
2816 m_edges.at(j).node = m_edges.at(i).node;
2817 m_edges.at(i).node = 0;
2818 m_edges.at(j).node->data = j;
2819 m_edges.at(j).helper = i;
2820 }
else if (m_edges.at(j).node) {
2822 if (m_edges.at(m_edges.at(j).helper).
type == MergeVertex)
2824 m_edges.at(i).node = m_edges.at(j).node;
2825 m_edges.at(j).node = 0;
2826 m_edges.at(i).node->data = i;
2827 m_edges.
at(i).helper = i;
2829 qWarning(
"Inconsistent polygon. (#1)");
2832 leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
2834 if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).
type == MergeVertex)
2836 m_edges.at(leftEdgeNode->data).helper = i;
2838 qWarning(
"Inconsistent polygon. (#2)");
2843 leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
2846 m_edges.at(leftEdgeNode->data).helper = i;
2848 qWarning(
"Inconsistent polygon. (#3)");
2852 if (m_clockwiseOrder) {
2853 leftEdgeNode = searchEdgeLeftOfEdge(j);
2856 m_edges.at(j).node = node;
2857 m_edges.at(j).helper = i;
2858 m_edgeList.attachAfter(leftEdgeNode, node);
2861 leftEdgeNode = searchEdgeLeftOfEdge(i);
2864 m_edges.
at(i).node = node;
2865 m_edges.at(i).helper = i;
2866 m_edgeList.attachAfter(leftEdgeNode, node);
2871 leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
2873 if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).
type == MergeVertex)
2875 m_edges.at(leftEdgeNode->data).helper = i;
2877 qWarning(
"Inconsistent polygon. (#4)");
2881 if (m_clockwiseOrder) {
2882 if (m_edges.at(m_edges.at(i).helper).
type == MergeVertex)
2884 if (m_edges.at(i).node) {
2885 m_edgeList.deleteNode(m_edges.at(i).node);
2888 qWarning(
"Inconsistent polygon. (#5)");
2891 if (m_edges.at(m_edges.at(j).helper).
type == MergeVertex)
2893 if (m_edges.at(j).node) {
2894 m_edgeList.deleteNode(m_edges.at(j).node);
2897 qWarning(
"Inconsistent polygon. (#6)");
2904 for (
int i = 0; i < diagonals.
size(); ++i)
2905 createDiagonal(diagonals.at(i).first, diagonals.at(i).second);
2908 template <
typename T>
2911 if (m_parent->m_edges.at(i).from == m_parent->m_edges.at(j).from)
2912 return m_parent->m_edges.at(i).type > m_parent->m_edges.at(j).type;
2913 return m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).from) >
2914 m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).from);
2920 template <
typename T>
2927 while (m_first + 3 <= m_parent->m_indices.
size()) {
2929 while (m_parent->m_indices.at(m_first + m_length) != T(-1)) {
2931 Q_ASSERT(m_first + m_length < m_parent->m_indices.
size());
2934 m_first += m_length + 1;
2939 while (less(next(minimum), minimum))
2940 minimum = next(minimum);
2941 while (less(previous(minimum), minimum))
2942 minimum = previous(minimum);
2946 int left = previous(minimum);
2947 int right = next(minimum);
2948 bool stackIsOnLeftSide;
2949 bool clockwiseOrder = leftOfEdge(minimum, left, right);
2951 if (less(left, right)) {
2953 left = previous(left);
2954 stackIsOnLeftSide =
true;
2957 right = next(right);
2958 stackIsOnLeftSide =
false;
2961 for (
int count = 0; count + 2 < m_length; ++count)
2964 if (less(left, right)) {
2965 if (stackIsOnLeftSide ==
false) {
2966 for (
int i = 0; i + 1 < stack.size(); ++i) {
2971 stack.first() = stack.last();
2974 while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(left, stack.at(stack.size() - 2), stack.last()))) {
2982 left = previous(left);
2983 stackIsOnLeftSide =
true;
2985 if (stackIsOnLeftSide ==
true) {
2986 for (
int i = 0; i + 1 < stack.size(); ++i) {
2991 stack.first() = stack.last();
2994 while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(right, stack.last(), stack.at(stack.size() - 2)))) {
3002 right = next(right);
3003 stackIsOnLeftSide =
false;
3007 m_first += m_length + 1;
3009 m_parent->m_indices = result;
3022 triangulator.
initialize(polygon, count, hint, matrix);
3029 triangulator.
initialize(polygon, count, hint, matrix);
The QPainter class performs low-level painting on widgets and other paint devices.
bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const
ElementType
This enum describes the types of elements used to connect vertices in subpaths.
void attachLeft(Node *parent, Node *child)
void monotoneDecomposition()
static const uchar prime_deltas[]
CompareEdges(ComplexToSimple *parent)
timeval operator-(const timeval &t1, const timeval &t2)
bool leftOfEdge(int i, int j, int k) const
static qint64 qCross(const QPodPoint &u, const QPodPoint &v)
Q_DECL_CONSTEXPR const T & qMin(const T &a, const T &b)
#define QT_END_NAMESPACE
This macro expands to.
Node * previous(Node *node) const
static const quint64 UNUSED
QVertexSet< T > triangulate()
QVertexIndexVector indices
void setDataUint(const QVector< quint32 > &data)
QDataBuffer< Edge > m_edges
T indices(int index) const
bool operator>(const QByteArray &a1, const QByteArray &a2)
bool less(int i, int j) const
The QDialog class is the base class of dialog windows.
The QPainterPath class provides a container for painting operations, enabling graphical shapes to be ...
QDataBuffer< Event > m_events
The QWheelEvent class contains parameters that describe a wheel event.
QRBTree< int >::Node * searchEdgeLeftOfEdge(int edgeIndex) const
QRBTree< int >::Node * QRBTreeIntNodePointer
int findSector(int edge, int vertex)
void setY(qreal y)
Sets the y coordinate of this point to the given y coordinate.
QRBTree< int >::Node * searchEdgeLeftOf(int edgeIndex) const
The QPointF class defines a point in the plane using floating point precision.
Node * next(Node *node) const
QVector< qreal > vertices
bool contains(quint64 key) const
#define Q_FIXED_POINT_SCALE
static void clear(QVariant::Private *d)
QVertexIndexVector indices
bool splitEdgesAtIntersections()
long ASN1_INTEGER_get ASN1_INTEGER * a
bool operator!=(QBool b1, bool b2)
const QVectorPath & qtVectorPathForPath(const QPainterPath &path)
void drawLine(const QLineF &line)
Draws a line defined by line.
static quint64 gcd(quint64 x, quint64 y)
ComplexToSimple * m_parent
void setDataUshort(const QVector< quint16 > &data)
QInt64Set(int capacity=64)
void attachRight(Node *parent, Node *child)
Q_DECL_CONSTEXPR T qAbs(const T &t)
static qint64 qPointDistanceFromLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
bool empty() const
This function is provided for STL compatibility.
void splitEdgeListRange(QRBTree< int >::Node *leftmost, QRBTree< int >::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint)
int next(int index) const
bool operator<(int priority, const QPair< QRunnable *, int > &p)
const QPainterPath::ElementType * elements() const
QRBTree< int >::Node * searchEdgeLeftOfPoint(int pointIndex) const
QVertexSet< T > polyline()
QPair< QRBTree< int >::Node *, QRBTree< int >::Node * > bounds(const QPodPoint &point) const
QDataBuffer< Edge > m_edges
Q_CORE_EXPORT QTextStream & right(QTextStream &s)
bool isOnLine(const QPodPoint &u, const QPodPoint &v) const
static int primeForCount(int count)
static QIntersectionPoint qIntersectionPoint(const QPodPoint &point)
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
bool operator<=(const QByteArray &a1, const QByteArray &a2)
const QPoint & pos() const
Returns the position of the mouse cursor, relative to the widget that received the event...
qreal x() const
Returns the x-coordinate of this point.
void resize(int size)
Sets the size of the vector to size.
QInt64Set m_processedEdgePairs
void pop_back()
This function is provided for STL compatibility.
MonotoneToTriangles(QTriangulator< T > *parent)
QTextStream & center(QTextStream &stream)
Calls QTextStream::setFieldAlignment(QTextStream::AlignCenter) on stream and returns stream...
static QBezier fromPoints(const QPointF &p1, const QPointF &p2, const QPointF &p3, const QPointF &p4)
CompareVertices(SimpleToMonotone *parent)
void setRenderHint(RenderHint hint, bool on=true)
Sets the given render hint on the painter if on is true; otherwise clears the render hint...
#define QT_BEGIN_NAMESPACE
This macro expands to.
The QRectF class defines a rectangle in the plane using floating point precision. ...
SimpleToMonotone(QTriangulator< T > *parent)
static bool lessThan(const QChar *a, int l, const char *c)
QVector< qreal > vertices
static void sort(T *array, int count, LessThan lessThan)
QVarLengthArray< int, 6 > ShortArray
void insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i)
void calculateIntersections()
QRBTree< int >::Node * node
#define QT_PREPEND_NAMESPACE(name)
This macro qualifies identifier with the full namespace.
The QPolygonF class provides a vector of points using floating point precision.
void reorderEdgeListRange(QRBTree< int >::Node *leftmost, QRBTree< int >::Node *rightmost)
Q_CORE_EXPORT void qWarning(const char *,...)
static int comparePoints(const QPodPoint &u, const QPodPoint &v)
int blackDepth(Node *top) const
int delta() const
Returns the distance that the wheel is rotated, in eighths of a degree.
bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const
ComplexToSimple(QTriangulator< T > *parent)
QRBTree< int > m_edgeList
static void split(QT_FT_Vector *b)
void attachAfter(Node *parent, Node *child)
static int cmp(const ushort *s1, const ushort *s2, size_t len)
QVertexSet(const QVertexSet< T > &other)
const T & at(int idx) const
bool operator==(const QIntersectionPoint &other) const
void sortEdgeList(const QPodPoint eventPoint)
static int compare(quint64 a, quint64 b)
Qt::MouseButton button() const
Returns the button that caused the event.
void qSwap(T &value1, T &value2)
void setWindow(const QRect &window)
Sets the painter's window to the given rectangle, and enables view transformations.
const T & at(int i) const
Returns the item at index position i in the vector.
SimpleToMonotone * m_parent
The QMouseEvent class contains parameters that describe a mouse event.
Q_CORE_EXPORT QTextStream & center(QTextStream &s)
bool operator<(const QFraction &other) const
The QBitArray class provides an array of bits.
void swapNodes(Node *n1, Node *n2)
void removeUnusedPoints()
QDataBuffer< int > m_upperVertex
static bool qPointIsLeftOfLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
QVector< qreal > vertices
void deleteNode(Node *&node)
#define Q_ASSERT_X(cond, where, what)
void rotateLeft(Node *node)
QIntersectionPoint intersectionPoint
QPolygonF toPolygon(qreal bezier_flattening_threshold=0.5) const
static qint64 qDot(const QPodPoint &u, const QPodPoint &v)
Qt::MouseButtons buttons() const
Returns the button state when the event was generated.
void removeUnwantedEdgesAndConnect()
bool operator<(const QIntersectionPoint &other) const
static int qCompareFractions(quint64 a, quint64 b, quint64 c, quint64 d)
static int primeForNumBits(int numBits)
bool checkRedBlackProperty(Node *top) const
bool operator>=(const QByteArray &a1, const QByteArray &a2)
The QPoint class defines a point in the plane using integer precision.
int splitEdge(int splitIndex)
reference back()
This function is provided for STL compatibility.
const qreal * points() const
void rotateRight(Node *node)
bool operator==(const QFraction &other) const
void setPen(const QColor &color)
Sets the painter's pen to have style Qt::SolidLine, width 0 and the specified color.
void initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix)
void setupDataStructures()
QTriangulator< T > * m_parent
void push_back(const T &t)
This function is provided for STL compatibility.
static Extensions glExtensions()
void setX(qreal x)
Sets the x coordinate of this point to the given x coordinate.
QTriangleSet qTriangulate(const qreal *polygon, int count, uint hint, const QTransform &matrix)
bool reallocate(int capacity)
qreal y() const
Returns the y-coordinate of this point.
QVertexSet< T > & operator=(const QVertexSet< T > &other)
void removeZeroLengthEdges()
bool rehash(int capacity)
bool calculateIntersection(int left, int right)
QMaxHeap< Intersection > m_topIntersection
QDataBuffer< QPodPoint > m_vertices
int x() const
Returns the x coordinate of this point.
QRBTree< int >::Node * node
void setOpacity(qreal opacity)
Sets the opacity of the painter to opacity.
int order(Node *left, Node *right)
QDataBuffer< Split > m_splits
QPair< QRBTree< int >::Node *, QRBTree< int >::Node * > outerBounds(const QPodPoint &point) const
timeval & operator+=(timeval &t1, const timeval &t2)
QRBTree< int > m_edgeList
bool pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3)
The QPaintEvent class contains event parameters for paint events.
void classifyVertex(int i)
static QFraction qFraction(quint64 n, quint64 d)
bool operator<(const Event &other) const
Q_CORE_EXPORT QTextStream & left(QTextStream &s)
void createDiagonal(int lower, int upper)
bool operator==(QBool b1, bool b2)
Node * front(Node *node) const
int size() const
Returns the number of items in the vector.
void attachBefore(Node *parent, Node *child)
bool operator()(int i, int j) const
Q_DECL_CONSTEXPR int qRound(qreal d)
void fillRect(const QRectF &, const QBrush &)
Fills the given rectangle with the brush specified.
Node * back(Node *node) const
QPolylineSet qPolyline(const QVectorPath &path, const QTransform &matrix, qreal lod)
int previous(int index) const
void rebalance(Node *node)
bool operator()(int i, int j) const
timeval operator+(const timeval &t1, const timeval &t2)