57 #define QDEBUG if (1){} else qDebug 101 return edge < other.
edge;
125 bool intersect(
const Edge &other,
Q27Dot5 *
y,
bool *det_positive)
const;
133 bool operator() (
const Edge *e1,
const Edge *e2);
142 void init(
int maxActiveEdges);
146 int findEdgePosition(
const Edge &e)
const;
147 int findEdge(
int edge)
const;
151 Edge *tmp = edges[p1];
152 edges[p1] = edges[p2];
155 void insert(
int pos,
const Edge &e);
156 void removeAt(
int pos);
157 void markEdges(
int pos1,
int pos2);
172 enum { default_alloc = 32 };
176 enum { default_alloc = 128 };
179 void init(
int maxVertices);
184 Vertex *operator[] (
int i) {
return storage + i; }
185 const Vertex *operator[] (
int i)
const {
return storage + i; }
191 if (v == storage + nPoints)
197 if (v == storage + nPoints)
203 if (v == storage + nPoints)
209 v = storage + nPoints;
215 v = storage + nPoints;
221 v = storage + nPoints;
244 intersect_left = intersect_right =
true;
249 v1 = vertices.
next(v0);
259 y_left = y_right = v0->y;
286 qint64 a1 = v1->y - v0->y;
287 qint64 b1 = v0->x - v1->x;
292 qint64 det = a1 * b2 - a2 * b1;
303 QDEBUG() <<
" " << r3 << r4;
304 if (r3 != 0 && r4 != 0 &&
sameSign( r3, r4 ))
309 qint64 r1 = a2 * v0->x + b2 * v0->y + c2;
310 qint64 r2 = a2 * v1->x + b2 * v1->y + c2;
314 QDEBUG() <<
" " << r1 << r2;
315 if (r1 != 0 && r2 != 0 &&
sameSign( r1, r2 ))
321 qint64 offset = det < 0 ? -det : det;
324 qint64 num = a2 * c1 - a1 * c2;
325 *y = ( num < 0 ? num - offset : num + offset ) / det;
327 *det_positive = (det > 0);
337 qint64 a1 = v1->y - v0->y;
338 qint64 b1 = v0->x - v1->x;
344 qint64 det = a1 * b2 - a2 * b1;
348 qint64 r1 = a2 * v0->x + b2 * v0->y + c2;
351 return edge < other.
edge;
358 qint64 offset = det < 0 ? -det : det;
361 qint64 num = a2 * c1 - a1 * c2;
362 qint64 yi = ( num < 0 ? num - offset : num + offset ) / det;
365 return ((yi > y) ^ (det < 0));
371 if (p1->
y == p2->
y) {
374 return p1->
x < p2->x;
376 return p1->
y < p2->
y;
387 return (v0->x + d*(y - v0->y)/(v1->y-v0->y));
406 if (!edges || maxActiveEdges > default_alloc) {
407 max_edges = maxActiveEdges;
408 int s =
qMax(maxActiveEdges + 1, default_alloc + 1);
416 for (
int i = 0; i < maxActiveEdges; ++i)
417 edge_table[i].edge = i+1;
418 edge_table[maxActiveEdges].edge = -1;
423 if (max_edges > default_alloc) {
445 int pos = min + ((max - min + 1) >> 1);
446 Q27Dot5 ax = edges[pos]->positionAt(y);
462 int pos = min + ((max - min) >> 1);
464 if (edges[pos]->isLeftOf(e, e.
v0->
y)) {
476 for (
int i = 0; i < size; ++i) {
477 int item_edge = edges[i]->edge;
478 if (item_edge == edge)
487 for (
int i = 0; i < size; ++i) {
488 edges[i]->mark =
false;
489 edges[i]->intersect_left =
false;
490 edges[i]->intersect_right =
false;
513 (*e)->
edge = first_unused;
514 first_unused = (*e - edge_table);
522 Edge *edge = edge_table + first_unused;
523 first_unused = edge->
edge;
526 memmove(edges + pos + 1, edges + pos, (size - pos)*
sizeof(
Edge *));
533 Edge *e = edges[pos];
536 memmove(edges + pos, edges + pos + 1, (size - pos)*
sizeof(
Edge *));
544 for (
int i = pos1; i <= pos2; ++i)
545 edges[i]->mark =
true;
567 if (!storage || maxVertices > allocated) {
568 int size =
qMax((
int)default_alloc, maxVertices);
571 allocated = maxVertices;
577 if (allocated > default_alloc) {
612 qreal xmin(points[0].
x());
613 qreal xmax(points[0].
x());
614 qreal ymin(points[0].
y());
615 qreal ymax(points[0].
y());
634 xmin =
qMin(xmin, points[i+1].
x());
635 xmax =
qMax(xmax, points[i+1].
x());
636 ymin =
qMin(ymin, points[i+1].
y());
637 ymax =
qMax(ymax, points[i+1].
y());
643 if (v->
x == x_next && v->
y == y_next) {
651 else if (y_prev > y_curr)
657 *maxActiveEdges += 2;
663 else if (y_prev > y_curr)
671 else if (y_curr > y_next)
678 *maxActiveEdges += 2;
687 QDEBUG() <<
"maxActiveEdges=" << *maxActiveEdges;
691 return QRectF(xmin, ymin, xmax-xmin, ymax-ymin);
734 int testListSize = 0;
737 if (v->
x != n->
x || v->
y != n->
y)
740 if (testListSize > tlSize - 2) {
741 tlSize =
qMax(tlSize*2, 16);
745 tl[testListSize].
start = n;
747 tl[testListSize].
used =
false;
748 tl[testListSize].
before =
true;
752 tl[testListSize].
start = n;
754 tl[testListSize].
used =
false;
755 tl[testListSize].
before =
false;
763 qSort(tl, tl + testListSize);
765 for (
int j = 0; j < testListSize; ++j) {
769 for (
int k = j + 1; k < testListSize; ++k) {
770 if (tl[j].
end->x != tl[k].
end->
x 775 if (!
winding || tl[j].before != tl[k].before) {
852 QDEBUG() <<
"PROCESS INTERSECTIONS";
860 QDEBUG() <<
" swapping intersecting edges ";
873 min =
qMin(edgePos, min);
874 max =
qMax(edgePos, max);
891 QDEBUG() <<
"sorting between" << min <<
"and" << max <<
"xpos=" << xmin << xmax;
893 QDEBUG() <<
" adding edge on left";
897 QDEBUG() <<
" adding edge on right";
903 for (
int i = min; i <= max; ++i)
906 for (
int i = min; i <= max; ++i) {
961 QDEBUG() <<
" adding edge" << start <<
"at position" << pos;
1060 if (e2->
edge == next)
1063 if (e2->
edge == prev)
1068 bool isect = e1->
intersect(*e2, &yi, &det_positive);
1071 QDEBUG() <<
" no intersection";
1079 QDEBUG() <<
" ----->>>>>> WRONG ORDER!";
1082 QDEBUG() <<
" between edges " << e1->
edge <<
"and" << e2->
edge <<
"at point (" 1095 if (link1.
next == -1 && link2.
next == -1) {
1101 checkLinkChain(intersections, i1);
1102 checkLinkChain(intersections, i2);
1106 }
else if (link1.
next == -1 || link2.
next == -1) {
1107 if (link2.
next == -1) {
1109 qSwap(link1, link2);
1113 checkLinkChain(intersections, i2);
1126 intersections.
insert(other, link);
1132 checkLinkChain(intersections, i1);
1133 checkLinkChain(intersections, i2);
1152 intersections.
insert(other1, linko1);
1153 intersections.
insert(other2, linko2);
1155 intersections.
insert(i1, link1);
1156 intersections.
insert(i2, link2);
1158 checkLinkChain(intersections, i1);
1159 checkLinkChain(intersections, i2);
1170 QDEBUG() <<
"INTERSECTIONS";
1190 QDEBUG() <<
"----------------> intersection on same line";
1192 scanline.processIntersections(
y, &intersections);
1217 Q_ASSERT(points[0] == points[nPoints-1]);
1222 for (
int i = 0; i < nPoints; ++i) {
1228 d->vertices.nPoints = nPoints;
1229 d->vertices.init(nPoints);
1231 int maxActiveEdges = 0;
1232 QRectF br =
d->collectAndSortVertices(points, &maxActiveEdges);
1233 d->cancelCoincidingEdges();
1236 QDEBUG() <<
"nPoints = " << nPoints <<
"using " <<
d->vertices.nPoints;
1238 for (
int i = 0; i <
d->vertices.nPoints; ++i) {
1239 QDEBUG() <<
" " << i <<
": " 1240 <<
"point=" <<
d->vertices.position(
d->vertices.sorted[i])
1241 <<
"flags=" <<
d->vertices.sorted[i]->flags
1247 d->scanline.init(maxActiveEdges);
1249 d->currentVertex = 0;
1251 while (
d->currentVertex <
d->vertices.nPoints) {
1252 d->scanline.clearMarks();
1254 d->y =
d->vertices.sorted[
d->currentVertex]->y;
1255 if (!
d->intersections.isEmpty())
1256 d->y =
qMin(
d->y,
d->intersections.constBegin().key().y);
1260 d->scanline.prepareLine();
1261 d->processIntersections();
1264 d->addIntersections();
1266 d->scanline.lineDone();
1269 QDEBUG()<<
"===== edges:";
1270 for (
int i = 0; i <
d->scanline.size; ++i) {
1271 QDEBUG() <<
" " <<
d->scanline.edges[i]->edge
1279 ?
d->scanline.edges[i]->isLeftOf(*
d->scanline.edges[i+1],
d->y)
1286 d->intersections.clear();
1293 Q_ASSERT(points[0] == points[nPoints-1]);
1296 d->vertices.nPoints = nPoints;
1297 d->vertices.init(nPoints);
1299 for (
int i = 0; i < nPoints; ++i) {
1307 for (
int i = 1; i < nPoints; ++i) {
1308 if (
d->vertices[i]->y <
d->vertices[top]->y)
1312 left = (top + nPoints - 1) % nPoints;
1313 right = (top + 1) % nPoints;
1315 while (
d->vertices[left]->x ==
d->vertices[top]->x &&
d->vertices[left]->y ==
d->vertices[top]->y && left !=
right)
1316 left = (left + nPoints - 1) % nPoints;
1318 while (
d->vertices[
right]->x ==
d->vertices[top]->x &&
d->vertices[
right]->y ==
d->vertices[top]->y && left !=
right)
1326 Vertex dLeft = {
d->vertices[top]->x -
d->vertices[
left]->x,
1327 d->vertices[top]->y -
d->vertices[
left]->y };
1329 Vertex dRight = {
d->vertices[
right]->x -
d->vertices[top]->x,
1330 d->vertices[
right]->y -
d->vertices[top]->y };
1332 Q27Dot5 cross = dLeft.
x * dRight.
y - dLeft.
y * dRight.
x;
1335 if (cross < 0 || (cross == 0 && dLeft.
x > 0)) {
1340 Vertex *lastLeft =
d->vertices[top];
1341 Vertex *lastRight =
d->vertices[top];
1345 while (lastLeft->
y ==
d->vertices[left]->y && left !=
right) {
1346 lastLeft =
d->vertices[
left];
1347 left = (left + nPoints - dir) % nPoints;
1350 while (lastRight->
y ==
d->vertices[
right]->y && left !=
right) {
1351 lastRight =
d->vertices[
right];
1356 trap.
top =
qMax(lastRight->
y, lastLeft->
y);
1369 if (
d->vertices[
right]->y <
d->vertices[left]->y) {
1371 lastRight =
d->vertices[
right];
1374 while (lastRight->
y ==
d->vertices[
right]->y && left !=
right);
1377 lastLeft =
d->vertices[
left];
1378 left = (left + nPoints - dir) % nPoints;
1380 while (lastLeft->
y ==
d->vertices[left]->y && left !=
right);
1398 Vertex delta = { b.
x - a.
x, b.y - a.
y };
1400 if (delta.
x == 0 && delta.
y == 0)
1411 Vertex topLeft = { a.
x - halfWidth, a.
y };
1412 Vertex topRight = { a.
x + halfWidth, a.
y };
1413 Vertex bottomLeft = { a.
x - halfWidth, b.y };
1414 Vertex bottomRight = { a.
x + halfWidth, b.y };
1418 }
else if (delta.
y == 0) {
1427 Vertex topLeft = { a.
x, a.
y - halfWidth };
1428 Vertex topRight = { b.
x, a.
y - halfWidth };
1429 Vertex bottomLeft = { a.
x, a.
y + halfWidth };
1430 Vertex bottomRight = { b.
x, a.
y + halfWidth };
1442 perp *= hw / length;
void init(int maxActiveEdges)
void markEdges(int pos1, int pos2)
void cancelCoincidingEdges()
Q_DECL_CONSTEXPR const T & qMin(const T &a, const T &b)
#define QT_END_NAMESPACE
This macro expands to.
QTessellatorPrivate::Vertex * end
#define it(className, varName)
static const bool emit_clever
The QPointF class defines a point in the plane using floating point precision.
const Vertex * bottomLeft
#define Q27Dot5ToDouble(i)
QRectF tessellate(const QPointF *points, int nPoints)
int findEdgePosition(Q27Dot5 x, Q27Dot5 y) const
QTessellatorPrivate::Vertex * start
static bool compareVertex(const QTessellatorPrivate::Vertex *p1, const QTessellatorPrivate::Vertex *p2)
long ASN1_INTEGER_get ASN1_INTEGER * a
int nextPos(const Vertex *v) const
int position(const Vertex *v) const
iterator find(const Key &key)
Returns an iterator pointing to the item with key key in the map.
bool edgeInChain(Intersection i, int edge)
bool operator<(int priority, const QPair< QRunnable *, int > &p)
bool operator()(const Edge *e1, const Edge *e2)
Q_CORE_EXPORT QTextStream & right(QTextStream &s)
#define FloatToQ27Dot5(i)
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
qreal x() const
Returns the x-coordinate of this point.
#define QT_BEGIN_NAMESPACE
This macro expands to.
static QIntfbScreen * connected
bool intersect(const Edge &other, Q27Dot5 *y, bool *det_positive) const
The QRectF class defines a rectangle in the plane using floating point precision. ...
static void fillTrapezoid(Q27Dot5 y1, Q27Dot5 y2, int left, int right, const QTessellatorPrivate::Vertices &vertices, QTessellator::Trapezoid *trap)
static void cancelEdges(QCoincidingEdge &e1, QCoincidingEdge &e2)
Edge(const Vertices &v, int _edge)
const T value(const Key &key) const
Returns the value associated with the key key.
void emitEdges(QTessellator *tessellator)
const Vertex * bottomRight
void init(int maxVertices)
const Vertex * prev(const Vertex *v) const
const_iterator constBegin() const
Returns a const STL-style iterator pointing to the first item in the map.
Q27Dot5 positionAt(Q27Dot5 y) const
void qSort(RandomAccessIterator start, RandomAccessIterator end)
void qSwap(T &value1, T &value2)
iterator begin()
Returns an STL-style iterator pointing to the first item in the map.
int remove(const Key &key)
Removes all the items that have the key key from the map.
iterator end()
Returns an STL-style iterator pointing to the imaginary item after the last item in the map...
void processIntersections()
static bool sameSign(qint64 a, qint64 b)
Intersections intersections
iterator insert(const Key &key, const T &value)
Inserts a new item with the key key and a value of value.
int prevPos(const Vertex *v) const
bool isEmpty() const
Returns true if the map contains no items; otherwise returns false.
bool operator<(const QCoincidingEdge &e2) const
QRectF collectAndSortVertices(const QPointF *points, int *maxActiveEdges)
int findEdge(int edge) const
qreal y() const
Returns the y-coordinate of this point.
static Q_DECL_CONSTEXPR bool qFuzzyIsNull(double d)
static const bool mark_clever
virtual void addTrap(const Trapezoid &trap)=0
bool isLeftOf(const Edge &other, Q27Dot5 y) const
void tessellateRect(const QPointF &a, const QPointF &b, qreal width)
void tessellateConvex(const QPointF *points, int nPoints)
QMap< Intersection, IntersectionLink > Intersections
void swap(int p1, int p2)
static const KeyPair *const end
void addIntersection(const Edge *e1, const Edge *e2)
Q_CORE_EXPORT QTextStream & left(QTextStream &s)
void insert(int pos, const Edge &e)
const Vertex * next(const Vertex *v) const