42 for (
int i = 0; i <
mHalfEdge.count(); i++ )
53 for (
int i = 0; i <
mHalfEdge.count(); i++ )
72 int currentpoint = -10;
75 for (
const QgsPoint &point : points )
79 if ( actpoint != -100 )
85 if ( actpoint == -100 )
90 for ( ; i < points.size(); ++i )
93 if ( currentpoint != -100 && actpoint != -100 && currentpoint != actpoint )
97 actpoint = currentpoint;
125 unsigned int zedge =
insertEdge( -10, -10, -1,
false,
false );
126 unsigned int fedge =
insertEdge( (
int )zedge, (
int )zedge, 0,
false,
false );
127 (
mHalfEdge.at( zedge ) )->setDual( (
int )fedge );
128 (
mHalfEdge.at( zedge ) )->setNext( (
int )fedge );
137 QgsDebugMsg(
"second point is the same as the first point, it thus has not been inserted" );
144 unsigned int sedge =
insertEdge( -10, -10, 1,
false,
false );
145 unsigned int tedge =
insertEdge( (
int )sedge, 0, 0,
false,
false );
146 unsigned int foedge =
insertEdge( -10, 4, 1,
false,
false );
147 unsigned int fiedge =
insertEdge( (
int )foedge, 1, -1,
false,
false );
148 mHalfEdge.at( sedge )->setDual( (
int )tedge );
149 mHalfEdge.at( sedge )->setNext( (
int )fiedge );
150 mHalfEdge.at( foedge )->setDual( (
int )fiedge );
151 mHalfEdge.at( foedge )->setNext( (
int )tedge );
152 mHalfEdge.at( 0 )->setNext( (
int )foedge );
153 mHalfEdge.at( 1 )->setNext( (
int )sedge );
165 unsigned int edgea =
insertEdge( -10, -10, 2,
false,
false );
166 unsigned int edgeb =
insertEdge( (
int )edgea, 5, 1,
false,
false );
167 unsigned int edgec =
insertEdge( -10, (
int )edgeb, 2,
false,
false );
168 unsigned int edged =
insertEdge( -10, 2, 0,
false,
false );
169 unsigned int edgee =
insertEdge( (
int )edged, -10, 2,
false,
false );
170 unsigned int edgef =
insertEdge( (
int )edgec, 1, -1,
false,
false );
171 mHalfEdge.at( edgea )->setDual( (
int )edgeb );
172 mHalfEdge.at( edgea )->setNext( (
int )edged );
173 mHalfEdge.at( edgec )->setDual( (
int )edgef );
174 mHalfEdge.at( edged )->setDual( (
int )edgee );
175 mHalfEdge.at( edgee )->setNext( (
int )edgef );
176 mHalfEdge.at( 5 )->setNext( (
int )edgec );
177 mHalfEdge.at( 1 )->setNext( (
int )edgee );
178 mHalfEdge.at( 2 )->setNext( (
int )edgea );
184 unsigned int edgea =
insertEdge( -10, -10, 2,
false,
false );
185 unsigned int edgeb =
insertEdge( (
int )edgea, 0, 0,
false,
false );
186 unsigned int edgec =
insertEdge( -10, (
int )edgeb, 2,
false,
false );
187 unsigned int edged =
insertEdge( -10, 3, 1,
false,
false );
188 unsigned int edgee =
insertEdge( (
int )edged, -10, 2,
false,
false );
189 unsigned int edgef =
insertEdge( (
int )edgec, 4, -1,
false,
false );
190 mHalfEdge.at( edgea )->setDual( (
int )edgeb );
191 mHalfEdge.at( edgea )->setNext( (
int )edged );
192 mHalfEdge.at( edgec )->setDual( (
int )edgef );
193 mHalfEdge.at( edged )->setDual( (
int )edgee );
194 mHalfEdge.at( edgee )->setNext( (
int )edgef );
195 mHalfEdge.at( 0 )->setNext( (
int )edgec );
196 mHalfEdge.at( 4 )->setNext( (
int )edgee );
197 mHalfEdge.at( 3 )->setNext( (
int )edgea );
203 QgsDebugMsg(
"error: third point is on the same line as the first and the second point. It thus has not been inserted into the triangulation" );
254 unsigned int edge5 =
insertEdge( edge3, -10, -1,
false,
false );
267 unsigned int index = ccwedge;
274 if ( toswap == cwedge )
284 else if ( number >= 0 )
286 int nextnumber =
mHalfEdge[number]->getNext();
298 mHalfEdge.at( edge1 )->setDual( (
int )edge2 );
299 mHalfEdge.at( edge2 )->setNext( (
int )edge5 );
300 mHalfEdge.at( edge3 )->setDual( (
int )edge4 );
301 mHalfEdge.at( edge5 )->setDual( (
int )edge6 );
302 mHalfEdge.at( number )->setNext( (
int )edge2 );
303 mHalfEdge.at( nextnumber )->setNext( (
int )edge4 );
304 mHalfEdge.at( nextnextnumber )->setNext( (
int )edge6 );
313 else if ( number == -20 )
348 else if ( number == -100 || number == -5 )
356 else if ( number == -25 )
361 existingPoint->
setZ( std::max( newPoint->
z(), existingPoint->
z() ) );
379 for (
int i = 0; i <
mHalfEdge.count(); i++ )
393 if ( control > 1000000 )
399 for (
int i = 0; i <
mHalfEdge.count(); i++ )
409 int topoint =
mHalfEdge[actedge]->getPoint();
411 if ( frompoint == -1 || topoint == -1 )
413 for (
int i = 0; i <
mHalfEdge.count(); i++ )
432 else if ( leftofnumber <= 0.0 )
451 int firstendp = 0, secendp = 0, thendp = 0, fouendp = 0;
472 else if ( leftofvalue == 0 )
478 secendp =
mHalfEdge[actedge]->getPoint();
480 else if ( nulls == 1 )
484 fouendp =
mHalfEdge[actedge]->getPoint();
527 if ( numinstabs > 0 )
537 if ( firstendp == thendp || firstendp == fouendp )
543 else if ( secendp == thendp || secendp == fouendp )
572 if ( x1 < x2 && x1 < x3 )
576 else if ( x2 < x1 && x2 < x3 )
580 else if ( x3 < x1 && x3 < x2 )
653 QgsPoint *ptc =
mPointVector[mHalfEdge[mHalfEdge[mHalfEdge[edge]->getNext()]->getNext()]->getPoint()];
654 QgsPoint *ptd =
mPointVector[mHalfEdge[mHalfEdge[mHalfEdge[edge]->getDual()]->getNext()]->getPoint()];
657 doSwap( edge, recursiveDeep );
666 unsigned int edge1 = edge;
667 unsigned int edge2 =
mHalfEdge[edge]->getDual();
668 unsigned int edge3 =
mHalfEdge[edge]->getNext();
684 unsigned int edge1 = edge;
685 unsigned int edge2 =
mHalfEdge[edge]->getDual();
686 unsigned int edge3 =
mHalfEdge[edge]->getNext();
706 void DualEdgeTriangulation::draw( QPainter *p,
double xlowleft,
double ylowleft,
double xupright,
double yupright,
double width,
double height )
const 716 bool *control =
new bool[
mHalfEdge.count()];
717 bool *control2 =
new bool[
mHalfEdge.count()];
719 for (
unsigned int i = 0; i <=
mHalfEdge.count() - 1; i++ )
725 if ( ( ( xupright - xlowleft ) / width ) > ( ( yupright - ylowleft ) / height ) )
727 double lowerborder = -( height * ( xupright - xlowleft ) / width - yupright );
728 for (
unsigned int i = 0; i <
mHalfEdge.count() - 1; i++ )
742 if ( p1 == p2 && p2 == p3 &&
halfEdgeBBoxTest( i, xlowleft, lowerborder, xupright, yupright ) &&
halfEdgeBBoxTest(
mHalfEdge[i]->getNext(), xlowleft, lowerborder, xupright, yupright ) &&
halfEdgeBBoxTest(
mHalfEdge[
mHalfEdge[i]->getNext()]->getNext(), xlowleft, lowerborder, xupright, yupright ) )
748 QColor c( 255, 0, 0 );
750 p->drawPolygon( pa );
755 control2[
mHalfEdge[i]->getNext()] =
true;
756 control2[mHalfEdge[mHalfEdge[i]->getNext()]->getNext()] =
true;
790 double rightborder = width * ( yupright - ylowleft ) / height + xlowleft;
791 for (
unsigned int i = 0; i <
mHalfEdge.count() - 1; i++ )
805 if ( p1 == p2 && p2 == p3 &&
halfEdgeBBoxTest( i, xlowleft, ylowleft, rightborder, yupright ) &&
halfEdgeBBoxTest(
mHalfEdge[i]->getNext(), xlowleft, ylowleft, rightborder, yupright ) &&
halfEdgeBBoxTest(
mHalfEdge[
mHalfEdge[i]->getNext()]->getNext(), xlowleft, ylowleft, rightborder, yupright ) )
811 QColor c( 255, 0, 0 );
813 p->drawPolygon( pa );
818 control2[
mHalfEdge[i]->getNext()] =
true;
819 control2[mHalfEdge[mHalfEdge[i]->getNext()]->getNext()] =
true;
864 int nextnextedge = firstedge;
868 edge =
mHalfEdge[nextnextedge]->getDual();
871 theedge = nextnextedge;
875 nextnextedge =
mHalfEdge[nextedge]->getNext();
877 while ( nextnextedge != firstedge );
879 if ( theedge == -10 )
881 QgsDebugMsg( QString(
"warning, error: the points are: %1 and %2" ).arg( p1 ).arg( p2 ) );
895 if ( firstedge == -1 )
900 int actedge = firstedge;
901 int edge, nextedge, nextnextedge;
908 nextnextedge =
mHalfEdge[nextedge]->getNext();
910 if (
mHalfEdge[nextnextedge]->getBreak() )
918 actedge = nextnextedge;
920 while ( nextnextedge != firstedge );
940 else if ( edge >= 0 )
959 else if ( edge == -20 )
964 if ( ptnr1 == -1 || ptnr2 == -1 || ptnr3 == -1 )
982 else if ( edge == -25 )
987 int ptnr1 =
mHalfEdge[edge1]->getPoint();
988 int ptnr2 =
mHalfEdge[edge2]->getPoint();
989 int ptnr3 =
mHalfEdge[edge3]->getPoint();
1004 else if ( edge == -5 )
1009 if ( ptnr1 == -1 || ptnr2 == -1 || ptnr3 == -1 )
1029 QgsDebugMsg( QString(
"problem: the edge is: %1" ).arg( edge ) );
1047 else if ( edge >= 0 )
1049 int ptnr1 =
mHalfEdge[edge]->getPoint();
1063 else if ( edge == -20 )
1068 if ( ptnr1 == -1 || ptnr2 == -1 || ptnr3 == -1 )
1083 else if ( edge == -25 )
1086 int edge2 =
mHalfEdge[edge1]->getNext();
1087 int edge3 =
mHalfEdge[edge2]->getNext();
1088 int ptnr1 =
mHalfEdge[edge1]->getPoint();
1089 int ptnr2 =
mHalfEdge[edge2]->getPoint();
1090 int ptnr3 =
mHalfEdge[edge3]->getPoint();
1091 if ( ptnr1 == -1 || ptnr2 == -1 || ptnr3 == -1 )
1106 else if ( edge == -5 )
1111 if ( ptnr1 == -1 || ptnr2 == -1 || ptnr3 == -1 )
1148 QList<int> crossedEdges;
1151 int pointingedge = 0;
1155 if ( pointingedge == -1 )
1161 int actedge =
mHalfEdge[pointingedge]->getDual();
1168 if ( control > 17000 )
1219 if ( dista <= distb )
1225 else if ( distb <= dista )
1241 float frac = distpart / disttot;
1243 if ( frac == 0 || frac == 1 )
1255 else if ( frac == 1 )
1286 crossedEdges.append(
mHalfEdge[actedge]->getNext() );
1302 p3 = mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getPoint();
1303 p4 = mHalfEdge[mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getNext()]->getPoint();
1305 double dista = std::sqrt( ( crosspoint.
x() - mPointVector[p3]->x() ) * ( crosspoint.
x() - mPointVector[p3]->x() ) + ( crosspoint.
y() - mPointVector[p3]->y() ) * ( crosspoint.
y() - mPointVector[p3]->y() ) );
1306 double distb = std::sqrt( ( crosspoint.
x() - mPointVector[p4]->x() ) * ( crosspoint.
x() - mPointVector[p4]->x() ) + ( crosspoint.
y() - mPointVector[p4]->y() ) * ( crosspoint.
y() - mPointVector[p4]->y() ) );
1307 if ( dista <= distb )
1313 else if ( distb <= dista )
1324 p3 = mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getPoint();
1325 p4 = mHalfEdge[mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getNext()]->getPoint();
1327 double distpart = std::sqrt( ( crosspoint.
x() - mPointVector[p3]->x() ) * ( crosspoint.
x() - mPointVector[p3]->x() ) + ( crosspoint.
y() - mPointVector[p3]->y() ) * ( crosspoint.
y() - mPointVector[p3]->y() ) );
1328 double disttot = std::sqrt( ( mPointVector[p3]->x() - mPointVector[p4]->x() ) * ( mPointVector[p3]->x() - mPointVector[p4]->x() ) + ( mPointVector[p3]->y() - mPointVector[p4]->y() ) * ( mPointVector[p3]->y() - mPointVector[p4]->y() ) );
1329 float frac = distpart / disttot;
1330 if ( frac == 0 || frac == 1 )
1334 int newpoint =
splitHalfEdge( mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getNext(), frac );
1340 crossedEdges.append( mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getNext() );
1343 else if (
MathUtils::lineIntersection( mPointVector[mHalfEdge[mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getNext()]->getPoint()], mPointVector[mHalfEdge[mHalfEdge[mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getNext()]->getNext()]->getPoint()], mPointVector[p1], mPointVector[p2] ) )
1349 p3 = mHalfEdge[mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getNext()]->getPoint();
1350 p4 = mHalfEdge[mHalfEdge[mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getNext()]->getNext()]->getPoint();
1352 double dista = std::sqrt( ( crosspoint.
x() - mPointVector[p3]->x() ) * ( crosspoint.
x() - mPointVector[p3]->x() ) + ( crosspoint.
y() - mPointVector[p3]->y() ) * ( crosspoint.
y() - mPointVector[p3]->y() ) );
1353 double distb = std::sqrt( ( crosspoint.
x() - mPointVector[p4]->x() ) * ( crosspoint.
x() - mPointVector[p4]->x() ) + ( crosspoint.
y() - mPointVector[p4]->y() ) * ( crosspoint.
y() - mPointVector[p4]->y() ) );
1354 if ( dista <= distb )
1360 else if ( distb <= dista )
1371 p3 = mHalfEdge[mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getNext()]->getPoint();
1372 p4 = mHalfEdge[mHalfEdge[mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getNext()]->getNext()]->getPoint();
1374 double distpart = std::sqrt( ( crosspoint.
x() - mPointVector[p3]->x() ) * ( crosspoint.
x() - mPointVector[p3]->x() ) + ( crosspoint.
y() - mPointVector[p3]->y() ) * ( crosspoint.
y() - mPointVector[p3]->y() ) );
1375 double disttot = std::sqrt( ( mPointVector[p3]->x() - mPointVector[p4]->x() ) * ( mPointVector[p3]->x() - mPointVector[p4]->x() ) + ( mPointVector[p3]->y() - mPointVector[p4]->y() ) * ( mPointVector[p3]->y() - mPointVector[p4]->y() ) );
1376 float frac = distpart / disttot;
1377 if ( frac == 0 || frac == 1 )
1381 int newpoint =
splitHalfEdge( mHalfEdge[mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getNext()]->getNext(), frac );
1387 crossedEdges.append( mHalfEdge[mHalfEdge[mHalfEdge[crossedEdges.last()]->getDual()]->getNext()]->getNext() );
1397 QList<int>::const_iterator iter;
1398 for ( iter = crossedEdges.constBegin(); iter != crossedEdges.constEnd(); ++iter )
1400 mHalfEdge[( *( iter ) )]->setForced(
false );
1401 mHalfEdge[( *( iter ) )]->setBreak(
false );
1409 QList<int> freelist = crossedEdges;
1412 QList<int> leftPolygon;
1413 QList<int> rightPolygon;
1416 int firstedge = freelist.first();
1417 mHalfEdge[firstedge]->setForced(
true );
1419 leftPolygon.append( firstedge );
1420 int dualfirstedge =
mHalfEdge[freelist.first()]->getDual();
1421 mHalfEdge[dualfirstedge]->setForced(
true );
1423 rightPolygon.append( dualfirstedge );
1424 freelist.pop_front();
1428 QList<int>::const_iterator leftiter;
1429 leftiter = crossedEdges.constEnd();
1434 if ( newpoint != actpointl )
1437 actpointl = newpoint;
1439 leftPolygon.append( theedge );
1441 if ( leftiter == crossedEdges.constBegin() )
1447 leftPolygon.append(
mHalfEdge[crossedEdges.first()]->getNext() );
1450 QList<int>::const_iterator rightiter;
1452 for ( rightiter = crossedEdges.constBegin(); rightiter != crossedEdges.constEnd(); ++rightiter )
1455 if ( newpoint != actpointr )
1458 actpointr = newpoint;
1460 rightPolygon.append( theedge );
1466 rightPolygon.append(
mHalfEdge[
mHalfEdge[crossedEdges.last()]->getDual()]->getNext() );
1467 mHalfEdge[rightPolygon.last()]->setNext( dualfirstedge );
1470 int actedgel = leftPolygon[1];
1471 leftiter = leftPolygon.constBegin();
1473 for ( ; leftiter != leftPolygon.constEnd(); ++leftiter )
1475 mHalfEdge[actedgel]->setNext( ( *leftiter ) );
1476 actedgel = ( *leftiter );
1480 int actedger = rightPolygon[1];
1481 rightiter = rightPolygon.constBegin();
1483 for ( ; rightiter != rightPolygon.constEnd(); ++rightiter )
1485 mHalfEdge[actedger]->setNext( ( *rightiter ) );
1486 actedger = ( *( rightiter ) );
1491 mHalfEdge[leftPolygon.first()]->setNext( ( *( ++( leftiter = leftPolygon.constBegin() ) ) ) );
1492 mHalfEdge[leftPolygon.first()]->setPoint( p2 );
1493 mHalfEdge[leftPolygon.last()]->setNext( firstedge );
1494 mHalfEdge[rightPolygon.first()]->setNext( ( *( ++( rightiter = rightPolygon.constBegin() ) ) ) );
1495 mHalfEdge[rightPolygon.first()]->setPoint( p1 );
1496 mHalfEdge[rightPolygon.last()]->setNext( dualfirstedge );
1502 for ( iter = crossedEdges.constBegin(); iter != crossedEdges.constEnd(); ++iter )
1507 return leftPolygon.first();
1537 QgsDebugMsg(
"am in eliminateHorizontalTriangles" );
1538 double minangle = 0;
1542 bool swapped =
false;
1543 bool *control =
new bool[
mHalfEdge.count()];
1545 for (
int i = 0; i <=
mHalfEdge.count() - 1; i++ )
1551 for (
int i = 0; i <=
mHalfEdge.count() - 1; i++ )
1569 if ( p1 == -1 || p2 == -1 || p3 == -1 )
1577 double el1, el2, el3;
1582 if ( el1 == el2 && el2 == el3 )
1630 std::map<int, double> edge_angle;
1631 std::multimap<double, int> angle_edge;
1632 QSet<int> dontexamine;
1643 for (
int i = 0; i < nhalfedges - 1; i++ )
1646 int nextnext =
mHalfEdge[next]->getNext();
1657 Q_UNUSED( pointno );
1668 for (
int i = 0; i <
mHalfEdge.count() - 1; i++ )
1674 if ( p1 == -1 || p2 == -1 || p3 == -1 )
1680 bool twoforcededges;
1685 if ( angle < mintol && !twoforcededges )
1687 edge_angle.insert( std::make_pair( i, angle ) );
1688 angle_edge.insert( std::make_pair( angle, i ) );
1693 for ( std::multimap<double, int>::const_iterator it = angle_edge.begin(); it != angle_edge.end(); ++it )
1695 QgsDebugMsg( QString(
"angle: %1" ).arg( it->first ) );
1699 double minangle = 0;
1702 int minedgenextnext;
1706 while ( !edge_angle.empty() )
1708 minangle = angle_edge.begin()->first;
1709 QgsDebugMsg( QString(
"minangle: %1" ).arg( minangle ) );
1710 minedge = angle_edge.begin()->second;
1711 minedgenext =
mHalfEdge[minedge]->getNext();
1712 minedgenextnext =
mHalfEdge[minedgenext]->getNext();
1717 QgsDebugMsg(
"warning, calculation of circumcenter failed" );
1719 dontexamine.insert( minedge );
1720 edge_angle.erase( minedge );
1721 std::multimap<double, int>::iterator minedgeiter = angle_edge.find( minangle );
1722 while ( minedgeiter->second != minedge )
1726 angle_edge.erase( minedgeiter );
1733 QgsDebugMsg( QString(
"put circumcenter %1//%2 on dontexamine list because it is outside the convex hull" )
1734 .arg( circumcenter.
x() ).arg( circumcenter.
y() ) );
1735 dontexamine.insert( minedge );
1736 edge_angle.erase( minedge );
1737 std::multimap<double, int>::iterator minedgeiter = angle_edge.find( minangle );
1738 while ( minedgeiter->second != minedge )
1742 angle_edge.erase( minedgeiter );
1748 bool encroached =
false;
1750 #if 0 //slow version 1752 for (
int i = 0; i < numhalfedges; i++ )
1766 int actedge = pointingedge;
1769 double angle1, angle2, angle3;
1781 if ( pt1 == -1 || pt2 == -1 || pt3 == -1 )
1791 bool twoforcededges1, twoforcededges2, twoforcededges3;
1795 twoforcededges1 =
true;
1799 twoforcededges1 =
false;
1804 twoforcededges2 =
true;
1808 twoforcededges2 =
false;
1813 twoforcededges3 =
true;
1817 twoforcededges3 =
false;
1821 QSet<int>::iterator ed1iter = dontexamine.find( ed1 );
1822 if ( ed1iter != dontexamine.end() )
1825 dontexamine.erase( ed1iter );
1830 std::map<int, double>::iterator tempit1;
1831 tempit1 = edge_angle.find( ed1 );
1832 if ( tempit1 != edge_angle.end() )
1835 double angle = tempit1->second;
1836 edge_angle.erase( ed1 );
1837 std::multimap<double, int>::iterator tempit2 = angle_edge.lower_bound( angle );
1838 while ( tempit2->second != ed1 )
1842 angle_edge.erase( tempit2 );
1846 if ( angle1 < mintol && !twoforcededges1 )
1848 edge_angle.insert( std::make_pair( ed1, angle1 ) );
1849 angle_edge.insert( std::make_pair( angle1, ed1 ) );
1853 QSet<int>::iterator ed2iter = dontexamine.find( ed2 );
1854 if ( ed2iter != dontexamine.end() )
1857 dontexamine.erase( ed2iter );
1862 std::map<int, double>::iterator tempit1;
1863 tempit1 = edge_angle.find( ed2 );
1864 if ( tempit1 != edge_angle.end() )
1867 double angle = tempit1->second;
1868 edge_angle.erase( ed2 );
1869 std::multimap<double, int>::iterator tempit2 = angle_edge.lower_bound( angle );
1870 while ( tempit2->second != ed2 )
1874 angle_edge.erase( tempit2 );
1878 if ( angle2 < mintol && !twoforcededges2 )
1880 edge_angle.insert( std::make_pair( ed2, angle2 ) );
1881 angle_edge.insert( std::make_pair( angle2, ed2 ) );
1885 QSet<int>::iterator ed3iter = dontexamine.find( ed3 );
1886 if ( ed3iter != dontexamine.end() )
1889 dontexamine.erase( ed3iter );
1894 std::map<int, double>::iterator tempit1;
1895 tempit1 = edge_angle.find( ed3 );
1896 if ( tempit1 != edge_angle.end() )
1899 double angle = tempit1->second;
1900 edge_angle.erase( ed3 );
1901 std::multimap<double, int>::iterator tempit2 = angle_edge.lower_bound( angle );
1902 while ( tempit2->second != ed3 )
1906 angle_edge.erase( tempit2 );
1910 if ( angle3 < mintol && !twoforcededges3 )
1912 edge_angle.insert( std::make_pair( ed3, angle3 ) );
1913 angle_edge.insert( std::make_pair( angle3, ed3 ) );
1918 while ( actedge != pointingedge );
1922 #endif //end slow version 1926 QSet<int> influenceedges;
1928 if ( baseedge == -5 )
1931 edge_angle.erase( minedge );
1932 std::multimap<double, int>::iterator minedgeiter = angle_edge.find( minangle );
1933 while ( minedgeiter->second != minedge )
1937 angle_edge.erase( minedgeiter );
1940 else if ( baseedge == -25 )
1943 edge_angle.erase( minedge );
1944 std::multimap<double, int>::iterator minedgeiter = angle_edge.find( minangle );
1945 while ( minedgeiter->second != minedge )
1949 angle_edge.erase( minedgeiter );
1952 else if ( baseedge == -20 )
1961 for ( QSet<int>::iterator it = influenceedges.begin(); it != influenceedges.end(); ++it )
1973 int actedge = pointingedge;
1976 double angle1, angle2, angle3;
1988 if ( pt1 == -1 || pt2 == -1 || pt3 == -1 )
1998 bool twoforcededges1, twoforcededges2, twoforcededges3;
2010 QSet<int>::iterator ed1iter = dontexamine.find( ed1 );
2011 if ( ed1iter != dontexamine.end() )
2014 dontexamine.erase( ed1iter );
2019 std::map<int, double>::iterator tempit1;
2020 tempit1 = edge_angle.find( ed1 );
2021 if ( tempit1 != edge_angle.end() )
2024 double angle = tempit1->second;
2025 edge_angle.erase( ed1 );
2026 std::multimap<double, int>::iterator tempit2 = angle_edge.lower_bound( angle );
2027 while ( tempit2->second != ed1 )
2031 angle_edge.erase( tempit2 );
2035 if ( angle1 < mintol && !twoforcededges1 )
2037 edge_angle.insert( std::make_pair( ed1, angle1 ) );
2038 angle_edge.insert( std::make_pair( angle1, ed1 ) );
2042 QSet<int>::iterator ed2iter = dontexamine.find( ed2 );
2043 if ( ed2iter != dontexamine.end() )
2046 dontexamine.erase( ed2iter );
2051 std::map<int, double>::iterator tempit1;
2052 tempit1 = edge_angle.find( ed2 );
2053 if ( tempit1 != edge_angle.end() )
2056 double angle = tempit1->second;
2057 edge_angle.erase( ed2 );
2058 std::multimap<double, int>::iterator tempit2 = angle_edge.lower_bound( angle );
2059 while ( tempit2->second != ed2 )
2063 angle_edge.erase( tempit2 );
2067 if ( angle2 < mintol && !twoforcededges2 )
2069 edge_angle.insert( std::make_pair( ed2, angle2 ) );
2070 angle_edge.insert( std::make_pair( angle2, ed2 ) );
2074 QSet<int>::iterator ed3iter = dontexamine.find( ed3 );
2075 if ( ed3iter != dontexamine.end() )
2078 dontexamine.erase( ed3iter );
2083 std::map<int, double>::iterator tempit1;
2084 tempit1 = edge_angle.find( ed3 );
2085 if ( tempit1 != edge_angle.end() )
2088 double angle = tempit1->second;
2089 edge_angle.erase( ed3 );
2090 std::multimap<double, int>::iterator tempit2 = angle_edge.lower_bound( angle );
2091 while ( tempit2->second != ed3 )
2095 angle_edge.erase( tempit2 );
2099 if ( angle3 < mintol && !twoforcededges3 )
2101 edge_angle.insert( std::make_pair( ed3, angle3 ) );
2102 angle_edge.insert( std::make_pair( angle3, ed3 ) );
2107 while ( actedge != pointingedge );
2125 if ( pointno == -100 )
2127 QgsDebugMsg( QString(
"put circumcenter %1//%2 on dontexamine list because of numerical instabilities" )
2128 .arg( circumcenter.
x() ).arg( circumcenter.
y() ) );
2132 QgsDebugMsg( QString(
"put circumcenter %1//%2 on dontexamine list because it is already inserted" )
2133 .arg( circumcenter.
x() ).arg( circumcenter.
y() ) );
2145 QgsDebugMsg(
"point is not present in the triangulation" );
2149 dontexamine.insert( minedge );
2150 edge_angle.erase( minedge );
2151 std::multimap<double, int>::iterator minedgeiter = angle_edge.lower_bound( minangle );
2152 while ( minedgeiter->second != minedge )
2156 angle_edge.erase( minedgeiter );
2167 int actedge = pointingedge;
2170 double angle1, angle2, angle3;
2182 if ( pt1 == -1 || pt2 == -1 || pt3 == -1 )
2192 bool twoforcededges1, twoforcededges2, twoforcededges3;
2202 QSet<int>::iterator ed1iter = dontexamine.find( ed1 );
2203 if ( ed1iter != dontexamine.end() )
2206 dontexamine.erase( ed1iter );
2211 std::map<int, double>::iterator tempit1;
2212 tempit1 = edge_angle.find( ed1 );
2213 if ( tempit1 != edge_angle.end() )
2216 double angle = tempit1->second;
2217 edge_angle.erase( ed1 );
2218 std::multimap<double, int>::iterator tempit2 = angle_edge.lower_bound( angle );
2219 while ( tempit2->second != ed1 )
2223 angle_edge.erase( tempit2 );
2227 if ( angle1 < mintol && !twoforcededges1 )
2229 edge_angle.insert( std::make_pair( ed1, angle1 ) );
2230 angle_edge.insert( std::make_pair( angle1, ed1 ) );
2235 QSet<int>::iterator ed2iter = dontexamine.find( ed2 );
2236 if ( ed2iter != dontexamine.end() )
2239 dontexamine.erase( ed2iter );
2244 std::map<int, double>::iterator tempit1;
2245 tempit1 = edge_angle.find( ed2 );
2246 if ( tempit1 != edge_angle.end() )
2249 double angle = tempit1->second;
2250 edge_angle.erase( ed2 );
2251 std::multimap<double, int>::iterator tempit2 = angle_edge.lower_bound( angle );
2252 while ( tempit2->second != ed2 )
2256 angle_edge.erase( tempit2 );
2260 if ( angle2 < mintol && !twoforcededges2 )
2262 edge_angle.insert( std::make_pair( ed2, angle2 ) );
2263 angle_edge.insert( std::make_pair( angle2, ed2 ) );
2267 QSet<int>::iterator ed3iter = dontexamine.find( ed3 );
2268 if ( ed3iter != dontexamine.end() )
2271 dontexamine.erase( ed3iter );
2276 std::map<int, double>::iterator tempit1;
2277 tempit1 = edge_angle.find( ed3 );
2278 if ( tempit1 != edge_angle.end() )
2281 double angle = tempit1->second;
2282 edge_angle.erase( ed3 );
2283 std::multimap<double, int>::iterator tempit2 = angle_edge.lower_bound( angle );
2284 while ( tempit2->second != ed3 )
2288 angle_edge.erase( tempit2 );
2292 if ( angle3 < mintol && !twoforcededges3 )
2294 edge_angle.insert( std::make_pair( ed3, angle3 ) );
2295 angle_edge.insert( std::make_pair( angle3, ed3 ) );
2300 while ( actedge != pointingedge );
2306 for ( QSet<int>::iterator it = dontexamine.begin(); it != dontexamine.end(); ++it )
2308 QgsDebugMsg( QString(
"edge nr. %1 is in dontexamine" ).arg( *it ) );
2330 QgsPoint *ptc =
mPointVector[mHalfEdge[mHalfEdge[mHalfEdge[edge]->getNext()]->getNext()]->getPoint()];
2331 QgsPoint *ptd =
mPointVector[mHalfEdge[mHalfEdge[mHalfEdge[edge]->getDual()]->getNext()]->getPoint()];
2355 if ( poly->count() == 3 )
2361 QList<int>::const_iterator iterator = ++( poly->constBegin() );
2363 int distedge = ( *iterator );
2364 int nextdistedge =
mHalfEdge[( *iterator )]->getNext();
2367 while ( iterator != --( poly->constEnd() ) )
2371 distedge = ( *iterator );
2372 nextdistedge = mHalfEdge[( *iterator )]->getNext();
2378 if ( nextdistedge == ( *( --poly->end() ) ) )
2380 int inserta = free->first();
2381 int insertb =
mHalfEdge[inserta]->getDual();
2384 mHalfEdge[inserta]->setNext( ( poly->at( 1 ) ) );
2386 mHalfEdge[insertb]->setNext( nextdistedge );
2388 mHalfEdge[distedge]->setNext( inserta );
2389 mHalfEdge[mainedge]->setNext( insertb );
2392 for ( iterator = ( ++( poly->constBegin() ) ); ( *iterator ) != nextdistedge; ++iterator )
2394 polya.append( ( *iterator ) );
2396 polya.prepend( inserta );
2400 for ( iterator = polya.begin(); iterator != polya.end(); ++iterator )
2409 else if ( distedge == ( *( ++poly->begin() ) ) )
2411 int inserta = free->first();
2412 int insertb =
mHalfEdge[inserta]->getDual();
2415 mHalfEdge[inserta]->setNext( ( poly->at( 2 ) ) );
2417 mHalfEdge[insertb]->setNext( mainedge );
2419 mHalfEdge[distedge]->setNext( insertb );
2420 mHalfEdge[( *( --poly->end() ) )]->setNext( inserta );
2423 iterator = poly->constBegin();
2425 while ( iterator != poly->constEnd() )
2427 polya.append( ( *iterator ) );
2430 polya.prepend( inserta );
2437 int inserta = free->first();
2438 int insertb =
mHalfEdge[inserta]->getDual();
2441 int insertc = free->first();
2442 int insertd =
mHalfEdge[insertc]->getDual();
2445 mHalfEdge[inserta]->setNext( ( poly->at( 1 ) ) );
2449 mHalfEdge[insertc]->setNext( nextdistedge );
2451 mHalfEdge[insertd]->setNext( mainedge );
2454 mHalfEdge[distedge]->setNext( inserta );
2455 mHalfEdge[mainedge]->setNext( insertb );
2456 mHalfEdge[( *( --poly->end() ) )]->setNext( insertc );
2462 for ( iterator = ++( poly->constBegin() ); ( *iterator ) != nextdistedge; ++iterator )
2464 polya.append( ( *iterator ) );
2466 polya.prepend( inserta );
2469 while ( iterator != poly->constEnd() )
2471 polyb.append( ( *iterator ) );
2474 polyb.prepend( insertc );
2501 QgsDebugMsg( QString(
"warning, instability detected: Point coordinates: %1//%2" ).arg( x ).arg( y ) );
2535 actedge =
mHalfEdge[actedge]->getDual();
2541 actedge =
mHalfEdge[actedge]->getNext();
2558 if ( numinstabs > 0 )
2573 bool DualEdgeTriangulation::readFromTAFF( QString filename )
2575 QApplication::setOverrideCursor( QCursor( Qt::WaitCursor ) );
2577 QFile file( filename );
2578 file.open( IO_Raw | IO_ReadOnly );
2579 QBuffer buffer( file.readAll() );
2582 QTextStream textstream( &buffer );
2583 buffer.open( IO_ReadOnly );
2586 int numberofhalfedges;
2590 while ( buff.mid( 0, 4 ) !=
"TRIA" )
2592 buff = textstream.readLine();
2594 while ( buff.mid( 0, 4 ) !=
"NEDG" )
2596 buff = textstream.readLine();
2598 numberofhalfedges = buff.section(
' ', 1, 1 ).toInt();
2602 while ( buff.mid( 0, 4 ) !=
"DATA" )
2607 int nr1, nr2, dual1, dual2, point1, point2, next1, next2, fo1, fo2, b1, b2;
2608 bool forced1, forced2, break1, break2;
2612 QProgressBar *edgebar =
new QProgressBar();
2613 edgebar->setCaption(
"Reading edges…" );
2614 edgebar->setTotalSteps( numberofhalfedges / 2 );
2615 edgebar->setMinimumWidth( 400 );
2616 edgebar->move( 500, 500 );
2619 for (
int i = 0; i < numberofhalfedges / 2; i++ )
2621 if ( i % 1000 == 0 )
2623 edgebar->setProgress( i );
2627 textstream >> point1;
2628 textstream >> next1;
2652 textstream >> point2;
2653 textstream >> next2;
2696 edgebar->setProgress( numberofhalfedges / 2 );
2700 for (
int i = 0; i < numberofhalfedges; i++ )
2707 if ( a != -1 && b != -1 && c != -1 && d != -1 )
2715 while ( buff.mid( 0, 4 ) !=
"POIN" )
2717 buff = textstream.readLine();
2720 while ( buff.mid( 0, 4 ) !=
"NPTS" )
2722 buff = textstream.readLine();
2725 numberofpoints = buff.section(
' ', 1, 1 ).toInt();
2728 while ( buff.mid( 0, 4 ) !=
"DATA" )
2733 QProgressBar *pointbar =
new QProgressBar();
2734 pointbar->setCaption( tr(
"Reading points…" ) );
2735 pointbar->setTotalSteps( numberofpoints );
2736 pointbar->setMinimumWidth( 400 );
2737 pointbar->move( 500, 500 );
2742 for (
int i = 0; i < numberofpoints; i++ )
2744 if ( i % 1000 == 0 )
2746 pointbar->setProgress( i );
2772 else if ( x >
xMax )
2781 else if ( y >
yMax )
2788 pointbar->setProgress( numberofpoints );
2790 QApplication::restoreOverrideCursor();
2794 bool DualEdgeTriangulation::saveToTAFF( QString filename )
const 2796 QFile outputfile( filename );
2797 if ( !outputfile.open( IO_WriteOnly ) )
2799 QMessageBox::warning( 0, tr(
"Warning" ), tr(
"File could not be written." ), QMessageBox::Ok, QMessageBox::NoButton, QMessageBox::NoButton );
2803 QTextStream outstream( &outputfile );
2804 outstream.precision( 9 );
2807 outstream <<
"TRIA" << std::endl << std::flush;
2808 outstream <<
"NEDG " <<
mHalfEdge.count() << std::endl << std::flush;
2809 outstream <<
"PANO 1" << std::endl << std::flush;
2810 outstream <<
"DATA ";
2812 bool *cont =
new bool[
mHalfEdge.count()];
2813 for (
unsigned int i = 0; i <=
mHalfEdge.count() - 1; i++ )
2818 for (
unsigned int i = 0; i <
mHalfEdge.count(); i++ )
2827 outstream << dual <<
" " <<
mHalfEdge[dual]->getPoint() <<
" " <<
mHalfEdge[dual]->getNext() <<
" " <<
mHalfEdge[dual]->getForced() <<
" " <<
mHalfEdge[dual]->getBreak() <<
" ";
2831 outstream << std::endl << std::flush;
2832 outstream << std::endl << std::flush;
2837 outstream <<
"POIN" << std::endl << std::flush;
2839 outstream <<
"PATT 3" << std::endl << std::flush;
2840 outstream <<
"DATA ";
2845 outstream << p->getX() <<
" " << p->getY() <<
" " << p->getZ() <<
" ";
2847 outstream << std::endl << std::flush;
2848 outstream << std::endl << std::flush;
2869 if ( point1 && point2 && point3 )
2872 double dist1, dist2, dist3;
2876 if ( dist1 <= dist2 && dist1 <= dist3 )
2884 else if ( dist2 <= dist1 && dist2 <= dist3 )
2892 else if ( dist3 <= dist1 && dist3 <= dist2 )
2931 if ( point1 && point2 && point3 )
2933 double dist1, dist2, dist3;
2937 if ( dist1 <= dist2 && dist1 <= dist3 )
2944 else if ( dist2 <= dist1 && dist2 <= dist3 )
2951 else if ( dist3 <= dist1 && dist3 <= dist2 )
2958 QList<int> *list =
new QList<int>();
2985 bool *alreadyVisitedEdges =
new bool[
mHalfEdge.size()];
2986 if ( !alreadyVisitedEdges )
2992 for (
int i = 0; i <
mHalfEdge.size(); ++i )
2994 alreadyVisitedEdges[i] =
false;
2997 for (
int i = 0; i <
mHalfEdge.size(); ++i )
3017 QString attributeString;
3022 attributeString = QStringLiteral(
"break line" );
3026 attributeString = QStringLiteral(
"structure line" );
3033 alreadyVisitedEdges[i] =
true;
3036 delete [] alreadyVisitedEdges;
3053 if ( angle2 < minangle )
3058 if ( angle3 < minangle )
3063 if ( angle4 < minangle )
3068 if ( angle5 < minangle )
3073 if ( angle6 < minangle )
3084 if ( position < 0 || position > 1 )
3086 QgsDebugMsg(
"warning, position is not between 0 and 1" );
3095 p->
setZ( zvaluepoint.
z() );
3102 QgsDebugMsg( QString(
"inserting point nr. %1, %2//%3//%4" ).arg(
mPointVector.count() ).arg( p->
x() ).arg( p->
y() ).arg( p->
z() ) );
3106 int dualedge =
mHalfEdge[edge]->getDual();
3143 if (
set.find( edge ) ==
set.
end() )
bool getBreak() const
Returns, whether the HalfEdge belongs to a break line or not.
Triangulation * mDecorator
Pointer to the decorator using this triangulation. It it is used directly, mDecorator equals this...
Use faster inserts, at the cost of updating the passed features to reflect changes made at the provid...
static QgsGeometry fromPolylineXY(const QgsPolylineXY &polyline)
Creates a new LineString geometry from a list of QgsPointXY points.
void setBreakEdgeColor(int r, int g, int b) override
Sets the color of the breaklines.
void triangulatePolygon(QList< int > *poly, QList< int > *free, int mainedge)
Divides a polygon in a triangle and two polygons and calls itself recursively for these two polygons...
int getOppositePoint(int p1, int p2) override
Returns the number of the point opposite to the triangle points p1, p2 (which have to be on a halfedg...
int baseEdgeOfPoint(int point)
Returns the number of an edge which points to the point with number 'point' or -1 if there is an erro...
int getPoint() const
Returns the number of the point at which this HalfEdge points.
int splitHalfEdge(int edge, float position)
Inserts a new point on the halfedge with number 'edge'. The position can have a value from 0 to 1 (e...
void setZ(double z)
Sets the point's z-coordinate.
unsigned int insertEdge(int dual, int next, int point, bool mbreak, bool forced)
Inserts an edge and makes sure, everything is OK with the storage of the edge. The number of the Half...
int mTwiceInsPoint
If a point has been inserted twice, its number is stored in this member.
A class to represent a 2D point.
An interface for objects which accept features via addFeature(s) methods.
QgsPoint * getPoint(int i) const override
Draws the points, edges and the forced lines.
bool halfEdgeBBoxTest(int edge, double xlowleft, double ylowleft, double xupright, double yupright) const
Tests, if the bounding box of the halfedge with index i intersects the specified bounding box...
double yMin
Y-coordinate of the lower left corner of the bounding box.
bool calcPoint(double x, double y, QgsPoint &result) override
Calculates x-, y and z-value of the point on the surface and assigns it to 'result'.
bool ANALYSIS_EXPORT lineIntersection(QgsPoint *p1, QgsPoint *p2, QgsPoint *p3, QgsPoint *p4)
Returns true, if line1 (p1 to p2) and line2 (p3 to p4) intersect. If the lines have an endpoint in co...
int getNumberOfPoints() const override
Returns the number of points.
bool setAttribute(int field, const QVariant &attr)
Set an attribute's value by field index.
SourceType
Describes the type of input data.
void addLine(const QVector< QgsPoint > &points, QgsInterpolator::SourceType lineType) override
Adds a line (e.g.
The feature class encapsulates a single feature including its id, geometry and a list of field/values...
double xMax
X-coordinate of the upper right corner of the bounding box.
void doSwap(unsigned int edge, unsigned int recursiveDeep)
Swaps 'edge' and test recursively for other swaps (delaunay criterion)
bool ANALYSIS_EXPORT inDiametral(QgsPoint *p1, QgsPoint *p2, QgsPoint *point)
Tests, whether 'point' is inside the diametral circle through 'p1' and 'p2'.
unsigned int mUnstableEdge
If an instability occurs in 'baseEdgeOfTriangle', mUnstableEdge is set to the value of the current ed...
bool checkSwap(unsigned int edge, unsigned int recursiveDeep)
Checks, if 'edge' has to be swapped because of the empty circle criterion. If so, doSwap(...
double ANALYSIS_EXPORT angle(QgsPoint *p1, QgsPoint *p2, QgsPoint *p3, QgsPoint *p4)
Calculates the angle between two segments (in 2 dimension, z-values are ignored)
bool getTriangle(double x, double y, QgsPoint &p1, int &n1, QgsPoint &p2, int &n2, QgsPoint &p3, int &n3) override
Finds out in which triangle the point with coordinates x and y is and assigns the numbers of the vert...
void doOnlySwap(unsigned int edge)
Swaps 'edge' and does no recursiv testing.
QVector< HalfEdge * > mHalfEdge
Stores pointers to the HalfEdges.
void setForcedCrossBehavior(Triangulation::ForcedCrossBehavior b) override
Sets the behavior of the triangulation in case of crossing forced lines.
Base class for feedback objects to be used for cancelation of something running in a worker thread...
bool pointInside(double x, double y) override
Returns true, if the point with coordinates x and y is inside the convex hull and false otherwise...
void setEdgeColor(int r, int g, int b) override
Sets the color of the normal edges.
void setTriangleInterpolator(TriangleInterpolator *interpolator) override
Sets an interpolator object.
Class Vector3D represents a 3D-Vector, capable to store x-,y- and z-coordinates in double values...
This is an interface for interpolator classes for triangulations.
double yMax
Y-coordinate of the upper right corner of the bounding box.
void initAttributes(int fieldCount)
Initialize this feature with the given number of fields.
bool getForced() const
Returns, whether the HalfEdge belongs to a constrained edge or not.
virtual bool calcPoint(double x, double y, QgsPoint &result SIP_OUT)=0
Performs a linear interpolation in a triangle and assigns the x-,y- and z-coordinates to point...
bool edgeOnConvexHull(int edge)
Returns true, if a half edge is on the convex hull and false otherwise.
QColor mForcedEdgeColor
Color to paint the forced edges.
void evaluateInfluenceRegion(QgsPoint *point, int edge, QSet< int > &set)
Function needed for the ruppert algorithm. Tests, if point is in the circle through both endpoints of...
double swapMinAngle(int edge) const
Calculates the minimum angle, which would be present, if the specified halfedge would be swapped...
bool saveTriangulation(QgsFeatureSink *sink, QgsFeedback *feedback=nullptr) const override
Saves the triangulation features to a feature sink.
int addPoint(const QgsPoint &p) override
Adds a point to the triangulation.
virtual bool addFeature(QgsFeature &feature, QgsFeatureSink::Flags flags=nullptr)
Adds a single feature to the sink.
~DualEdgeTriangulation() override
bool ANALYSIS_EXPORT circumcenter(QgsPoint *p1, QgsPoint *p2, QgsPoint *p3, QgsPoint *result)
Calculates the center of the circle passing through p1, p2 and p3. Returns true in case of success an...
double ANALYSIS_EXPORT distPointFromLine(QgsPoint *thepoint, QgsPoint *p1, QgsPoint *p2)
Calculates the (2 dimensional) distance from 'thepoint' to the line defined by p1 and p2...
QColor mBreakEdgeColor
Color to paint the breaklines.
Point geometry type, with support for z-dimension and m-values.
int insertForcedSegment(int p1, int p2, QgsInterpolator::SourceType segmentType)
Inserts a forced segment between the points with the numbers p1 and p2 into the triangulation and ret...
void setBreak(bool b)
Sets the break flag.
void setPoint(int p)
Sets the number of point at which this HalfEdge points.
int getDual() const
Returns the number of the dual HalfEdge.
unsigned int mEdgeWithPoint
If an inserted point is exactly on an existing edge, 'baseEdgeOfTriangle' returns -20 and sets the va...
int baseEdgeOfTriangle(const QgsPoint &point)
Returns the number of a HalfEdge from a triangle in which 'point' is in. If the number -10 is returne...
bool swapPossible(unsigned int edge)
Returns true, if it is possible to swap an edge, otherwise false(concave quad or edge on (or outside)...
void performConsistencyTest() override
Performs a consistency check, remove this later.
void setX(double x)
Sets the point's x-coordinate.
Triangulation::ForcedCrossBehavior mForcedCrossBehavior
Member to store the behavior in case of crossing forced segments.
virtual int addPoint(const QgsPoint &point)=0
Adds a point to the triangulation.
void setY(double y)
Sets the point's y-coordinate.
unsigned int mEdgeInside
Number of an edge which does not point to the virtual point. It continuously updated for a fast searc...
The second inserted forced line is snapped to the closest vertice of the first inserted forced line...
TriangleInterpolator * mTriangleInterpolator
Association to an interpolator object.
bool ANALYSIS_EXPORT inCircle(QgsPoint *testp, QgsPoint *p1, QgsPoint *p2, QgsPoint *p3)
Tests, whether 'testp' is inside the circle through 'p1', 'p2' and 'p3'.
QVector< QgsPointXY > QgsPolylineXY
Polyline as represented as a vector of two-dimensional points.
bool isCanceled() const
Tells whether the operation has been canceled already.
bool calcNormal(double x, double y, Vector3D *result) override
Calculates the normal at a point on the surface.
void eliminateHorizontalTriangles() override
Eliminates the horizontal triangles by swapping or by insertion of new points.
void setForcedEdgeColor(int r, int g, int b) override
Sets the color of the forced edges.
void setGeometry(const QgsGeometry &geometry)
Set the feature's geometry.
QList< int > getSurroundingTriangles(int pointno) override
Returns a pointer to a value list with the information of the triangles surrounding (counterclockwise...
static const int MAX_BASE_ITERATIONS
Threshold for the leftOfTest to handle numerical instabilities.
void setDual(int d)
Sets the number of the dual HalfEdge.
QVector< QgsPoint * > mPointVector
Stores pointers to all points in the triangulations (including the points contained in the lines) ...
void setForced(bool f)
Sets the forced flag.
QColor mEdgeColor
Color to paint the normal edges.
double xMin
X-coordinate of the lower left corner of the bounding box.
void ruppertRefinement() override
Adds points to make the triangles better shaped (algorithm of ruppert)
QList< int > * getPointsAroundEdge(double x, double y) override
Returns a value list with the numbers of the four points, which would be affected by an edge swap...
ForcedCrossBehavior
Enumeration describing the behavior, if two forced lines cross.
void setNext(int n)
Sets the number of the next HalfEdge.
virtual bool calcPoint(double x, double y, QgsPoint &result)=0
Calculates x-, y and z-value of the point on the surface and assigns it to 'result'.
double ANALYSIS_EXPORT leftOf(const QgsPoint &thepoint, const QgsPoint *p1, const QgsPoint *p2)
Returns whether 'thepoint' is left or right of the line from 'p1' to 'p2'. Negativ values mean left a...
virtual bool calcNormVec(double x, double y, Vector3D *result SIP_OUT)=0
Calculates the normal vector and assigns it to vec.
unsigned int mEdgeOutside
Number of an edge on the outside of the convex hull. It is updated in method 'baseEdgeOfTriangle' to ...
bool swapEdge(double x, double y) override
Reads the dual edge structure of a taff file.