27static int vertexPositionInFace(
int vertexIndex,
const QgsMeshFace &face )
29 return face.indexOf( vertexIndex );
32static int vertexPositionInFace(
const QgsMesh &mesh,
int vertexIndex,
int faceIndex )
34 if ( faceIndex < 0 || faceIndex >= mesh.
faceCount() )
37 return vertexPositionInFace( vertexIndex, mesh.
face( faceIndex ) );
43 double ux1 = v1.
x() - vc.
x();
44 double uy1 = v1.
y() - vc.
y();
45 double vx1 = v2.
x() - vc.
x();
46 double vy1 = v2.
y() - vc.
y();
48 return ux1 * vy1 - uy1 * vx1;
51static double crossProduct(
int centralVertex,
int vertex1,
int vertex2,
const QgsMesh &mesh )
57 return crossProduct( vc, v1, v2 );
62 : mFaces( topologicalMesh.mMesh->faces )
63 , mFacesNeighborhood( topologicalMesh.mFacesNeighborhood )
64 , mVertexIndex( vertexIndex )
66 if ( vertexIndex >= 0 && vertexIndex < topologicalMesh.mMesh->vertexCount() )
68 mCurrentFace = topologicalMesh.mVertexToFace[vertexIndex];
69 mIsValid = vertexPositionInFace( *topologicalMesh.
mesh(), vertexIndex, mCurrentFace ) != -1;
77 mLastValidFace = mCurrentFace;
81 : mFaces( topologicalFaces.mFaces )
82 , mFacesNeighborhood( topologicalFaces.mFacesNeighborhood )
83 , mVertexIndex( vertexIndex )
85 const QgsMeshFace &face = topologicalFaces.mFaces.at( faceIndex );
86 mIsValid = vertexPositionInFace( vertexIndex, face ) != -1;
88 mCurrentFace = faceIndex;
89 mLastValidFace = mCurrentFace;
93 : mFaces( topologicalFaces.mFaces )
94 , mFacesNeighborhood( topologicalFaces.mFacesNeighborhood )
95 , mVertexIndex( vertexIndex )
97 if ( topologicalFaces.mVerticesToFace.contains( vertexIndex ) )
98 mCurrentFace = topologicalFaces.mVerticesToFace.values( vertexIndex ).first();
99 mLastValidFace = mCurrentFace;
100 mIsValid = mCurrentFace != -1;
105 if ( mCurrentFace == -1 )
106 mCurrentFace = mLastValidFace;
109 int currentPos = positionInCurrentFace();
110 Q_ASSERT( currentPos != -1 );
114 mLastValidFace = mCurrentFace;
115 mCurrentFace = mFacesNeighborhood.at( mCurrentFace ).at( ( currentPos + faceSize - 1 ) %
currentFace.count() );
123 if ( mCurrentFace == -1 )
124 mCurrentFace = mLastValidFace;
127 int currentPos = positionInCurrentFace();
128 Q_ASSERT( currentPos != -1 );
132 mLastValidFace = mCurrentFace;
133 mCurrentFace = mFacesNeighborhood.at( mCurrentFace ).at( ( currentPos ) % faceSize );
146 if ( mCurrentFace != -1 )
147 return mFaces.at( mCurrentFace );
157 if ( mCurrentFace == -1 )
158 mCurrentFace = mLastValidFace;
160 int firstFace = mCurrentFace;
163 if ( mCurrentFace == firstFace )
174 if ( mCurrentFace == -1 )
175 mCurrentFace = mLastValidFace;
177 int firstFace = mCurrentFace;
180 if ( mCurrentFace == firstFace )
188 if ( mCurrentFace == -1 )
193 if ( face.isEmpty() )
196 int vertexPosition = vertexPositionInFace( mVertexIndex,
currentFace() );
198 if ( vertexPosition == -1 )
201 return face.at( ( vertexPosition + 1 ) % face.count() );
206 if ( mCurrentFace == -1 )
211 if ( face.isEmpty() )
214 int vertexPosition = vertexPositionInFace( mVertexIndex,
currentFace() );
216 if ( vertexPosition == -1 )
219 return face.at( ( vertexPosition - 1 + face.count() ) % face.count() );
233 if ( mCurrentFace != -1 )
234 ret.append( mCurrentFace );
279int QgsMeshVertexCirculator::positionInCurrentFace()
const
281 if ( mCurrentFace < 0 || mCurrentFace >= mFaces.count() )
284 return vertexPositionInFace( mVertexIndex, mFaces.at( mCurrentFace ) );
294 for (
int i = 0; i < changes.
mFacesToAdd.count(); ++i )
297 for (
int boundary : topologicalFaces.mBoundaries )
300 if ( mVertexToFace.at( boundary ) == -1 )
303 const QList<int> &linkedFaces = topologicalFaces.mVerticesToFace.values( boundary );
304 for (
int linkedFace : linkedFaces )
310 if ( mVertexToFace.at( oppositeVertexForNewFace ) == -1 )
318 int boundaryPositionInNewFace = vertexPositionInFace( boundary, newFaceBoundary );
320 if ( oppositeVertexForMeshFace != oppositeVertexForNewFace )
332 boundaryPositionInMeshFace,
342 for (
int f = 0; f < changes.
mFacesToAdd.count(); ++f )
343 for (
int n = 0; n < changes.
mFacesToAdd.at( f ).count(); ++n )
345 changes.
mFacesNeighborhoodToAdd[f][n] = changes.addedFaceIndexInMesh( topologicalFaces.mFacesNeighborhood.at( f ).at( n ) );
347 const QList<int> &verticesToFaceToChange = topologicalFaces.mVerticesToFace.keys();
348 for (
const int vtc : verticesToFaceToChange )
349 if ( mVertexToFace.at( vtc ) == -1 )
351 mVertexToFace.at( vtc ),
352 changes.addedFaceIndexInMesh( topologicalFaces.mVerticesToFace.values( vtc ).first() )
355 applyChanges( changes );
362 int initialVerticesCount = mMesh->
vertices.count();
367 mVertexToFace.resize( newSize );
373 mMesh->
faces.resize( newSize );
374 mFacesNeighborhood.resize( newSize );
380 mFacesNeighborhood[changes.removedFaceIndexInMesh( i )] =
FaceNeighbors();
386 if ( mVertexToFace.at( vertexIndex ) == -1 )
387 dereferenceAsFreeVertex( vertexIndex );
389 mVertexToFace[vertexIndex] = -1;
397 referenceAsFreeVertex( initialVerticesCount + i );
400 for (
int i = 0; i < changes.
mFacesToAdd.count(); ++i )
402 mMesh->
faces[changes.addedFaceIndexInMesh( i )] = changes.
mFacesToAdd.at( i );
408 const int faceIndex = neighborChange.at( 0 );
409 const int positionInFace = neighborChange.at( 1 );
410 const int valueToApply = neighborChange.at( 3 );
411 mFacesNeighborhood[faceIndex][positionInFace] = valueToApply;
416 int vertexIndex = vertexToFaceChange.at( 0 );
417 mVertexToFace[vertexToFaceChange.at( 0 )] = vertexToFaceChange.at( 2 );
419 if ( vertexToFaceChange.at( 2 ) == -1 &&
420 vertexToFaceChange.at( 1 ) != -1 &&
421 !mMesh->
vertices.at( vertexIndex ).isEmpty() )
422 referenceAsFreeVertex( vertexIndex );
424 if ( vertexToFaceChange.at( 1 ) == -1 && vertexToFaceChange.at( 2 ) != -1 )
425 dereferenceAsFreeVertex( vertexIndex );
436 mMesh->
vertices[vertexIndex].setX( pt.
x() );
437 mMesh->
vertices[vertexIndex].setY( pt.
y() );
446 const int faceIndex = neighborChange.at( 0 );
447 const int positionInFace = neighborChange.at( 1 );
448 const int valueToApply = neighborChange.at( 2 );
449 mFacesNeighborhood[faceIndex][positionInFace] = valueToApply;
463 if ( mVertexToFace.at( vertexIndex ) == -1 )
464 referenceAsFreeVertex( vertexIndex );
468 for (
int i = 0; i < verticesToFaceChangesCount; ++i )
470 const std::array<int, 3> vertexToFaceChange = changes.
mVerticesToFaceChanges.at( verticesToFaceChangesCount - i - 1 );
471 int vertexIndex = vertexToFaceChange.at( 0 );
472 mVertexToFace[vertexIndex] = vertexToFaceChange.at( 1 );
474 if ( vertexToFaceChange.at( 2 ) == -1 && vertexToFaceChange.at( 1 ) != -1 )
475 dereferenceAsFreeVertex( vertexIndex );
477 if ( vertexToFaceChange.at( 1 ) == -1 &&
478 vertexToFaceChange.at( 2 ) != -1 &&
480 referenceAsFreeVertex( vertexIndex );
486 mMesh->
faces.resize( newSize );
487 mFacesNeighborhood.resize( newSize );
494 for (
int i = newSize; i < mMesh->
vertexCount(); ++i )
495 if ( mVertexToFace.at( i ) == -1 )
496 dereferenceAsFreeVertex( i );
499 mVertexToFace.resize( newSize );
510 mMesh->
vertices[vertexIndex].setX( pt.
x() );
511 mMesh->
vertices[vertexIndex].setY( pt.
y() );
521QSet<int> QgsTopologicalMesh::concernedFacesBy(
const QList<int> &faceIndexes )
const
524 for (
const int faceIndex : faceIndexes )
527 for (
int i = 0; i < face.count(); ++i )
530 faces.unite( QSet< int >( around.begin(), around.end() ) );
536void QgsTopologicalMesh::dereferenceAsFreeVertex(
int vertexIndex )
538 mFreeVertices.remove( vertexIndex );
541void QgsTopologicalMesh::referenceAsFreeVertex(
int vertexIndex )
545 mFreeVertices.insert( vertexIndex );
550 for (
int faceIndex = 0 ; faceIndex < mMesh->
faces.count( ); ++faceIndex )
553 const FaceNeighbors &neighborhood = mFacesNeighborhood.at( faceIndex );
554 if ( face.count() != neighborhood.count() )
556 for (
int i = 0; i < face.count(); ++i )
558 int vertexIndex = face.at( i );
560 if ( mVertexToFace.at( vertexIndex ) == -1 )
563 int neighborIndex = neighborhood.at( i );
564 if ( neighborIndex != -1 )
567 if ( neighborFace.isEmpty() )
569 int neighborSize = neighborFace.size();
570 const FaceNeighbors &neighborhoodOfNeighbor = mFacesNeighborhood.at( neighborIndex );
571 int posInNeighbor = vertexPositionInFace( *mMesh, vertexIndex, neighborIndex );
572 if ( neighborhoodOfNeighbor.isEmpty() || neighborhoodOfNeighbor.at( ( posInNeighbor + neighborSize - 1 ) % neighborSize ) != faceIndex )
578 for (
int vertexIndex = 0; vertexIndex < mMesh->
vertexCount(); ++vertexIndex )
580 if ( mVertexToFace.at( vertexIndex ) != -1 )
582 if ( !mMesh->
face( mVertexToFace.at( vertexIndex ) ).contains( vertexIndex ) )
608 if ( vertexIndex < 0 || vertexIndex >= mMesh->
vertexCount() )
610 return mVertexToFace.at( vertexIndex );
625 if ( vertexIndex < 0 || vertexIndex >= mMesh->
vertexCount() )
628 if ( mMesh->
vertices.at( vertexIndex ).isEmpty() )
631 return mVertexToFace.at( vertexIndex ) == -1;
636 return QList<int>( mFreeVertices.begin(), mFreeVertices.end() );
641 int size = vertices.size();
643 for (
int i = 0; i < size; ++i )
646 int iv1 = ( i + 1 ) % size;
647 int iv2 = ( i + 2 ) % size;
662 double crossProd = crossProduct( v1, v0, v2 );
663 if ( direction != 0 && crossProd * direction < 0 )
665 clockwise = direction > 0;
668 else if ( crossProd == 0 )
670 clockwise = direction > 0;
673 else if ( direction == 0 )
674 direction = crossProd / std::fabs( crossProd );
677 clockwise = direction > 0;
686 int faceSize = face.count();
690 QVector<QgsMeshVertex> vertices( face.size() );
692 for (
int i = 0; i < faceSize; ++i )
701 bool clockwise =
false;
708 for (
int i = 0; i < faceSize / 2; ++i )
711 face[i] = face.at( faceSize - i - 1 );
712 face[faceSize - i - 1] = temp;
721 QVector<int> oldToNewIndex( mMesh->
vertices.count(), -1 );
725 while ( oldIndex < verticesTotalCount )
733 oldToNewIndex[oldIndex] = newIndex;
734 if ( oldIndex != newIndex )
736 oldToNewIndex[oldIndex] = newIndex;
746 int facesTotalCount = mMesh->
faceCount();
747 while ( oldIndex < facesTotalCount )
749 if ( mMesh->
face( oldIndex ).isEmpty() )
753 if ( oldIndex != newIndex )
754 mMesh->
faces[newIndex] = mMesh->
faces[oldIndex];
756 for (
int i = 0; i < face.count(); ++i )
757 face[i] = oldToNewIndex[face.at( i )];
763 mMesh->
faces.resize( newIndex );
765 mVertexToFace.clear();
766 mFacesNeighborhood.clear();
771 QVector<int> oldToNewVerticesIndexes;
772 if ( !renumberVertices( oldToNewVerticesIndexes ) )
776 QVector<int> oldToNewFacesIndexes;
778 if ( !renumberFaces( oldToNewFacesIndexes ) )
783 QVector<QgsMeshVertex> tempVertices( mMesh->
vertices.count() );
784 for (
int i = 0; i < oldToNewVerticesIndexes.count(); ++i )
786 tempVertices[oldToNewVerticesIndexes.at( i )] = mMesh->
vertex( i );
790 QVector<QgsMeshFace> tempFaces( mMesh->
faces.count() );
791 for (
int i = 0; i < oldToNewFacesIndexes.count(); ++i )
793 tempFaces[oldToNewFacesIndexes.at( i )] = mMesh->
face( i );
795 QgsMeshFace &face = tempFaces[oldToNewFacesIndexes.at( i )];
797 for (
int fi = 0; fi < face.count(); ++fi )
799 face[fi] = oldToNewVerticesIndexes.at( face.at( fi ) );
803 mMesh->
faces = tempFaces;
809bool QgsTopologicalMesh::renumberVertices( QVector<int> &oldToNewIndex )
const
811 std::vector<QgsMeshVertexCirculator> circulators;
812 circulators.reserve( mMesh->
vertices.count() );
813 int minDegree = std::numeric_limits<int>::max();
814 int minDegreeVertex = -1;
817 QSet<int> nonThreadedVertex;
818 oldToNewIndex = QVector<int> ( mMesh->
vertexCount(), -1 );
821 circulators.emplace_back( *
this, i );
823 if ( circulators.back().degree() < minDegree )
825 minDegreeVertex = circulators.size() - 1;
826 minDegree = circulator.
degree();
828 nonThreadedVertex.insert( i );
831 auto sortedNeighbor = [ = ]( QList<int> &neighbors,
int index )
845 int degree = circulators.at( neighborIndex ).degree();
846 QList<int>::Iterator it = neighbors.begin();
847 while ( it != neighbors.end() )
849 if ( degree <= circulators.at( *it ).degree() )
851 neighbors.insert( it, neighborIndex );
856 if ( it == neighbors.end() )
857 neighbors.append( neighborIndex );
863 int currentVertex = minDegreeVertex;
864 nonThreadedVertex.remove( minDegreeVertex );
866 while ( newIndex < mMesh->vertexCount() )
868 if ( oldToNewIndex[currentVertex] == -1 )
869 oldToNewIndex[currentVertex] = newIndex++;
871 if ( circulators.at( currentVertex ).isValid() )
873 QList<int> neighbors;
874 sortedNeighbor( neighbors, currentVertex );
876 for (
const int i : std::as_const( neighbors ) )
877 if ( oldToNewIndex.at( i ) == -1 && nonThreadedVertex.contains( i ) )
880 nonThreadedVertex.remove( i );
884 if ( queue.isEmpty() )
886 if ( nonThreadedVertex.isEmpty() && newIndex < mMesh->vertexCount() )
889 const QList<int> remainingVertex( nonThreadedVertex.constBegin(), nonThreadedVertex.constEnd() );
890 int minRemainingDegree = std::numeric_limits<int>::max();
891 int minRemainingVertex = -1;
892 for (
const int i : remainingVertex )
894 int degree = circulators.at( i ).degree();
895 if ( degree < minRemainingDegree )
897 minRemainingDegree = degree;
898 minRemainingVertex = i;
901 currentVertex = minRemainingVertex;
902 nonThreadedVertex.remove( currentVertex );
906 currentVertex = queue.dequeue();
913bool QgsTopologicalMesh::renumberFaces( QVector<int> &oldToNewIndex )
const
916 QSet<int> nonThreadedFaces;
918 oldToNewIndex = QVector<int>( mMesh->
faceCount(), -1 );
920 QVector<int> faceDegrees( mMesh->
faceCount(), 0 );
922 int minDegree = std::numeric_limits<int>::max();
923 int minDegreeFace = -1;
924 for (
int faceIndex = 0; faceIndex < mMesh->
faceCount(); ++faceIndex )
926 const FaceNeighbors &neighbors = mFacesNeighborhood.at( faceIndex );
929 for (
int n = 0; n < neighbors.size(); ++n )
931 if ( neighbors.at( n ) != -1 )
935 if ( degree < minDegree )
938 minDegreeFace = faceIndex;
941 faceDegrees[faceIndex] = degree;
942 nonThreadedFaces.insert( faceIndex );
946 int currentFace = minDegreeFace;
947 nonThreadedFaces.remove( minDegreeFace );
949 auto sortedNeighbor = [
this, faceDegrees]( QList<int> &neighbors,
int index )
951 const FaceNeighbors &neighborhood = mFacesNeighborhood.at( index );
953 for (
int i = 0; i < neighborhood.count(); ++i )
955 int neighborIndex = neighborhood.at( i );
956 if ( neighborIndex == -1 )
959 int degree = faceDegrees.at( neighborIndex );
960 if ( neighbors.isEmpty() )
961 neighbors.append( neighborIndex );
964 QList<int>::Iterator it = neighbors.begin();
965 while ( it != neighbors.end() )
967 if ( degree <= faceDegrees.at( *it ) )
969 neighbors.insert( it, neighborIndex );
974 if ( it == neighbors.end() )
975 neighbors.append( neighborIndex );
980 while ( newIndex < mMesh->faceCount() )
982 if ( oldToNewIndex[currentFace] == -1 )
983 oldToNewIndex[currentFace] = newIndex++;
985 QList<int> neighbors;
986 sortedNeighbor( neighbors, currentFace );
988 for (
const int i : std::as_const( neighbors ) )
989 if ( oldToNewIndex.at( i ) == -1 && nonThreadedFaces.contains( i ) )
992 nonThreadedFaces.remove( i );
995 if ( queue.isEmpty() )
997 if ( nonThreadedFaces.isEmpty() && newIndex < mMesh->faceCount() )
1000 const QList<int> remainingFace( nonThreadedFaces.constBegin(), nonThreadedFaces.constEnd() );
1001 int minRemainingDegree = std::numeric_limits<int>::max();
1002 int minRemainingFace = -1;
1003 for (
const int i : remainingFace )
1005 int degree = faceDegrees.at( i );
1006 if ( degree < minRemainingDegree )
1008 minRemainingDegree = degree;
1009 minRemainingFace = i;
1012 currentFace = minRemainingFace;
1013 nonThreadedFaces.remove( currentFace );
1017 currentFace = queue.dequeue();
1032 return mFacesToRemove;
1037 return mFaceIndexesToRemove;
1042 return mVerticesToAdd;
1047 return mChangeCoordinateVerticesIndexes;
1057 return mNewXYValues;
1062 return mOldXYValues;
1067 return mNativeFacesIndexesGeometryChanged;
1072 return ( mFaceIndexesToRemove.isEmpty() &&
1073 mFacesToAdd.isEmpty() &&
1074 mFacesNeighborhoodToAdd.isEmpty() &&
1075 mFacesToRemove.isEmpty() &&
1076 mFacesNeighborhoodToRemove.isEmpty() &&
1077 mNeighborhoodChanges.isEmpty() &&
1078 mVerticesToAdd.isEmpty() &&
1079 mVertexToFaceToAdd.isEmpty() &&
1080 mVerticesToRemoveIndexes.isEmpty() &&
1081 mRemovedVertices.isEmpty() &&
1082 mVerticesToFaceRemoved.isEmpty() &&
1083 mVerticesToFaceChanges.isEmpty() &&
1084 mChangeCoordinateVerticesIndexes.isEmpty() &&
1085 mNewZValues.isEmpty() &&
1086 mOldZValues.isEmpty() &&
1087 mNewXYValues.isEmpty() &&
1088 mOldXYValues.isEmpty() &&
1089 mNativeFacesIndexesGeometryChanged.isEmpty() );
1094 return mVerticesToRemoveIndexes;
1097int QgsTopologicalMesh::Changes::addedFaceIndexInMesh(
int internalIndex )
const
1099 if ( internalIndex == -1 )
1102 return internalIndex + mAddedFacesFirstIndex;
1105int QgsTopologicalMesh::Changes::removedFaceIndexInMesh(
int internalIndex )
const
1107 if ( internalIndex == -1 )
1110 return mFaceIndexesToRemove.at( internalIndex );
1115 mAddedFacesFirstIndex = 0;
1116 mFaceIndexesToRemove.clear();
1117 mFacesToAdd.clear();
1118 mFacesNeighborhoodToAdd.clear();
1119 mFacesToRemove.clear();
1120 mFacesNeighborhoodToRemove.clear();
1121 mNeighborhoodChanges.clear();
1123 mVerticesToAdd.clear();
1124 mVertexToFaceToAdd.clear();
1125 mVerticesToRemoveIndexes.clear();
1126 mRemovedVertices.clear();
1127 mVerticesToFaceRemoved.clear();
1128 mVerticesToFaceChanges.clear();
1130 mChangeCoordinateVerticesIndexes.clear();
1131 mNewZValues.clear();
1132 mOldZValues.clear();
1133 mNewXYValues.clear();
1134 mOldXYValues.clear();
1135 mNativeFacesIndexesGeometryChanged.clear();
1145 mVertexToFace.append( -1 );
1146 referenceAsFreeVertex( mMesh->
vertices.count() - 1 );
1152static double vertexPolygonOrientation(
const QgsMesh &
mesh,
const QList<int> &vertexIndexes )
1154 if ( vertexIndexes.count() < 3 )
1157 int hullDomainVertexPos = -1;
1158 double xMin = std::numeric_limits<double>::max();
1159 double yMin = std::numeric_limits<double>::max();
1160 for (
int i = 0; i < vertexIndexes.count(); ++i )
1163 if ( xMin >= vertex.
x() && yMin > vertex.
y() )
1165 hullDomainVertexPos = i;
1171 if ( hullDomainVertexPos >= 0 )
1173 int iv1 = vertexIndexes.at( ( hullDomainVertexPos - 1 + vertexIndexes.count() ) % vertexIndexes.count() );
1174 int iv2 = vertexIndexes.at( ( hullDomainVertexPos + 1 ) % vertexIndexes.count() );
1175 int ivc = vertexIndexes.at( ( hullDomainVertexPos ) );
1176 double cp = crossProduct( ivc, iv1, iv2,
mesh );
1185 if ( vertexIndex >= mVertexToFace.count() )
1188 if ( mVertexToFace.at( vertexIndex ) == -1 )
1194 dereferenceAsFreeVertex( vertexIndex );
1202 QList<int> boundariesVertexIndex;
1203 QList<int> associateFaceToBoundaries;
1204 QList<int> removedFacesIndexes;
1205 QSet<int> boundaryInGlobalMesh;
1211 Q_ASSERT( !mMesh->
vertices.at( boundariesVertexIndex.last() ).isEmpty() );
1213 associateFaceToBoundaries.append( mFacesNeighborhood.at( circulator.
currentFaceIndex() ).at(
1214 vertexPositionInFace( boundariesVertexIndex.last(), currentFace ) ) );
1216 if ( currentFace.count() > 3 )
1218 int posInface = vertexPositionInFace( vertexIndex, currentFace );
1219 for (
int i = 2; i < currentFace.count() - 1; ++i )
1221 boundariesVertexIndex.append( currentFace.at( ( posInface + i ) % currentFace.count() ) );
1222 Q_ASSERT( !mMesh->
vertices.at( boundariesVertexIndex.last() ).isEmpty() );
1223 associateFaceToBoundaries.append( mFacesNeighborhood.at( circulator.
currentFaceIndex() ).at(
1224 vertexPositionInFace( boundariesVertexIndex.last(), currentFace ) ) );
1230 bool boundaryFill =
false;
1233 boundaryFill =
true;
1237 boundariesVertexIndex.append( lastVertexIndex );
1246 boundaryFill =
false;
1249 associateFaceToBoundaries.append( -1 );
1251 for (
const int index : std::as_const( boundariesVertexIndex ) )
1254 boundaryInGlobalMesh.insert( index );
1258 int currentVertexToFace = mVertexToFace.at( vertexIndex );
1262 QList<QList<int>> holes;
1263 QList<QList<int>> associateMeshFacesToHoles;
1265 bool cancelOperation =
false;
1273 int finalPos = boundariesVertexIndex.count() - 1;
1274 QList<int> uncoveredVertex;
1276 QList<int> partToCheck = boundariesVertexIndex.mid( startPos, finalPos - startPos + 1 );
1277 QList<int> associateFacePart = associateFaceToBoundaries.mid( startPos, finalPos - startPos + 1 );
1278 while ( startPos < finalPos && !partToCheck.isEmpty() )
1281 int secondPos = partToCheck.count() - 1;
1282 const QgsPoint &closingSegmentExtremety1 = mMesh->
vertex( partToCheck.at( 0 ) );
1283 const QgsPoint &closingSegmentExtremety2 = mMesh->
vertex( partToCheck.last() );
1284 bool isEdgeIntersect =
false;
1285 for (
int i = 1; i < secondPos - 1; ++i )
1289 bool isLineIntersection;
1292 if ( isEdgeIntersect )
1296 int index = partToCheck.at( 0 );
1297 if ( boundaryInGlobalMesh.contains( index ) && index != boundariesVertexIndex.at( 0 ) )
1299 cancelOperation =
true;
1305 if ( isEdgeIntersect || vertexPolygonOrientation( *mMesh, partToCheck ) >= 0 )
1307 partToCheck.removeLast();
1308 associateFacePart.removeAt( associateFacePart.count() - 2 );
1309 if ( partToCheck.count() == 1 )
1311 uncoveredVertex.append( index );
1312 startPos = startPos + 1;
1313 partToCheck = boundariesVertexIndex.mid( startPos, finalPos - startPos + 1 );
1314 associateFacePart = associateFaceToBoundaries.mid( startPos, finalPos - startPos + 1 );
1320 holes.append( partToCheck );
1321 associateMeshFacesToHoles.append( associateFacePart );
1323 startPos = startPos + partToCheck.count() - 1;
1324 uncoveredVertex.append( partToCheck.at( 0 ) );
1325 partToCheck = boundariesVertexIndex.mid( startPos, finalPos - startPos + 1 );
1326 associateFacePart = associateFaceToBoundaries.mid( startPos, finalPos - startPos + 1 );
1332 holes.append( boundariesVertexIndex );
1333 associateMeshFacesToHoles.append( associateFaceToBoundaries );
1336 if ( cancelOperation )
1342 Q_ASSERT( holes.count() == associateMeshFacesToHoles.count() );
1348 dereferenceAsFreeVertex( vertexIndex );
1350 mVertexToFace[vertexIndex] = -1;
1353 for (
int h = 0; h < holes.count(); ++h )
1355 const QList<int> &holeVertices = holes.at( h );
1356 const QList<int> &associateMeshFacesToHole = associateMeshFacesToHoles.at( h );
1357 QHash<p2t::Point *, int> mapPoly2TriPointToVertex;
1358 std::vector<p2t::Point *> holeToFill( holeVertices.count() );
1361 for (
int i = 0; i < holeVertices.count(); ++i )
1364 holeToFill[i] =
new p2t::Point( vertex.
x(), vertex.
y() );
1365 mapPoly2TriPointToVertex.insert( holeToFill[i], holeVertices.at( i ) );
1368 std::unique_ptr<p2t::CDT> cdt(
new p2t::CDT( holeToFill ) );
1371 std::vector<p2t::Triangle *> triangles = cdt->GetTriangles();
1372 QVector<QgsMeshFace> newFaces( triangles.size() );
1373 for (
size_t i = 0; i < triangles.size(); ++i )
1377 for (
int j = 0; j < 3; j++ )
1379 int vertInd = mapPoly2TriPointToVertex.value( triangles.at( i )->GetPoint( j ), -1 );
1380 if ( vertInd == -1 )
1381 throw std::exception();
1382 Q_ASSERT( !mMesh->
vertices.at( vertInd ).isEmpty() );
1390 throw std::exception();
1391 int newFaceIndexStartIndex = mMesh->
faceCount();
1398 const QList<int> &verticesToFaceToChange = topologicalFaces.mVerticesToFace.keys();
1399 for (
const int vtc : verticesToFaceToChange )
1400 if ( mVertexToFace.at( vtc ) == -1 )
1402 mVertexToFace.at( vtc ),
1403 addChanges.addedFaceIndexInMesh( topologicalFaces.mVerticesToFace.values( vtc ).first() )
1408 for (
int i = 0; i < topologicalFaces.mFaces.count(); ++i )
1410 FaceNeighbors &faceNeighbors = addChanges.mFacesNeighborhoodToAdd[i];
1411 faceNeighbors = topologicalFaces.mFacesNeighborhood.at( i );
1412 for (
int n = 0; n < faceNeighbors.count(); ++n )
1414 if ( faceNeighbors.at( n ) != -1 )
1415 faceNeighbors[n] += newFaceIndexStartIndex;
1420 for (
int i = 0 ; i < holeVertices.count(); ++i )
1422 int vertexHoleIndex = holeVertices.at( i );
1423 int meshFaceBoundaryIndex = associateMeshFacesToHole.at( i );
1428 int newFaceBoundaryIndexInMesh = circulator.
currentFaceIndex() + newFaceIndexStartIndex;
1430 int positionInNewFaces = vertexPositionInFace( vertexHoleIndex, newFace );
1432 if ( meshFaceBoundaryIndex != -1 )
1435 int positionInMeshFaceBoundary = vertexPositionInFace( *mMesh, vertexHoleIndex, meshFaceBoundaryIndex );
1436 positionInMeshFaceBoundary = ( positionInMeshFaceBoundary - 1 + meshFace.count() ) % meshFace.count();
1438 addChanges.mNeighborhoodChanges.append( {meshFaceBoundaryIndex, positionInMeshFaceBoundary, -1, newFaceBoundaryIndexInMesh} );
1441 addChanges.mFacesNeighborhoodToAdd[newFaceBoundaryLocalIndex][positionInNewFaces] = meshFaceBoundaryIndex;
1446 changes.
mFacesToAdd.append( addChanges.mFacesToAdd );
1449 for (
const std::array<int, 4> &neighborChangeToAdd : std::as_const( addChanges.mNeighborhoodChanges ) )
1451 bool merged =
false;
1454 if ( existingNeighborChange.at( 0 ) == neighborChangeToAdd.at( 0 ) &&
1455 existingNeighborChange.at( 1 ) == neighborChangeToAdd.at( 1 ) )
1458 Q_ASSERT( existingNeighborChange.at( 3 ) == neighborChangeToAdd.at( 2 ) );
1459 existingNeighborChange[3] = neighborChangeToAdd.at( 3 );
1466 for (
const std::array<int, 3> &verticesToFaceToAdd : std::as_const( addChanges.mVerticesToFaceChanges ) )
1468 bool merged =
false;
1471 if ( existingVerticesToFace.at( 0 ) == verticesToFaceToAdd.at( 0 ) )
1474 Q_ASSERT( existingVerticesToFace.at( 2 ) == verticesToFaceToAdd.at( 1 ) );
1475 existingVerticesToFace[2] = verticesToFaceToAdd.at( 2 );
1482 qDeleteAll( holeToFill );
1486 qDeleteAll( holeToFill );
1490 changes.mAddedFacesFirstIndex = oldFacesCount;
1494 changes.mAddedFacesFirstIndex = oldFacesCount;
1501 QSet<int> facesIndex;
1503 for (
int vertexIndex : vertices )
1506 facesIndex.unite( QSet< int >( faces.begin(), faces.end() ) );
1513 for (
int vertexIndex : vertices )
1515 int currentVertexToFace = mVertexToFace.at( vertexIndex );
1521 dereferenceAsFreeVertex( vertexIndex );
1523 mVertexToFace[vertexIndex] = -1;
1531 QList<int> boundariesToCheckClockwiseInNewFaces = topologicFaces.mBoundaries;
1532 QList<std::array<int, 2>> boundariesToCheckCounterClockwiseInNewFaces;
1533 QList<int> uniqueSharedVertexBoundary;
1541 while ( !boundariesToCheckClockwiseInNewFaces.isEmpty() )
1543 int boundary = boundariesToCheckClockwiseInNewFaces.takeLast();
1545 const QList<int> &linkedFaces = topologicFaces.mVerticesToFace.values( boundary );
1547 for (
int const linkedFace : linkedFaces )
1551 if ( mVertexToFace.at( boundary ) == -1 )
1557 if ( !newFacescirculator.
isValid() )
1571 if ( oppositeVertexCCWInMesh == oppositeVertexInNewFaces )
1577 int faceSize = newFaceOnBoundary.size();
1578 int posInNewFace = vertexPositionInFace( boundary, newFaceOnBoundary );
1579 int previousVertexIndex = ( posInNewFace + faceSize - 1 ) % faceSize;
1580 if ( newFaceOnBoundary.at( previousVertexIndex ) == oppositeVertexCCWInMesh )
1588 if ( oppositeVertexCWInMesh == oppositeVertexInNewFaces )
1592 boundariesToCheckCounterClockwiseInNewFaces.append( {boundary, linkedFace} );
1597 while ( !boundariesToCheckCounterClockwiseInNewFaces.isEmpty() )
1599 std::array<int, 2> boundaryLinkedface = boundariesToCheckCounterClockwiseInNewFaces.takeLast();
1600 int boundary = boundaryLinkedface.at( 0 );
1601 int linkedFace = boundaryLinkedface.at( 1 );
1616 if ( oppositeVertexCWInMesh == oppositeVertexInNewFaces )
1623 if ( oppositeVertexCCWInMesh == oppositeVertexInNewFaces )
1626 uniqueSharedVertexBoundary.append( boundary );
1629 if ( !uniqueSharedVertexBoundary.isEmpty() )
1633 QSet<int> boundaryVertices( topologicFaces.mBoundaries.constBegin(), topologicFaces.mBoundaries.constEnd() );
1634 for (
const QgsMeshFace &newFace : std::as_const( topologicFaces.mFaces ) )
1636 for (
const int vertexIndex : newFace )
1638 if ( boundaryVertices.contains( vertexIndex ) )
1640 if ( mVertexToFace.at( vertexIndex ) != -1 )
1651 mFacesNeighborhood.clear();
1652 mVerticesToFace.clear();
1653 mBoundaries.clear();
1658 return mFacesNeighborhood;
1663 if ( mVerticesToFace.contains( vertexIndex ) )
1664 return mVerticesToFace.values( vertexIndex ).at( 0 );
1672 topologicMesh.mMesh =
mesh;
1673 topologicMesh.mVertexToFace = QVector<int>(
mesh->
vertexCount(), -1 );
1674 topologicMesh.mMaximumVerticesPerFace = maxVerticesPerFace;
1681 if ( maxVerticesPerFace != 0 &&
mesh->
face( i ).count() > maxVerticesPerFace )
1699 topologicMesh.mFacesNeighborhood = subMesh.mFacesNeighborhood;
1701 for (
int i = 0; i < topologicMesh.mMesh->
vertexCount(); ++i )
1703 if ( topologicMesh.mVertexToFace.at( i ) == -1 )
1704 topologicMesh.mFreeVertices.insert( i );
1708 return topologicMesh;
1713 return createTopologicalFaces( faces,
nullptr, error, uniqueSharedVertexAllowed );
1718 const QVector<QgsMeshFace> &faces,
1719 QVector<int> *globalVertexToFace,
1721 bool allowUniqueSharedVertex )
1723 int facesCount = faces.count();
1724 QVector<FaceNeighbors> faceTopologies;
1725 QMultiHash<int, int> verticesToFace;
1728 TopologicalFaces ret;
1732 QMap<int, QMap<int, int>> verticesToNeighbor;
1734 for (
int faceIndex = 0; faceIndex < facesCount; ++faceIndex )
1737 int faceSize = face.count();
1739 for (
int i = 0; i < faceSize; ++i )
1741 int v1 = face[i % faceSize];
1742 int v2 = face[( i + 1 ) % faceSize];
1743 if ( verticesToNeighbor[v2].contains( v1 ) )
1749 verticesToNeighbor[v2].insert( v1, faceIndex );
1753 faceTopologies = QVector<FaceNeighbors>( faces.count() );
1755 QSet<int> boundaryVertices;
1757 for (
int faceIndex = 0; faceIndex < facesCount; ++faceIndex )
1760 int faceSize = face.size();
1762 faceTopology.resize( faceSize );
1764 for (
int i = 0; i < faceSize; ++i )
1766 int v1 = face.at( i );
1767 int v2 = face.at( ( i + 1 ) % faceSize );
1769 if ( globalVertexToFace )
1771 if ( ( *globalVertexToFace )[v1] == -1 )
1772 ( *globalVertexToFace )[v1] = faceIndex ;
1776 if ( allowUniqueSharedVertex || !verticesToFace.contains( v1 ) )
1777 verticesToFace.insert( v1, faceIndex ) ;
1780 QMap<int, int> &edges = verticesToNeighbor[v1];
1781 if ( edges.contains( v2 ) )
1782 faceTopology[i] = edges.value( v2 );
1785 faceTopology[i] = -1;
1787 if ( !allowUniqueSharedVertex )
1789 if ( boundaryVertices.contains( v1 ) )
1795 boundaryVertices.insert( v1 );
1801 ret.mFacesNeighborhood = faceTopologies;
1802 ret.mBoundaries = boundaryVertices.values();
1803 ret.mVerticesToFace = verticesToFace;
1809 return mFacesNeighborhood.at( faceIndex );
1821 QSet<int> removedFaces( facesIndexes.begin(), facesIndexes.end() );
1822 QSet<int> concernedFaces = concernedFacesBy( facesIndexes );
1824 for (
const int f : std::as_const( removedFaces ) )
1825 concernedFaces.remove( f );
1827 QVector<QgsMeshFace> remainingFaces;
1828 remainingFaces.reserve( concernedFaces.count() );
1829 for (
const int f : std::as_const( concernedFaces ) )
1830 remainingFaces.append( mMesh->
face( f ) );
1833 createTopologicalFaces( remainingFaces,
nullptr, error,
false );
1845 QSet<int> indexSet( facesIndexesToRemove.begin(), facesIndexesToRemove.end() );
1846 QSet<int> threatedVertex;
1848 for (
int i = 0; i < facesIndexesToRemove.count(); ++i )
1850 const int faceIndex = facesIndexesToRemove.at( i );
1853 const FaceNeighbors &neighborhood = mFacesNeighborhood.at( faceIndex );
1855 for (
int j = 0; j < face.count(); ++j )
1858 int neighborIndex = neighborhood.at( j );
1859 if ( neighborIndex != -1 && !indexSet.contains( neighborIndex ) )
1861 int positionInNeighbor = mFacesNeighborhood.at( neighborIndex ).indexOf( faceIndex );
1866 int vertexIndex = face.at( j );
1867 if ( !threatedVertex.contains( vertexIndex ) && indexSet.contains( mVertexToFace.at( vertexIndex ) ) )
1869 int oldValue = mVertexToFace.at( vertexIndex );
1872 if ( neighborIndex != -1 && !indexSet.contains( neighborIndex ) )
1873 refValue = neighborIndex;
1877 aroundFaces.removeOne( faceIndex );
1878 if ( !aroundFaces.isEmpty() )
1880 while ( !aroundFaces.isEmpty() && refValue == -1 )
1882 if ( !indexSet.contains( aroundFaces.first() ) )
1883 refValue = aroundFaces.first();
1885 aroundFaces.removeFirst();
1890 threatedVertex.insert( vertexIndex );
1900bool QgsTopologicalMesh::eitherSideFacesAndVertices(
int vertexIndex1,
1904 int &neighborVertex1InFace1,
1905 int &neighborVertex1InFace2,
1906 int &neighborVertex2inFace1,
1907 int &neighborVertex2inFace2 )
const
1949 int oppositeVertexFace1;
1950 int oppositeVertexFace2;
1951 int supposedOppositeVertexFace1;
1952 int supposedoppositeVertexFace2;
1954 bool result = eitherSideFacesAndVertices(
1959 oppositeVertexFace1,
1960 supposedoppositeVertexFace2,
1961 supposedOppositeVertexFace1,
1962 oppositeVertexFace2 );
1967 oppositeVertexFace1 < 0 ||
1968 oppositeVertexFace2 < 0 ||
1969 supposedOppositeVertexFace1 != oppositeVertexFace1 ||
1970 supposedoppositeVertexFace2 != oppositeVertexFace2 )
1977 if ( face1.count() != 3 || face2.count() != 3 )
1980 double crossProduct1 = crossProduct( vertexIndex1, oppositeVertexFace1, oppositeVertexFace2, *mMesh );
1981 double crossProduct2 = crossProduct( vertexIndex2, oppositeVertexFace1, oppositeVertexFace2, *mMesh );
1983 return crossProduct1 * crossProduct2 < 0;
1990 int oppositeVertexFace1;
1991 int oppositeVertexFace2;
1992 int supposedOppositeVertexFace1;
1993 int supposedoppositeVertexFace2;
1995 bool result = eitherSideFacesAndVertices(
2000 oppositeVertexFace1,
2001 supposedoppositeVertexFace2,
2002 supposedOppositeVertexFace1,
2003 oppositeVertexFace2 );
2008 oppositeVertexFace1 < 0 ||
2009 oppositeVertexFace2 < 0 ||
2010 supposedOppositeVertexFace1 != oppositeVertexFace1 ||
2011 supposedoppositeVertexFace2 != oppositeVertexFace2 )
2020 Q_ASSERT( face1.count() == 3 );
2021 Q_ASSERT( face2.count() == 3 );
2023 int pos1 = vertexPositionInFace( vertexIndex1, face1 );
2024 int pos2 = vertexPositionInFace( vertexIndex2, face2 );
2026 int neighborFace1 = mFacesNeighborhood.at( faceIndex1 ).at( pos1 );
2027 int posInNeighbor1 = vertexPositionInFace( *mMesh, oppositeVertexFace1, neighborFace1 );
2028 int neighborFace2 = mFacesNeighborhood.at( faceIndex1 ).at( ( pos1 + 1 ) % 3 );
2029 int posInNeighbor2 = vertexPositionInFace( *mMesh, vertexIndex2, neighborFace2 );
2030 int neighborFace3 = mFacesNeighborhood.at( faceIndex2 ).at( pos2 );
2031 int posInNeighbor3 = vertexPositionInFace( *mMesh, oppositeVertexFace2, neighborFace3 );
2032 int neighborFace4 = mFacesNeighborhood.at( faceIndex2 ).at( ( pos2 + 1 ) % 3 );
2033 int posInNeighbor4 = vertexPositionInFace( *mMesh, vertexIndex1, neighborFace4 );
2043 changes.
mFacesToAdd.append( {oppositeVertexFace1, oppositeVertexFace2, vertexIndex1} );
2044 changes.
mFacesToAdd.append( {oppositeVertexFace2, oppositeVertexFace1, vertexIndex2} );
2046 mFacesNeighborhood.at( faceIndex2 ).at( ( pos2 + 1 ) % 3 ),
2047 mFacesNeighborhood.at( faceIndex1 ).at( pos1 )
2050 mFacesNeighborhood.at( faceIndex1 ).at( ( pos1 + 1 ) % 3 ),
2051 mFacesNeighborhood.at( faceIndex2 ).at( pos2 )
2054 if ( neighborFace1 >= 0 )
2055 changes.
mNeighborhoodChanges.append( {neighborFace1, posInNeighbor1, faceIndex1, startIndex} );
2056 if ( neighborFace2 >= 0 )
2057 changes.
mNeighborhoodChanges.append( {neighborFace2, posInNeighbor2, faceIndex1, startIndex + 1} );
2058 if ( neighborFace3 >= 0 )
2059 changes.
mNeighborhoodChanges.append( {neighborFace3, posInNeighbor3, faceIndex2, startIndex + 1} );
2060 if ( neighborFace4 >= 0 )
2061 changes.
mNeighborhoodChanges.append( {neighborFace4, posInNeighbor4, faceIndex2, startIndex} );
2064 if ( mVertexToFace.at( vertexIndex1 ) == faceIndex1 || mVertexToFace.at( vertexIndex1 ) == faceIndex2 )
2066 if ( mVertexToFace.at( vertexIndex2 ) == faceIndex1 || mVertexToFace.at( vertexIndex2 ) == faceIndex2 )
2067 changes.
mVerticesToFaceChanges.append( {vertexIndex2, mVertexToFace.at( vertexIndex2 ), startIndex + 1} );
2069 if ( mVertexToFace.at( oppositeVertexFace1 ) == faceIndex1 )
2072 if ( mVertexToFace.at( oppositeVertexFace2 ) == faceIndex2 )
2084 int neighborVertex1InFace1;
2085 int neighborVertex1InFace2;
2086 int neighborVertex2inFace1;
2087 int neighborVertex2inFace2;
2089 bool result = eitherSideFacesAndVertices(
2094 neighborVertex1InFace1,
2095 neighborVertex1InFace2,
2096 neighborVertex2inFace1,
2097 neighborVertex2inFace2 );
2107 if ( face1.count() + face2.count() - 2 > mMaximumVerticesPerFace )
2117 double crossProduct1 = crossProduct( vertexIndex1, neighborVertex1InFace1, neighborVertex1InFace2, *mMesh );
2118 double crossProduct2 = crossProduct( vertexIndex2, neighborVertex2inFace1, neighborVertex2inFace2, *mMesh );
2120 return crossProduct1 * crossProduct2 < 0;
2127 int neighborVertex1InFace1;
2128 int neighborVertex1InFace2;
2129 int neighborVertex2inFace1;
2130 int neighborVertex2inFace2;
2132 bool result = eitherSideFacesAndVertices(
2137 neighborVertex1InFace1,
2138 neighborVertex1InFace2,
2139 neighborVertex2inFace1,
2140 neighborVertex2inFace2 );
2151 int faceSize1 = face1.count();
2152 int faceSize2 = face2.count();
2154 int pos1 = vertexPositionInFace( vertexIndex1, face1 );
2155 int pos2 = vertexPositionInFace( vertexIndex2, face2 );
2168 for (
int i = 0; i < faceSize1 - 1; ++i )
2170 int currentPos = ( pos1 + i ) % faceSize1;
2171 newface.append( face1.at( currentPos ) );
2173 int currentNeighbor = mFacesNeighborhood.at( faceIndex1 ).at( currentPos );
2174 newNeighborhood.append( currentNeighbor );
2176 if ( currentNeighbor != -1 )
2178 int currentPosInNeighbor = vertexPositionInFace( *mMesh, face1.at( ( currentPos + 1 ) % faceSize1 ), currentNeighbor );
2179 changes.
mNeighborhoodChanges.append( {currentNeighbor, currentPosInNeighbor, faceIndex1, startIndex} );
2182 for (
int i = 0; i < faceSize2 - 1; ++i )
2184 int currentPos = ( pos2 + i ) % faceSize2;
2185 newface.append( face2.at( currentPos ) );
2187 int currentNeighbor = mFacesNeighborhood.at( faceIndex2 ).at( currentPos );
2188 newNeighborhood.append( currentNeighbor );
2190 if ( currentNeighbor != -1 )
2192 int currentPosInNeighbor = vertexPositionInFace( *mMesh, face2.at( ( currentPos + 1 ) % faceSize2 ), currentNeighbor );
2193 changes.
mNeighborhoodChanges.append( {currentNeighbor, currentPosInNeighbor, faceIndex2, startIndex} );
2197 for (
int i = 0; i < faceSize1; ++i )
2198 if ( mVertexToFace.at( face1.at( i ) ) == faceIndex1 )
2201 for (
int i = 0; i < faceSize2; ++i )
2202 if ( mVertexToFace.at( face2.at( i ) ) == faceIndex2 )
2217 return face.count() == 4;
2224 int faceSize = face.count();
2226 Q_ASSERT( faceSize == 4 );
2228 double maxAngle = 0;
2229 int splitVertexPos = -1;
2230 for (
int i = 0; i < faceSize; ++i )
2232 QgsVector vect1( mMesh->
vertex( face.at( i ) ) - mMesh->
vertex( face.at( ( i + 1 ) % faceSize ) ) );
2233 QgsVector vect2( mMesh->
vertex( face.at( ( i + 2 ) % faceSize ) ) - mMesh->
vertex( face.at( ( i + 1 ) % faceSize ) ) );
2235 double angle = std::abs( vect1.
angle( vect2 ) );
2236 angle = std::min( angle, 2.0 * M_PI - angle );
2237 if ( angle > maxAngle )
2240 splitVertexPos = ( i + 1 ) % faceSize;
2245 if ( splitVertexPos == -1 )
2248 const QgsMeshFace newFace1 = {face.at( splitVertexPos ),
2249 face.at( ( splitVertexPos + 1 ) % faceSize ),
2250 face.at( ( splitVertexPos + 2 ) % faceSize )
2253 const QgsMeshFace newFace2 = {face.at( splitVertexPos ),
2254 face.at( ( splitVertexPos + 2 ) % faceSize ),
2255 face.at( ( splitVertexPos + 3 ) % faceSize )
2258 QVector<int> neighborIndex( faceSize );
2259 QVector<int> posInNeighbor( faceSize );
2261 for (
int i = 0; i < faceSize; ++i )
2263 neighborIndex[i] = mFacesNeighborhood.at( faceIndex ).at( ( splitVertexPos + i ) % faceSize );
2264 posInNeighbor[i] = vertexPositionInFace( *mMesh, face.at( ( splitVertexPos + i + 1 ) % faceSize ), neighborIndex[i] );
2276 mFacesNeighborhood.at( faceIndex ).at( ( splitVertexPos + 1 ) % faceSize ),
2280 mFacesNeighborhood.at( faceIndex ).at( ( splitVertexPos + 2 ) % faceSize ),
2281 mFacesNeighborhood.at( faceIndex ).at( ( splitVertexPos + 3 ) % faceSize )
2284 for (
int i = 0; i < faceSize; ++i )
2286 if ( neighborIndex[i] >= 0 )
2287 changes.
mNeighborhoodChanges.append( {neighborIndex[i], posInNeighbor[i], faceIndex, startIndex + int( i / 2 )} );
2289 int vertexIndex = face.at( ( splitVertexPos + i ) % faceSize );
2290 if ( mVertexToFace.at( vertexIndex ) == faceIndex )
2307 mVertexToFace.append( -1 );
2311 const FaceNeighbors includingFaceNeighborhood = mFacesNeighborhood.at( includingFaceIndex );
2312 int includingFaceSize = includingFace.count();
2314 for (
int i = 0; i < includingFaceSize; ++i )
2319 face[1] = includingFace.at( i );
2320 face[2] = includingFace.at( ( i + 1 ) % includingFaceSize );
2321 mMesh->
faces.append( face );
2324 int currentVertexIndex = includingFace.at( i );
2325 if ( mVertexToFace.at( currentVertexIndex ) == includingFaceIndex )
2327 int newFaceIndex = mMesh->
faceCount() - 1;
2328 mVertexToFace[currentVertexIndex] = newFaceIndex;
2332 int includingFaceNeighbor = includingFaceNeighborhood.at( i );
2336 includingFaceNeighbor,
2339 mFacesNeighborhood.append( neighbors );
2342 if ( includingFaceNeighbor != -1 )
2344 int indexInNeighbor = vertexPositionInFace( *mMesh, includingFace.at( ( i + 1 ) % includingFaceSize ), includingFaceNeighbor );
2345 int oldValue = mFacesNeighborhood[includingFaceNeighbor][indexInNeighbor];
2357 mVertexToFace[mVertexToFace.count() - 1] = mMesh->
faceCount() - 1;
2372 int newVertexPositionInFace1 = position + 1;
2374 auto triangulate = [
this, &changes](
int removedFaceIndex,
const QgsMeshVertex & newVertex,
int newVertexPosition, QVector<int> &edgeFacesIndexes )->
bool
2380 const int addedVertexIndex = mMesh->
vertexCount();
2383 int localStartIndex = changes.
mFacesToAdd.count();
2385 QVector<int> newBoundary = initialFace;
2386 newBoundary.insert( newVertexPosition, addedVertexIndex );
2390 QHash<p2t::Point *, int> mapPoly2TriPointToVertex;
2391 std::vector<p2t::Point *> faceToFill( newBoundary.count() );
2392 for (
int i = 0; i < newBoundary.count(); ++i )
2396 if ( newBoundary.at( i ) == addedVertexIndex )
2399 vert = mMesh->
vertex( newBoundary.at( i ) );
2401 faceToFill[i] =
new p2t::Point( vert.
x(), vert.
y() );
2402 mapPoly2TriPointToVertex.insert( faceToFill[i], newBoundary.at( i ) );
2405 std::unique_ptr<p2t::CDT> cdt(
new p2t::CDT( faceToFill ) );
2407 std::vector<p2t::Triangle *> triangles = cdt->GetTriangles();
2408 QVector<QgsMeshFace> newFaces( triangles.size() );
2409 for (
size_t i = 0; i < triangles.size(); ++i )
2413 for (
int j = 0; j < 3; j++ )
2415 int vertInd = mapPoly2TriPointToVertex.value( triangles.at( i )->GetPoint( j ), -1 );
2416 if ( vertInd == -1 )
2417 throw std::exception();
2425 throw std::exception();
2431 const QList<int> &verticesToFaceToChange = topologicalFaces.mVerticesToFace.keys();
2432 for (
const int vtc : verticesToFaceToChange )
2433 if ( vtc != addedVertexIndex && mVertexToFace.at( vtc ) == removedFaceIndex )
2438 topologicalFaces.
vertexToFace( vtc ) + faceStartGlobalIndex
2442 for (
int i = 0; i < topologicalFaces.mFaces.count(); ++i )
2445 for (
int n = 0; n < faceNeighbors.count(); ++n )
2447 if ( faceNeighbors.at( n ) != -1 )
2448 faceNeighbors[n] += faceStartGlobalIndex;
2452 edgeFacesIndexes.resize( 2 );
2454 for (
int i = 0 ; i < newBoundary.count(); ++i )
2456 int vertexIndex = newBoundary.at( i );
2459 int newFaceBoundaryLocalIndex = localStartIndex + circulator.
currentFaceIndex();
2461 int newFaceBoundaryIndexInMesh = faceStartGlobalIndex;
2463 int meshFaceBoundaryIndex;
2464 if ( i == newVertexPosition )
2466 meshFaceBoundaryIndex = -1;
2467 edgeFacesIndexes[0] = newFaceBoundaryLocalIndex;
2469 else if ( i == ( newVertexPosition + newBoundary.count() - 1 ) % newBoundary.count() )
2471 meshFaceBoundaryIndex = -1;
2472 edgeFacesIndexes[1] = newFaceBoundaryLocalIndex;
2475 meshFaceBoundaryIndex = mFacesNeighborhood.at( removedFaceIndex ).at( vertexPositionInFace( vertexIndex, initialFace ) );
2478 int positionInNewFaces = vertexPositionInFace( vertexIndex, newFace );
2480 if ( meshFaceBoundaryIndex != -1 )
2483 int positionInMeshFaceBoundary = vertexPositionInFace( *mMesh, vertexIndex, meshFaceBoundaryIndex );
2484 positionInMeshFaceBoundary = ( positionInMeshFaceBoundary - 1 + meshFace.count() ) % meshFace.count();
2487 positionInMeshFaceBoundary,
2489 newFaceBoundaryIndexInMesh +
2497 qDeleteAll( faceToFill );
2507 QVector<int> edgeFacesIndexes;
2508 if ( !triangulate( faceIndex, vertexToInsert, newVertexPositionInFace1, edgeFacesIndexes ) )
2511 changes.mVertexToFaceToAdd.append( edgeFacesIndexes.at( 0 ) + changes.mAddedFacesFirstIndex );
2516 int face2Index = mFacesNeighborhood.at( faceIndex ).at( position );
2517 if ( face2Index != -1 )
2520 int vertexPositionInFace2 = vertexPositionInFace( face1.at( position ), face2 );
2521 QVector<int> edgeFacesIndexesFace2;
2522 if ( !triangulate( face2Index, vertexToInsert, vertexPositionInFace2, edgeFacesIndexesFace2 ) )
2526 const QgsMeshFace &firstFaceSide1 = changes.mFacesToAdd.at( edgeFacesIndexes.at( 0 ) );
2527 int pos1InFaceSide1 = vertexPositionInFace( addedVertexIndex, firstFaceSide1 );
2529 const QgsMeshFace &secondFaceSide1 = changes.mFacesToAdd.at( edgeFacesIndexes.at( 1 ) );
2530 int pos2InFaceSide1 = vertexPositionInFace( addedVertexIndex, secondFaceSide1 );
2531 pos2InFaceSide1 = ( pos2InFaceSide1 + secondFaceSide1.size() - 1 ) % secondFaceSide1.size();
2533 const QgsMeshFace &firstFaceSide2 = changes.mFacesToAdd.at( edgeFacesIndexesFace2.at( 0 ) );
2534 int pos1InFaceSide2 = vertexPositionInFace( addedVertexIndex, firstFaceSide2 );
2536 const QgsMeshFace &secondFaceSide2 = changes.mFacesToAdd.at( edgeFacesIndexesFace2.at( 1 ) );
2537 int pos2InFaceSide2 = vertexPositionInFace( addedVertexIndex, secondFaceSide2 );
2538 pos2InFaceSide2 = ( pos2InFaceSide2 + secondFaceSide1.size() - 1 ) % secondFaceSide1.size();
2540 changes.mFacesNeighborhoodToAdd[edgeFacesIndexes.at( 0 )][pos1InFaceSide1] = edgeFacesIndexesFace2.at( 1 ) + changes.mAddedFacesFirstIndex;
2541 changes.mFacesNeighborhoodToAdd[edgeFacesIndexes.at( 1 )][pos2InFaceSide1] = edgeFacesIndexesFace2.at( 0 ) + changes.mAddedFacesFirstIndex;
2542 changes.mFacesNeighborhoodToAdd[edgeFacesIndexesFace2.at( 0 )][pos1InFaceSide2] = edgeFacesIndexes.at( 1 ) + changes.mAddedFacesFirstIndex;
2543 changes.mFacesNeighborhoodToAdd[edgeFacesIndexesFace2.at( 1 )][pos2InFaceSide2] = edgeFacesIndexes.at( 0 ) + changes.mAddedFacesFirstIndex;
2552 Q_ASSERT( verticesIndexes.count() == newValues.count() );
2555 changes.
mNewZValues.reserve( verticesIndexes.count() );
2556 changes.
mOldZValues.reserve( verticesIndexes.count() );
2557 for (
int i = 0; i < verticesIndexes.count(); ++i )
2571 Q_ASSERT( verticesIndexes.count() == newValues.count() );
2574 changes.
mNewXYValues.reserve( verticesIndexes.count() );
2575 changes.
mOldXYValues.reserve( verticesIndexes.count() );
2576 QSet<int> concernedFace;
2577 for (
int i = 0; i < verticesIndexes.count(); ++i )
2583 concernedFace.unite( QSet< int>( faces.begin(), faces.end() ) );
@ InvalidFace
An error occurs due to an invalid face (for example, vertex indexes are unordered)
@ UniqueSharedVertex
A least two faces share only one vertices.
@ ManifoldFace
ManifoldFace.
@ InvalidVertex
An error occurs due to an invalid vertex (for example, vertex index is out of range the available ver...
@ FlatFace
A flat face is present.
static bool segmentIntersection(const QgsPoint &p1, const QgsPoint &p2, const QgsPoint &q1, const QgsPoint &q2, QgsPoint &intersectionPoint, bool &isIntersection, double tolerance=1e-8, bool acceptImproperIntersection=false)
Compute the intersection between two segments.
Class that represents an error during mesh editing.
Qgis::MeshEditingErrorType errorType
Convenient class that turn around a vertex and provide information about faces and vertices.
bool isValid() const
Returns whether the vertex circulator is valid.
int turnClockwise() const
Turns counter clockwise around the vertex and returns the new current face, -1 if the circulator pass...
bool goBoundaryCounterClockwise() const
Sets the circulator on the boundary face turning counter clockwise, return false is there isn't bound...
int oppositeVertexCounterClockwise() const
Returns the opposite vertex of the current face and on the edge on the side turning counter clockwise...
int turnCounterClockwise() const
Turns counter clockwise around the vertex and returns the new current face, -1 if the circulator pass...
int currentFaceIndex() const
Returns the current face index, -1 if the circulator has passed a boundary or circulator is invalid.
bool goBoundaryClockwise() const
Sets the circulator on the boundary face turning clockwise, return false is there isn't boundary face...
QgsMeshFace currentFace() const
Returns the current face, empty face if the circulator pass a boundary or circulator is invalid.
QgsMeshVertexCirculator(const QgsTopologicalMesh &topologicalMesh, int vertexIndex)
Constructor with topologicalMesh and vertexIndex.
int oppositeVertexClockwise() const
Returns the opposite vertex of the current face and on the edge on the side turning clockwise.
int degree() const
Returns the degree of the vertex, that is the count of other vertices linked.
QList< int > facesAround() const
Returns all the faces indexes around the vertex.
static void logMessage(const QString &message, const QString &tag=QString(), Qgis::MessageLevel level=Qgis::MessageLevel::Warning, bool notifyUser=true)
Adds a message to the log instance (and creates it if necessary).
A class to represent a 2D point.
Point geometry type, with support for z-dimension and m-values.
bool isEmpty() const override
Returns true if the geometry is empty.
Class that contains topological differences between two states of a topological mesh,...
QList< int > mChangeCoordinateVerticesIndexes
QList< int > mVerticesToFaceRemoved
void clearChanges()
Clears all changes.
QVector< FaceNeighbors > mFacesNeighborhoodToRemove
QVector< QgsMeshFace > removedFaces() const
Returns the faces that are removed with this changes.
QList< QgsPointXY > mNewXYValues
QList< QgsMeshVertex > mRemovedVertices
QVector< QgsMeshVertex > addedVertices() const
Returns the added vertices with this changes.
QList< std::array< int, 4 > > mNeighborhoodChanges
bool isEmpty() const
Returns whether changes are empty, that there is nothing to change.
QList< int > mVerticesToRemoveIndexes
QList< int > changedCoordinatesVerticesIndexes() const
Returns the indexes of vertices that have changed coordinates.
QList< int > mNativeFacesIndexesGeometryChanged
QVector< QgsMeshFace > mFacesToAdd
QList< int > removedFaceIndexes() const
Returns the indexes of the faces that are removed with this changes.
QVector< FaceNeighbors > mFacesNeighborhoodToAdd
QList< std::array< int, 3 > > mVerticesToFaceChanges
QList< QgsPointXY > mOldXYValues
QList< double > newVerticesZValues() const
Returns the new Z values of vertices that have changed their coordinates.
QList< double > mNewZValues
QVector< QgsMeshVertex > mVerticesToAdd
QVector< QgsMeshFace > addedFaces() const
Returns the face that are added with this changes.
QList< QgsPointXY > oldVerticesXYValues() const
Returns the old (X,Y) values of vertices that have changed their coordinates.
int mAddedFacesFirstIndex
QVector< int > mVertexToFaceToAdd
QList< int > mFaceIndexesToRemove
QList< QgsPointXY > newVerticesXYValues() const
Returns the new (X,Y) values of vertices that have changed their coordinates.
QVector< QgsMeshFace > mFacesToRemove
QList< double > mOldZValues
QList< int > nativeFacesIndexesGeometryChanged() const
Returns a list of the native face indexes that have a geometry changed.
QList< int > verticesToRemoveIndexes() const
Returns the indexes of vertices to remove.
Class that contains independent faces an topological information about this faces.
int vertexToFace(int vertexIndex) const
Returns a face linked to the vertices with index vertexIndex.
QVector< FaceNeighbors > facesNeighborhood() const
Returns the face neighborhood of the faces, indexing is local.
void clear()
Clears all data contained in the instance.
QVector< QgsMeshFace > meshFaces() const
Returns faces.
Class that wraps a QgsMesh to ensure the consistency of the mesh during editing and help to access to...
static QgsMeshEditingError checkTopologyOfVerticesAsFace(const QVector< QgsMeshVertex > &vertices, bool &clockwise)
Checks the topology of the vertices as they are contained in a face and returns indication on directi...
Changes changeZValue(const QList< int > &verticesIndexes, const QList< double > &newValues)
Changes the Z values of the vertices with indexes in vertices indexes with the values in newValues.
static QgsTopologicalMesh createTopologicalMesh(QgsMesh *mesh, int maxVerticesPerFace, QgsMeshEditingError &error)
Creates a topologicaly consistent mesh with mesh, this static method modifies mesh to be topological ...
bool isVertexFree(int vertexIndex) const
Returns whether the vertex is a free vertex.
static QgsMeshEditingError counterClockwiseFaces(QgsMeshFace &face, QgsMesh *mesh)
Checks the topology of the face and sets it counter clockwise if necessary.
Changes removeVertexFillHole(int vertexIndex)
Removes the vertex with index vertexIndex.
static QgsMeshEditingError checkTopology(const QgsMesh &mesh, int maxVerticesPerFace)
Checks the topology of the mesh mesh, if error occurs, this mesh can't be edited.
friend class QgsMeshVertexCirculator
void applyChanges(const Changes &changes)
Applies the changes.
int firstFaceLinked(int vertexIndex) const
Returns the index of the first face linked, returns -1 if it is a free vertex or out of range index.
QgsMeshEditingError checkConsistency() const
Checks the consistency of the topological mesh and return false if there is a consistency issue.
Changes removeVertices(const QList< int > &vertices)
Removes all the vertices with index in the list vertices If vertices in linked with faces,...
Changes changeXYValue(const QList< int > &verticesIndexes, const QList< QgsPointXY > &newValues)
Changes the (X,Y) values of the vertices with indexes in vertices indexes with the values in newValue...
void reindex()
Reindexes faces and vertices, after this operation, the topological mesh can't be edited anymore and ...
QVector< int > neighborsOfFace(int faceIndex) const
Returns the indexes of neighbor faces of the face with index faceIndex.
QgsMeshEditingError facesCanBeAdded(const TopologicalFaces &topologicalFaces) const
Returns whether the faces can be added to the mesh.
bool renumber()
Renumbers the indexes of vertices and faces using the Reverse CutHill McKee Algorithm.
Changes flipEdge(int vertexIndex1, int vertexIndex2)
Flips edge (vertexIndex1, vertexIndex2) The method returns a instance of the class QgsTopologicalMesh...
QgsMeshEditingError facesCanBeRemoved(const QList< int > &facesIndexes)
Returns whether faces with index in faceIndexes can be removed/ The method an error object with type ...
QVector< int > FaceNeighbors
void reverseChanges(const Changes &changes)
Reverses the changes.
Changes addFaces(const TopologicalFaces &topologicFaces)
Adds faces topologicFaces to the topologic mesh.
Changes merge(int vertexIndex1, int vertexIndex2)
Merges faces separated by vertices with indexes vertexIndex1 and vertexIndex2 The method returns a in...
Changes removeFaces(const QList< int > &facesIndexes)
Removes faces with index in faceIndexes.
QList< int > freeVerticesIndexes() const
Returns a list of vertices are not linked to any faces.
bool edgeCanBeFlipped(int vertexIndex1, int vertexIndex2) const
Returns true if the edge can be flipped (only available for edge shared by two faces with 3 vertices)
Changes addVertexInFace(int faceIndex, const QgsMeshVertex &vertex)
Adds a vertex in the face with index faceIndex.
bool canBeMerged(int vertexIndex1, int vertexIndex2) const
Returns true if faces separated by vertices with indexes vertexIndex1 and vertexIndex2 can be merged.
QList< int > facesAroundVertex(int vertexIndex) const
Returns the indexes of faces that are around the vertex with index vertexIndex.
bool canBeSplit(int faceIndex) const
Returns true if face with index faceIndex can be split.
Changes addFreeVertex(const QgsMeshVertex &vertex)
Adds a free vertex in the face, that is a vertex that is not included or linked with any faces.
Changes insertVertexInFacesEdge(int faceIndex, int position, const QgsMeshVertex &vertex)
Inserts a vertex in the edge of face with index faceIndex at position .
QgsMesh * mesh() const
Returns a pointer to the wrapped mesh.
bool isVertexOnBoundary(int vertexIndex) const
Returns whether the vertex is on a boundary.
Changes splitFace(int faceIndex)
Splits face with index faceIndex The method returns a instance of the class QgsTopologicalMesh::Chang...
static TopologicalFaces createNewTopologicalFaces(const QVector< QgsMeshFace > &faces, bool uniqueSharedVertexAllowed, QgsMeshEditingError &error)
Creates new topological faces that are not yet included in the mesh.
QgsMeshVertexCirculator vertexCirculator(int vertexIndex) const
Returns a vertex circulator linked to this mesh around the vertex with index vertexIndex.
A class to represent a vector.
double angle() const
Returns the angle of the vector in radians.
QVector< int > QgsMeshFace
List of vertex indexes.
QgsPoint QgsMeshVertex
xyz coords of vertex
Mesh - vertices, edges and faces.
int vertexCount() const
Returns number of vertices.
QVector< QgsMeshVertex > vertices
QgsMeshFace face(int index) const
Returns a face at the index.
QVector< QgsMeshFace > faces
int faceCount() const
Returns number of faces.
QgsMeshVertex vertex(int index) const
Returns a vertex at the index.