28 static int vertexPositionInFace(
int vertexIndex,
const QgsMeshFace &face )
30 return face.indexOf( vertexIndex );
33 static int vertexPositionInFace(
const QgsMesh &mesh,
int vertexIndex,
int faceIndex )
35 if ( faceIndex < 0 || faceIndex >= mesh.
faceCount() )
38 return vertexPositionInFace( vertexIndex, mesh.
face( faceIndex ) );
41 static double crossProduct(
int centralVertex,
int vertex1,
int vertex2,
const QgsMesh &mesh )
47 double ux1 = v1.
x() - vc.
x();
48 double uy1 = v1.
y() - vc.
y();
49 double vx1 = v2.
x() - vc.
x();
50 double vy1 = v2.
y() - vc.
y();
52 return ux1 * vy1 - uy1 * vx1;
57 : mFaces( topologicalMesh.mMesh->faces )
58 , mFacesNeighborhood( topologicalMesh.mFacesNeighborhood )
59 , mVertexIndex( vertexIndex )
61 if ( vertexIndex >= 0 && vertexIndex < topologicalMesh.mMesh->vertexCount() )
63 mCurrentFace = topologicalMesh.mVertexToFace[vertexIndex];
64 mIsValid = vertexPositionInFace( *topologicalMesh.
mesh(), vertexIndex, mCurrentFace ) != -1;
72 mLastValidFace = mCurrentFace;
76 : mFaces( topologicalFaces.mFaces )
77 , mFacesNeighborhood( topologicalFaces.mFacesNeighborhood )
78 , mVertexIndex( vertexIndex )
80 const QgsMeshFace &face = topologicalFaces.mFaces.at( faceIndex );
81 mIsValid = vertexPositionInFace( vertexIndex, face ) != -1;
83 mCurrentFace = faceIndex;
84 mLastValidFace = mCurrentFace;
88 : mFaces( topologicalFaces.mFaces )
89 , mFacesNeighborhood( topologicalFaces.mFacesNeighborhood )
90 , mVertexIndex( vertexIndex )
92 if ( topologicalFaces.mVerticesToFace.contains( vertexIndex ) )
93 mCurrentFace = topologicalFaces.mVerticesToFace.values( vertexIndex ).first();
94 mLastValidFace = mCurrentFace;
95 mIsValid = mCurrentFace != -1;
100 if ( mCurrentFace == -1 )
101 mCurrentFace = mLastValidFace;
104 int currentPos = positionInCurrentFace();
105 Q_ASSERT( currentPos != -1 );
109 mLastValidFace = mCurrentFace;
110 mCurrentFace = mFacesNeighborhood.at( mCurrentFace ).at( ( currentPos + faceSize - 1 ) %
currentFace.count() );
118 if ( mCurrentFace == -1 )
119 mCurrentFace = mLastValidFace;
122 int currentPos = positionInCurrentFace();
123 Q_ASSERT( currentPos != -1 );
127 mLastValidFace = mCurrentFace;
128 mCurrentFace = mFacesNeighborhood.at( mCurrentFace ).at( ( currentPos ) % faceSize );
141 if ( mCurrentFace != -1 )
142 return mFaces.at( mCurrentFace );
152 if ( mCurrentFace == -1 )
153 mCurrentFace = mLastValidFace;
155 int firstFace = mCurrentFace;
158 if ( mCurrentFace == firstFace )
169 if ( mCurrentFace == -1 )
170 mCurrentFace = mLastValidFace;
172 int firstFace = mCurrentFace;
175 if ( mCurrentFace == firstFace )
183 if ( mCurrentFace == -1 )
188 if ( face.isEmpty() )
191 int vertexPosition = vertexPositionInFace( mVertexIndex,
currentFace() );
193 if ( vertexPosition == -1 )
196 return face.at( ( vertexPosition + 1 ) % face.count() );
201 if ( mCurrentFace == -1 )
206 if ( face.isEmpty() )
209 int vertexPosition = vertexPositionInFace( mVertexIndex,
currentFace() );
211 if ( vertexPosition == -1 )
214 return face.at( ( vertexPosition - 1 + face.count() ) % face.count() );
228 if ( mCurrentFace != -1 )
229 ret.append( mCurrentFace );
270 int QgsMeshVertexCirculator::positionInCurrentFace()
const
272 if ( mCurrentFace < 0 || mCurrentFace > mFaces.count() )
275 return vertexPositionInFace( mVertexIndex, mFaces.at( mCurrentFace ) );
285 for (
int i = 0; i < changes.
mFacesToAdd.count(); ++i )
288 for (
int boundary : topologicalFaces.mBoundaries )
291 if ( mVertexToFace.at( boundary ) == -1 )
294 const QList<int> &linkedFaces = topologicalFaces.mVerticesToFace.values( boundary );
295 for (
int linkedFace : linkedFaces )
301 if ( mVertexToFace.at( oppositeVertexForNewFace ) == -1 )
309 int boundaryPositionInNewFace = vertexPositionInFace( boundary, newFaceBoundary );
311 if ( oppositeVertexForMeshFace != oppositeVertexForNewFace )
323 boundaryPositionInMeshFace,
333 for (
int f = 0; f < changes.
mFacesToAdd.count(); ++f )
334 for (
int n = 0; n < changes.
mFacesToAdd.at( f ).count(); ++n )
336 changes.
mFacesNeighborhoodToAdd[f][n] = changes.addedFaceIndexInMesh( topologicalFaces.mFacesNeighborhood.at( f ).at( n ) );
338 const QList<int> &verticesToFaceToChange = topologicalFaces.mVerticesToFace.keys();
339 for (
const int vtc : verticesToFaceToChange )
340 if ( mVertexToFace.at( vtc ) == -1 )
342 mVertexToFace.at( vtc ),
343 changes.addedFaceIndexInMesh( topologicalFaces.mVerticesToFace.values( vtc ).first() ) } );
352 int initialVerticesCount = mMesh->
vertices.count();
357 mVertexToFace.resize( newSize );
363 mMesh->
faces.resize( newSize );
364 mFacesNeighborhood.resize( newSize );
370 mFacesNeighborhood[changes.removedFaceIndexInMesh( i )] =
FaceNeighbors();
376 if ( mVertexToFace.at( vertexIndex ) == -1 )
377 dereferenceAsFreeVertex( vertexIndex );
379 mVertexToFace[vertexIndex] = -1;
387 referenceAsFreeVertex( initialVerticesCount + i );
390 for (
int i = 0; i < changes.
mFacesToAdd.count(); ++i )
392 mMesh->
faces[changes.addedFaceIndexInMesh( i )] = changes.
mFacesToAdd.at( i );
398 const int faceIndex = neigborChange.at( 0 );
399 const int positionInFace = neigborChange.at( 1 );
400 const int valueToApply = neigborChange.at( 3 );
401 mFacesNeighborhood[faceIndex][positionInFace] = valueToApply;
406 int vertexIndex = vertexToFaceChange.at( 0 );
407 mVertexToFace[vertexToFaceChange.at( 0 )] = vertexToFaceChange.at( 2 );
409 if ( vertexToFaceChange.at( 2 ) == -1 &&
410 vertexToFaceChange.at( 1 ) != -1 &&
411 !mMesh->
vertices.at( vertexIndex ).isEmpty() )
412 referenceAsFreeVertex( vertexIndex );
414 if ( vertexToFaceChange.at( 1 ) == -1 && vertexToFaceChange.at( 2 ) != -1 )
415 dereferenceAsFreeVertex( vertexIndex );
426 mMesh->
vertices[vertexIndex].setX( pt.
x() );
427 mMesh->
vertices[vertexIndex].setY( pt.
y() );
436 const int faceIndex = neigborChange.at( 0 );
437 const int positionInFace = neigborChange.at( 1 );
438 const int valueToApply = neigborChange.at( 2 );
439 mFacesNeighborhood[faceIndex][positionInFace] = valueToApply;
453 if ( mVertexToFace.at( vertexIndex ) == -1 )
454 referenceAsFreeVertex( vertexIndex );
458 for (
int i = 0; i < verticesToFaceChangesCount; ++i )
460 const std::array<int, 3> vertexToFaceChange = changes.
mVerticesToFaceChanges.at( verticesToFaceChangesCount - i - 1 );
461 int vertexIndex = vertexToFaceChange.at( 0 );
462 mVertexToFace[vertexIndex] = vertexToFaceChange.at( 1 );
464 if ( vertexToFaceChange.at( 2 ) == -1 && vertexToFaceChange.at( 1 ) != -1 )
465 dereferenceAsFreeVertex( vertexIndex );
467 if ( vertexToFaceChange.at( 1 ) == -1 &&
468 vertexToFaceChange.at( 2 ) != -1 &&
470 referenceAsFreeVertex( vertexIndex );
476 mMesh->
faces.resize( newSize );
477 mFacesNeighborhood.resize( newSize );
484 for (
int i = newSize; i < mMesh->
vertexCount(); ++i )
485 if ( mVertexToFace.at( i ) == -1 )
486 dereferenceAsFreeVertex( i );
489 mVertexToFace.resize( newSize );
500 mMesh->
vertices[vertexIndex].setX( pt.
x() );
501 mMesh->
vertices[vertexIndex].setY( pt.
y() );
511 QSet<int> QgsTopologicalMesh::concernedFacesBy(
const QList<int> faceIndexes )
const
514 for (
const int faceIndex : faceIndexes )
517 for (
int i = 0; i < face.count(); ++i )
523 void QgsTopologicalMesh::dereferenceAsFreeVertex(
int vertexIndex )
525 mFreeVertices.remove( vertexIndex );
528 void QgsTopologicalMesh::referenceAsFreeVertex(
int vertexIndex )
532 mFreeVertices.insert( vertexIndex );
537 for (
int faceIndex = 0 ; faceIndex < mMesh->
faces.count( ); ++faceIndex )
540 const FaceNeighbors &neighborhood = mFacesNeighborhood.at( faceIndex );
541 if ( face.count() != neighborhood.count() )
543 for (
int i = 0; i < face.count(); ++i )
545 int vertexIndex = face.at( i );
547 if ( mVertexToFace.at( vertexIndex ) == -1 )
550 int neighborIndex = neighborhood.at( i );
551 if ( neighborIndex != -1 )
554 if ( neighborFace.isEmpty() )
556 int neighborSize = neighborFace.size();
557 const FaceNeighbors &neighborhoodOfNeighbor = mFacesNeighborhood.at( neighborIndex );
558 int posInNeighbor = vertexPositionInFace( *mMesh, vertexIndex, neighborIndex );
559 if ( neighborhoodOfNeighbor.isEmpty() || neighborhoodOfNeighbor.at( ( posInNeighbor + neighborSize - 1 ) % neighborSize ) != faceIndex )
565 for (
int vertexIndex = 0; vertexIndex < mMesh->
vertexCount(); ++vertexIndex )
567 if ( mVertexToFace.at( vertexIndex ) != -1 )
569 if ( !mMesh->
face( mVertexToFace.at( vertexIndex ) ).contains( vertexIndex ) )
595 if ( vertexIndex < 0 || vertexIndex >= mMesh->
vertexCount() )
597 return mVertexToFace.at( vertexIndex );
612 if ( vertexIndex < 0 || vertexIndex >= mMesh->
vertexCount() )
615 if ( mMesh->
vertices.at( vertexIndex ).isEmpty() )
618 return mVertexToFace.at( vertexIndex ) == -1;
623 #if QT_VERSION < QT_VERSION_CHECK(5, 14, 0)
624 return mFreeVertices.values();
626 return QList<int>( mFreeVertices.begin(), mFreeVertices.end() );
634 int faceSize = face.count();
639 for (
int i = 0; i < faceSize; ++i )
642 int iv1 = face[( i + 1 ) % faceSize];
643 int iv2 = face[( i + 2 ) % faceSize];
667 double crossProd = crossProduct( iv1, iv0, iv2, *
mesh );
668 if ( direction != 0 && crossProd * direction < 0 )
670 else if ( crossProd == 0 )
672 else if ( direction == 0 && crossProd != 0 )
673 direction = crossProd / std::fabs( crossProd );
678 for (
int i = 0; i < faceSize / 2; ++i )
681 face[i] = face.at( faceSize - i - 1 );
682 face[faceSize - i - 1] = temp;
691 QVector<int> oldToNewIndex( mMesh->
vertices.count(), -1 );
695 while ( oldIndex < verticesTotalCount )
703 oldToNewIndex[oldIndex] = newIndex;
704 if ( oldIndex != newIndex )
706 oldToNewIndex[oldIndex] = newIndex;
716 int facesTotalCount = mMesh->
faceCount();
717 while ( oldIndex < facesTotalCount )
719 if ( mMesh->
face( oldIndex ).isEmpty() )
723 if ( oldIndex != newIndex )
724 mMesh->
faces[newIndex] = mMesh->
faces[oldIndex];
726 for (
int i = 0; i < face.count(); ++i )
727 face[i] = oldToNewIndex[face.at( i )];
733 mMesh->
faces.resize( newIndex );
735 mVertexToFace.clear();
736 mFacesNeighborhood.clear();
741 QVector<int> oldToNewVerticesIndexes;
742 if ( !renumberVertices( oldToNewVerticesIndexes ) )
746 QVector<int> oldToNewFacesIndexes;
748 if ( !renumberFaces( oldToNewFacesIndexes ) )
753 QVector<QgsMeshVertex> tempVertices( mMesh->
vertices.count() );
754 for (
int i = 0; i < oldToNewVerticesIndexes.count(); ++i )
756 tempVertices[oldToNewVerticesIndexes.at( i )] = mMesh->
vertex( i );
760 QVector<QgsMeshFace> tempFaces( mMesh->
faces.count() );
761 for (
int i = 0; i < oldToNewFacesIndexes.count(); ++i )
763 tempFaces[oldToNewFacesIndexes.at( i )] = mMesh->
face( i );
765 QgsMeshFace &face = tempFaces[oldToNewFacesIndexes.at( i )];
767 for (
int fi = 0; fi < face.count(); ++fi )
769 face[fi] = oldToNewVerticesIndexes.at( face.at( fi ) );
773 mMesh->
faces = tempFaces;
779 bool QgsTopologicalMesh::renumberVertices( QVector<int> &oldToNewIndex )
const
781 std::vector<QgsMeshVertexCirculator> circulators;
782 circulators.reserve( mMesh->
vertices.count() );
783 int minDegree = std::numeric_limits<int>::max();
784 int minDegreeVertex = -1;
787 QSet<int> nonThreadedVertex;
788 oldToNewIndex = QVector<int> ( mMesh->
vertexCount(), -1 );
791 circulators.emplace_back( *
this, i );
793 if ( circulators.back().degree() < minDegree )
795 minDegreeVertex = circulators.size() - 1;
796 minDegree = circulator.
degree();
798 nonThreadedVertex.insert( i );
801 auto sortedNeighbor = [ = ]( QList<int> &neighbors,
int index )
815 int degree = circulators.at( neighborIndex ).degree();
816 QList<int>::Iterator it = neighbors.begin();
817 while ( it != neighbors.end() )
819 if ( degree <= circulators.at( *it ).degree() )
821 neighbors.insert( it, neighborIndex );
826 if ( it == neighbors.end() )
827 neighbors.append( neighborIndex );
833 int currentVertex = minDegreeVertex;
834 nonThreadedVertex.remove( minDegreeVertex );
836 while ( newIndex < mMesh->vertexCount() )
838 if ( oldToNewIndex[currentVertex] == -1 )
839 oldToNewIndex[currentVertex] = newIndex++;
841 if ( circulators.at( currentVertex ).isValid() )
843 QList<int> neighbors;
844 sortedNeighbor( neighbors, currentVertex );
846 for (
const int i : std::as_const( neighbors ) )
847 if ( oldToNewIndex.at( i ) == -1 && nonThreadedVertex.contains( i ) )
850 nonThreadedVertex.remove( i );
854 if ( queue.isEmpty() )
856 if ( nonThreadedVertex.isEmpty() && newIndex < mMesh->vertexCount() )
859 const QList<int> remainingVertex = qgis::setToList( nonThreadedVertex );
860 int minRemainingDegree = std::numeric_limits<int>::max();
861 int minRemainingVertex = -1;
862 for (
const int i : remainingVertex )
864 int degree = circulators.at( i ).degree();
865 if ( degree < minRemainingDegree )
867 minRemainingDegree = degree;
868 minRemainingVertex = i;
871 currentVertex = minRemainingVertex;
872 nonThreadedVertex.remove( currentVertex );
876 currentVertex = queue.dequeue();
883 bool QgsTopologicalMesh::renumberFaces( QVector<int> &oldToNewIndex )
const
886 QSet<int> nonThreadedFaces;
888 oldToNewIndex = QVector<int>( mMesh->
faceCount(), -1 );
890 QVector<int> faceDegrees( mMesh->
faceCount(), 0 );
892 int minDegree = std::numeric_limits<int>::max();
893 int minDegreeFace = -1;
894 for (
int faceIndex = 0; faceIndex < mMesh->
faceCount(); ++faceIndex )
896 const FaceNeighbors &neighbors = mFacesNeighborhood.at( faceIndex );
899 for (
int n = 0; n < neighbors.size(); ++n )
901 if ( neighbors.at( n ) != -1 )
905 if ( degree < minDegree )
908 minDegreeFace = faceIndex;
911 faceDegrees[faceIndex] = degree;
912 nonThreadedFaces.insert( faceIndex );
916 int currentFace = minDegreeFace;
917 nonThreadedFaces.remove( minDegreeFace );
919 auto sortedNeighbor = [ = ]( QList<int> &neighbors,
int index )
921 const FaceNeighbors &neighborhood = mFacesNeighborhood.at( index );
923 for (
int i = 0; i < neighborhood.count(); ++i )
925 int neighborIndex = neighborhood.at( i );
926 if ( neighborIndex == -1 )
929 int degree = faceDegrees.at( neighborIndex );
930 if ( neighbors.isEmpty() )
931 neighbors.append( neighborIndex );
934 QList<int>::Iterator it = neighbors.begin();
935 while ( it != neighbors.end() )
937 if ( degree <= faceDegrees.at( *it ) )
939 neighbors.insert( it, neighborIndex );
944 if ( it == neighbors.end() )
945 neighbors.append( neighborIndex );
950 while ( newIndex < mMesh->faceCount() )
952 if ( oldToNewIndex[currentFace] == -1 )
953 oldToNewIndex[currentFace] = newIndex++;
955 QList<int> neighbors;
956 sortedNeighbor( neighbors, currentFace );
958 for (
const int i : std::as_const( neighbors ) )
959 if ( oldToNewIndex.at( i ) == -1 && nonThreadedFaces.contains( i ) )
962 nonThreadedFaces.remove( i );
965 if ( queue.isEmpty() )
967 if ( nonThreadedFaces.isEmpty() && newIndex < mMesh->faceCount() )
970 const QList<int> remainingFace = qgis::setToList( nonThreadedFaces );
971 int minRemainingDegree = std::numeric_limits<int>::max();
972 int minRemainingFace = -1;
973 for (
const int i : remainingFace )
975 int degree = faceDegrees.at( i );
976 if ( degree < minRemainingDegree )
978 minRemainingDegree = degree;
979 minRemainingFace = i;
982 currentFace = minRemainingFace;
983 nonThreadedFaces.remove( currentFace );
987 currentFace = queue.dequeue();
1002 return mFacesToRemove;
1007 return mFaceIndexesToRemove;
1012 return mVerticesToAdd;
1017 return mChangeCoordinateVerticesIndexes;
1027 return mNewXYValues;
1032 return mOldXYValues;
1037 return mNativeFacesIndexesGeometryChanged;
1042 return ( mFaceIndexesToRemove.isEmpty() &&
1043 mFacesToAdd.isEmpty() &&
1044 mFacesNeighborhoodToAdd.isEmpty() &&
1045 mFacesToRemove.isEmpty() &&
1046 mFacesNeighborhoodToRemove.isEmpty() &&
1047 mNeighborhoodChanges.isEmpty() &&
1048 mVerticesToAdd.isEmpty() &&
1049 mVertexToFaceToAdd.isEmpty() &&
1050 mVerticesToRemoveIndexes.isEmpty() &&
1051 mRemovedVertices.isEmpty() &&
1052 mVerticesToFaceRemoved.isEmpty() &&
1053 mVerticesToFaceChanges.isEmpty() &&
1054 mChangeCoordinateVerticesIndexes.isEmpty() &&
1055 mNewZValues.isEmpty() &&
1056 mOldZValues.isEmpty() &&
1057 mNewXYValues.isEmpty() &&
1058 mOldXYValues.isEmpty() &&
1059 mNativeFacesIndexesGeometryChanged.isEmpty() );
1064 return mVerticesToRemoveIndexes;
1067 int QgsTopologicalMesh::Changes::addedFaceIndexInMesh(
int internalIndex )
const
1069 if ( internalIndex == -1 )
1072 return internalIndex + mAddedFacesFirstIndex;
1075 int QgsTopologicalMesh::Changes::removedFaceIndexInMesh(
int internalIndex )
const
1077 if ( internalIndex == -1 )
1080 return mFaceIndexesToRemove.at( internalIndex );
1085 mAddedFacesFirstIndex = 0;
1086 mFaceIndexesToRemove.clear();
1087 mFacesToAdd.clear();
1088 mFacesNeighborhoodToAdd.clear();
1089 mFacesToRemove.clear();
1090 mFacesNeighborhoodToRemove.clear();
1091 mNeighborhoodChanges.clear();
1093 mVerticesToAdd.clear();
1094 mVertexToFaceToAdd.clear();
1095 mVerticesToRemoveIndexes.clear();
1096 mRemovedVertices.clear();
1097 mVerticesToFaceRemoved.clear();
1098 mVerticesToFaceChanges.clear();
1100 mChangeCoordinateVerticesIndexes.clear();
1101 mNewZValues.clear();
1102 mOldZValues.clear();
1103 mNewXYValues.clear();
1104 mOldXYValues.clear();
1105 mNativeFacesIndexesGeometryChanged.clear();
1115 mVertexToFace.append( -1 );
1116 referenceAsFreeVertex( mMesh->
vertices.count() - 1 );
1122 static double vertexPolygonOrientation(
const QgsMesh &
mesh,
const QList<int> &vertexIndexes )
1124 if ( vertexIndexes.count() < 3 )
1127 int hullDomainVertexPos = -1;
1128 double xMin = std::numeric_limits<double>::max();
1129 double yMin = std::numeric_limits<double>::max();
1130 for (
int i = 0; i < vertexIndexes.count(); ++i )
1133 if ( xMin >= vertex.
x() && yMin > vertex.
y() )
1135 hullDomainVertexPos = i;
1141 if ( hullDomainVertexPos >= 0 )
1143 int iv1 = vertexIndexes.at( ( hullDomainVertexPos - 1 + vertexIndexes.count() ) % vertexIndexes.count() );
1144 int iv2 = vertexIndexes.at( ( hullDomainVertexPos + 1 ) % vertexIndexes.count() );
1145 int ivc = vertexIndexes.at( ( hullDomainVertexPos ) );
1146 double cp = crossProduct( ivc, iv1, iv2,
mesh );
1155 if ( vertexIndex >= mVertexToFace.count() )
1158 if ( mVertexToFace.at( vertexIndex ) == -1 )
1164 dereferenceAsFreeVertex( vertexIndex );
1172 QList<int> boundariesVertexIndex;
1173 QList<int> associateFaceToBoundaries;
1174 QList<int> removedFacesIndexes;
1175 QSet<int> boundaryInGlobalMesh;
1181 Q_ASSERT( !mMesh->
vertices.at( boundariesVertexIndex.last() ).isEmpty() );
1183 associateFaceToBoundaries.append( mFacesNeighborhood.at( circulator.
currentFaceIndex() ).at(
1184 vertexPositionInFace( boundariesVertexIndex.last(), currentFace ) ) );
1186 if ( currentFace.count() > 3 )
1188 int posInface = vertexPositionInFace( vertexIndex, currentFace );
1189 for (
int i = 2; i < currentFace.count() - 1; ++i )
1191 boundariesVertexIndex.append( currentFace.at( ( posInface + i ) % currentFace.count() ) );
1192 Q_ASSERT( !mMesh->
vertices.at( boundariesVertexIndex.last() ).isEmpty() );
1193 associateFaceToBoundaries.append( mFacesNeighborhood.at( circulator.
currentFaceIndex() ).at(
1194 vertexPositionInFace( boundariesVertexIndex.last(), currentFace ) ) );
1200 bool boundaryFill =
false;
1203 boundaryFill =
true;
1207 boundariesVertexIndex.append( lastVertexIndex );
1216 boundaryFill =
false;
1219 associateFaceToBoundaries.append( -1 );
1221 for (
const int index : std::as_const( boundariesVertexIndex ) )
1224 boundaryInGlobalMesh.insert( index );
1228 int currentVertexToFace = mVertexToFace.at( vertexIndex );
1232 QList<QList<int>> holes;
1233 QList<QList<int>> associateMeshFacesToHoles;
1235 bool cancelOperation =
false;
1243 int finalPos = boundariesVertexIndex.count() - 1;
1244 QList<int> uncoveredVertex;
1246 QList<int> partToCheck = boundariesVertexIndex.mid( startPos, finalPos - startPos + 1 );
1247 QList<int> associateFacePart = associateFaceToBoundaries.mid( startPos, finalPos - startPos + 1 );
1248 while ( startPos < finalPos && !partToCheck.isEmpty() )
1251 int secondPos = partToCheck.count() - 1;
1252 const QgsPoint &closingSegmentExtremety1 = mMesh->
vertex( partToCheck.at( 0 ) );
1253 const QgsPoint &closingSegmentExtremety2 = mMesh->
vertex( partToCheck.last() );
1254 bool isEdgeIntersect =
false;
1255 for (
int i = 1; i < secondPos - 1; ++i )
1259 bool isLineIntersection;
1262 if ( isEdgeIntersect )
1266 int index = partToCheck.at( 0 );
1267 if ( boundaryInGlobalMesh.contains( index ) && index != boundariesVertexIndex.at( 0 ) )
1269 cancelOperation =
true;
1275 if ( isEdgeIntersect || vertexPolygonOrientation( *mMesh, partToCheck ) >= 0 )
1277 partToCheck.removeLast();
1278 associateFacePart.removeAt( associateFacePart.count() - 2 );
1279 if ( partToCheck.count() == 1 )
1281 uncoveredVertex.append( index );
1282 startPos = startPos + 1;
1283 partToCheck = boundariesVertexIndex.mid( startPos, finalPos - startPos + 1 );
1284 associateFacePart = associateFaceToBoundaries.mid( startPos, finalPos - startPos + 1 );
1290 holes.append( partToCheck );
1291 associateMeshFacesToHoles.append( associateFacePart );
1293 startPos = startPos + partToCheck.count() - 1;
1294 uncoveredVertex.append( partToCheck.at( 0 ) );
1295 partToCheck = boundariesVertexIndex.mid( startPos, finalPos - startPos + 1 );
1296 associateFacePart = associateFaceToBoundaries.mid( startPos, finalPos - startPos + 1 );
1302 holes.append( boundariesVertexIndex );
1303 associateMeshFacesToHoles.append( associateFaceToBoundaries );
1306 if ( cancelOperation )
1312 Q_ASSERT( holes.count() == associateMeshFacesToHoles.count() );
1318 dereferenceAsFreeVertex( vertexIndex );
1320 mVertexToFace[vertexIndex] = -1;
1323 for (
int h = 0; h < holes.count(); ++h )
1325 const QList<int> &holeVertices = holes.at( h );
1326 const QList<int> &associateMeshFacesToHole = associateMeshFacesToHoles.at( h );
1327 QHash<p2t::Point *, int> mapPoly2TriPointToVertex;
1328 std::vector<p2t::Point *> holeToFill( holeVertices.count() );
1331 for (
int i = 0; i < holeVertices.count(); ++i )
1334 holeToFill[i] =
new p2t::Point( vertex.
x(), vertex.
y() );
1335 mapPoly2TriPointToVertex.insert( holeToFill[i], holeVertices.at( i ) );
1338 std::unique_ptr<p2t::CDT> cdt(
new p2t::CDT( holeToFill ) );
1341 std::vector<p2t::Triangle *> triangles = cdt->GetTriangles();
1342 QVector<QgsMeshFace> newFaces( triangles.size() );
1343 for (
size_t i = 0; i < triangles.size(); ++i )
1347 for (
int j = 0; j < 3; j++ )
1349 int vertInd = mapPoly2TriPointToVertex.value( triangles.at( i )->GetPoint( j ), -1 );
1350 if ( vertInd == -1 )
1351 throw std::exception();
1352 Q_ASSERT( !mMesh->
vertices.at( vertInd ).isEmpty() );
1360 throw std::exception();
1361 int newFaceIndexStartIndex = mMesh->
faceCount();
1368 const QList<int> &verticesToFaceToChange = topologicalFaces.mVerticesToFace.keys();
1369 for (
const int vtc : verticesToFaceToChange )
1370 if ( mVertexToFace.at( vtc ) == -1 )
1372 mVertexToFace.at( vtc ),
1373 addChanges.addedFaceIndexInMesh( topologicalFaces.mVerticesToFace.values( vtc ).first() ) } );
1377 for (
int i = 0; i < topologicalFaces.mFaces.count(); ++i )
1380 faceNeighbors = topologicalFaces.mFacesNeighborhood.at( i );
1381 for (
int n = 0; n < faceNeighbors.count(); ++n )
1383 if ( faceNeighbors.at( n ) != -1 )
1384 faceNeighbors[n] += newFaceIndexStartIndex;
1389 for (
int i = 0 ; i < holeVertices.count(); ++i )
1391 int vertexHoleIndex = holeVertices.at( i );
1392 int meshFaceBoundaryIndex = associateMeshFacesToHole.at( i );
1397 int newFaceBoundaryIndexInMesh = circulator.
currentFaceIndex() + newFaceIndexStartIndex;
1399 int positionInNewFaces = vertexPositionInFace( vertexHoleIndex, newFace );
1401 if ( meshFaceBoundaryIndex != -1 )
1404 int positionInMeshFaceBoundary = vertexPositionInFace( *mMesh, vertexHoleIndex, meshFaceBoundaryIndex );
1405 positionInMeshFaceBoundary = ( positionInMeshFaceBoundary - 1 + meshFace.count() ) % meshFace.count();
1407 addChanges.
mNeighborhoodChanges.append( {meshFaceBoundaryIndex, positionInMeshFaceBoundary, -1, newFaceBoundaryIndexInMesh} );
1418 for (
const std::array<int, 4> &neighborChangeToAdd : std::as_const( addChanges.
mNeighborhoodChanges ) )
1420 bool merged =
false;
1423 if ( existingNeighborChange.at( 0 ) == neighborChangeToAdd.at( 0 ) &&
1424 existingNeighborChange.at( 1 ) == neighborChangeToAdd.at( 1 ) )
1427 Q_ASSERT( existingNeighborChange.at( 3 ) == neighborChangeToAdd.at( 2 ) );
1428 existingNeighborChange[3] = neighborChangeToAdd.at( 3 );
1435 for (
const std::array<int, 3> &verticesToFaceToAdd : std::as_const( addChanges.
mVerticesToFaceChanges ) )
1437 bool merged =
false;
1440 if ( existingVerticesToFace.at( 0 ) == verticesToFaceToAdd.at( 0 ) )
1443 Q_ASSERT( existingVerticesToFace.at( 2 ) == verticesToFaceToAdd.at( 1 ) );
1444 existingVerticesToFace[2] = verticesToFaceToAdd.at( 2 );
1451 qDeleteAll( holeToFill );
1455 qDeleteAll( holeToFill );
1470 QSet<int> facesIndex;
1472 for (
int vertexIndex : vertices )
1479 for (
int vertexIndex : vertices )
1481 int currentVertexToFace = mVertexToFace.at( vertexIndex );
1487 dereferenceAsFreeVertex( vertexIndex );
1489 mVertexToFace[vertexIndex] = -1;
1497 QList<int> boundariesToCheckClockwiseInNewFaces = topologicFaces.mBoundaries;
1498 QList<std::array<int, 2>> boundariesToCheckCounterClockwiseInNewFaces;
1499 QList<int> uniqueSharedVertexBoundary;
1507 while ( !boundariesToCheckClockwiseInNewFaces.isEmpty() )
1509 int boundary = boundariesToCheckClockwiseInNewFaces.takeLast();
1511 const QList<int> &linkedFaces = topologicFaces.mVerticesToFace.values( boundary );
1513 for (
int const linkedFace : linkedFaces )
1517 if ( mVertexToFace.at( boundary ) == -1 )
1523 if ( !newFacescirculator.
isValid() )
1537 if ( oppositeVertexCCWInMesh == oppositeVertexInNewFaces )
1543 int faceSize = newFaceOnBoundary.size();
1544 int posInNewFace = vertexPositionInFace( boundary, newFaceOnBoundary );
1545 int previousVertexIndex = ( posInNewFace + faceSize - 1 ) % faceSize;
1546 if ( newFaceOnBoundary.at( previousVertexIndex ) == oppositeVertexCCWInMesh )
1554 if ( oppositeVertexCWInMesh == oppositeVertexInNewFaces )
1558 boundariesToCheckCounterClockwiseInNewFaces.append( {boundary, linkedFace} );
1563 while ( !boundariesToCheckCounterClockwiseInNewFaces.isEmpty() )
1565 std::array<int, 2> boundaryLinkedface = boundariesToCheckCounterClockwiseInNewFaces.takeLast();
1566 int boundary = boundaryLinkedface.at( 0 );
1567 int linkedFace = boundaryLinkedface.at( 1 );
1582 if ( oppositeVertexCWInMesh == oppositeVertexInNewFaces )
1589 if ( oppositeVertexCCWInMesh == oppositeVertexInNewFaces )
1592 uniqueSharedVertexBoundary.append( boundary );
1595 if ( !uniqueSharedVertexBoundary.isEmpty() )
1599 QSet<int> boundaryVertices = qgis::listToSet( topologicFaces.mBoundaries );
1600 for (
const QgsMeshFace &newFace : std::as_const( topologicFaces.mFaces ) )
1602 for (
const int vertexIndex : newFace )
1604 if ( boundaryVertices.contains( vertexIndex ) )
1606 if ( mVertexToFace.at( vertexIndex ) != -1 )
1617 mFacesNeighborhood.clear();
1618 mVerticesToFace.clear();
1619 mBoundaries.clear();
1624 return mFacesNeighborhood;
1629 if ( mVerticesToFace.contains( vertexIndex ) )
1630 return mVerticesToFace.values( vertexIndex ).at( 0 );
1638 topologicMesh.mMesh =
mesh;
1639 topologicMesh.mVertexToFace = QVector<int>(
mesh->
vertexCount(), -1 );
1640 topologicMesh.mMaximumVerticesPerFace = maxVerticesPerFace;
1647 if ( maxVerticesPerFace != 0 &&
mesh->
face( i ).count() > maxVerticesPerFace )
1665 topologicMesh.mFacesNeighborhood = subMesh.mFacesNeighborhood;
1667 for (
int i = 0; i < topologicMesh.mMesh->
vertexCount(); ++i )
1669 if ( topologicMesh.mVertexToFace.at( i ) == -1 )
1670 topologicMesh.mFreeVertices.insert( i );
1674 return topologicMesh;
1679 return createTopologicalFaces( faces,
nullptr, error, uniqueSharedVertexAllowed );
1684 const QVector<QgsMeshFace> &faces,
1685 QVector<int> *globalVertexToFace,
1687 bool allowUniqueSharedVertex )
1689 int facesCount = faces.count();
1690 QVector<FaceNeighbors> faceTopologies;
1691 QMultiHash<int, int> verticesToFace;
1694 TopologicalFaces ret;
1698 QMap<int, QMap<int, int>> verticesToNeighbor;
1700 for (
int faceIndex = 0; faceIndex < facesCount; ++faceIndex )
1703 int faceSize = face.count();
1705 for (
int i = 0; i < faceSize; ++i )
1707 int v1 = face[i % faceSize];
1708 int v2 = face[( i + 1 ) % faceSize];
1709 if ( verticesToNeighbor[v2].contains( v1 ) )
1715 verticesToNeighbor[v2].insert( v1, faceIndex );
1719 faceTopologies = QVector<FaceNeighbors>( faces.count() );
1721 QSet<int> boundaryVertices;
1723 for (
int faceIndex = 0; faceIndex < facesCount; ++faceIndex )
1726 int faceSize = face.size();
1728 faceTopology.resize( faceSize );
1730 for (
int i = 0; i < faceSize; ++i )
1732 int v1 = face.at( i );
1733 int v2 = face.at( ( i + 1 ) % faceSize );
1735 if ( globalVertexToFace )
1737 if ( ( *globalVertexToFace )[v1] == -1 )
1738 ( *globalVertexToFace )[v1] = faceIndex ;
1742 if ( allowUniqueSharedVertex || !verticesToFace.contains( v1 ) )
1743 verticesToFace.insert( v1, faceIndex ) ;
1746 QMap<int, int> &edges = verticesToNeighbor[v1];
1747 if ( edges.contains( v2 ) )
1748 faceTopology[i] = edges.value( v2 );
1751 faceTopology[i] = -1;
1753 if ( !allowUniqueSharedVertex )
1755 if ( boundaryVertices.contains( v1 ) )
1761 boundaryVertices.insert( v1 );
1767 ret.mFacesNeighborhood = faceTopologies;
1768 ret.mBoundaries = boundaryVertices.values();
1769 ret.mVerticesToFace = verticesToFace;
1775 return mFacesNeighborhood.at( faceIndex );
1787 QSet<int> removedFaces = qgis::listToSet( facesIndexes );
1788 QSet<int> concernedFaces = concernedFacesBy( facesIndexes );
1790 for (
const int f : std::as_const( removedFaces ) )
1791 concernedFaces.remove( f );
1793 QVector<QgsMeshFace> remainingFaces;
1794 remainingFaces.reserve( concernedFaces.count() );
1795 for (
const int f : std::as_const( concernedFaces ) )
1796 remainingFaces.append( mMesh->
face( f ) );
1799 createTopologicalFaces( remainingFaces,
nullptr, error,
false );
1811 QSet<int> indexSet = qgis::listToSet( facesIndexesToRemove );
1812 QSet<int> threatedVertex;
1814 for (
int i = 0; i < facesIndexesToRemove.count(); ++i )
1816 const int faceIndex = facesIndexesToRemove.at( i );
1819 const FaceNeighbors &neighborhood = mFacesNeighborhood.at( faceIndex );
1821 for (
int j = 0; j < face.count(); ++j )
1824 int neighborIndex = neighborhood.at( j );
1825 if ( neighborIndex != -1 && !indexSet.contains( neighborIndex ) )
1827 int positionInNeighbor = mFacesNeighborhood.at( neighborIndex ).indexOf( faceIndex );
1832 int vertexIndex = face.at( j );
1833 if ( !threatedVertex.contains( vertexIndex ) && indexSet.contains( mVertexToFace.at( vertexIndex ) ) )
1835 int oldValue = mVertexToFace.at( vertexIndex );
1838 if ( neighborIndex != -1 && !indexSet.contains( neighborIndex ) )
1839 refValue = neighborIndex;
1843 aroundFaces.removeOne( faceIndex );
1844 if ( !aroundFaces.isEmpty() )
1846 while ( !aroundFaces.isEmpty() && refValue == -1 )
1848 if ( !indexSet.contains( aroundFaces.first() ) )
1849 refValue = aroundFaces.first();
1851 aroundFaces.removeFirst();
1856 threatedVertex.insert( vertexIndex );
1866 bool QgsTopologicalMesh::eitherSideFacesAndVertices(
int vertexIndex1,
1870 int &neighborVertex1InFace1,
1871 int &neighborVertex1InFace2,
1872 int &neighborVertex2inFace1,
1873 int &neighborVertex2inFace2 )
const
1915 int oppositeVertexFace1;
1916 int oppositeVertexFace2;
1917 int supposedOppositeVertexFace1;
1918 int supposedoppositeVertexFace2;
1920 bool result = eitherSideFacesAndVertices(
1925 oppositeVertexFace1,
1926 supposedoppositeVertexFace2,
1927 supposedOppositeVertexFace1,
1928 oppositeVertexFace2 );
1933 oppositeVertexFace1 < 0 ||
1934 oppositeVertexFace2 < 0 ||
1935 supposedOppositeVertexFace1 != oppositeVertexFace1 ||
1936 supposedoppositeVertexFace2 != oppositeVertexFace2 )
1943 if ( face1.count() != 3 || face2.count() != 3 )
1946 double crossProduct1 = crossProduct( vertexIndex1, oppositeVertexFace1, oppositeVertexFace2, *mMesh );
1947 double crossProduct2 = crossProduct( vertexIndex2, oppositeVertexFace1, oppositeVertexFace2, *mMesh );
1949 return crossProduct1 * crossProduct2 < 0;
1956 int oppositeVertexFace1;
1957 int oppositeVertexFace2;
1958 int supposedOppositeVertexFace1;
1959 int supposedoppositeVertexFace2;
1961 bool result = eitherSideFacesAndVertices(
1966 oppositeVertexFace1,
1967 supposedoppositeVertexFace2,
1968 supposedOppositeVertexFace1,
1969 oppositeVertexFace2 );
1974 oppositeVertexFace1 < 0 ||
1975 oppositeVertexFace2 < 0 ||
1976 supposedOppositeVertexFace1 != oppositeVertexFace1 ||
1977 supposedoppositeVertexFace2 != oppositeVertexFace2 )
1986 Q_ASSERT( face1.count() == 3 );
1987 Q_ASSERT( face2.count() == 3 );
1989 int pos1 = vertexPositionInFace( vertexIndex1, face1 );
1990 int pos2 = vertexPositionInFace( vertexIndex2, face2 );
1992 int neighborFace1 = mFacesNeighborhood.at( faceIndex1 ).at( pos1 );
1993 int posInNeighbor1 = vertexPositionInFace( *mMesh, oppositeVertexFace1, neighborFace1 );
1994 int neighborFace2 = mFacesNeighborhood.at( faceIndex1 ).at( ( pos1 + 1 ) % 3 );
1995 int posInNeighbor2 = vertexPositionInFace( *mMesh, vertexIndex2, neighborFace2 );
1996 int neighborFace3 = mFacesNeighborhood.at( faceIndex2 ).at( pos2 );
1997 int posInNeighbor3 = vertexPositionInFace( *mMesh, oppositeVertexFace2, neighborFace3 );
1998 int neighborFace4 = mFacesNeighborhood.at( faceIndex2 ).at( ( pos2 + 1 ) % 3 );
1999 int posInNeighbor4 = vertexPositionInFace( *mMesh, vertexIndex1, neighborFace4 );
2009 changes.
mFacesToAdd.append( {oppositeVertexFace1, oppositeVertexFace2, vertexIndex1} );
2010 changes.
mFacesToAdd.append( {oppositeVertexFace2, oppositeVertexFace1, vertexIndex2} );
2012 mFacesNeighborhood.at( faceIndex2 ).at( ( pos2 + 1 ) % 3 ),
2013 mFacesNeighborhood.at( faceIndex1 ).at( pos1 )} );
2015 mFacesNeighborhood.at( faceIndex1 ).at( ( pos1 + 1 ) % 3 ),
2016 mFacesNeighborhood.at( faceIndex2 ).at( pos2 )} );
2018 if ( neighborFace1 >= 0 )
2019 changes.
mNeighborhoodChanges.append( {neighborFace1, posInNeighbor1, faceIndex1, startIndex} );
2020 if ( neighborFace2 >= 0 )
2021 changes.
mNeighborhoodChanges.append( {neighborFace2, posInNeighbor2, faceIndex1, startIndex + 1} );
2022 if ( neighborFace3 >= 0 )
2023 changes.
mNeighborhoodChanges.append( {neighborFace3, posInNeighbor3, faceIndex2, startIndex + 1} );
2024 if ( neighborFace4 >= 0 )
2025 changes.
mNeighborhoodChanges.append( {neighborFace4, posInNeighbor4, faceIndex2, startIndex} );
2028 if ( mVertexToFace.at( vertexIndex1 ) == faceIndex1 || mVertexToFace.at( vertexIndex1 ) == faceIndex2 )
2030 if ( mVertexToFace.at( vertexIndex2 ) == faceIndex1 || mVertexToFace.at( vertexIndex2 ) == faceIndex2 )
2031 changes.
mVerticesToFaceChanges.append( {vertexIndex2, mVertexToFace.at( vertexIndex2 ), startIndex + 1} );
2033 if ( mVertexToFace.at( oppositeVertexFace1 ) == faceIndex1 )
2036 if ( mVertexToFace.at( oppositeVertexFace2 ) == faceIndex2 )
2048 int neighborVertex1InFace1;
2049 int neighborVertex1InFace2;
2050 int neighborVertex2inFace1;
2051 int neighborVertex2inFace2;
2053 bool result = eitherSideFacesAndVertices(
2058 neighborVertex1InFace1,
2059 neighborVertex1InFace2,
2060 neighborVertex2inFace1,
2061 neighborVertex2inFace2 );
2071 if ( face1.count() + face2.count() - 2 > mMaximumVerticesPerFace )
2081 double crossProduct1 = crossProduct( vertexIndex1, neighborVertex1InFace1, neighborVertex1InFace2, *mMesh );
2082 double crossProduct2 = crossProduct( vertexIndex2, neighborVertex2inFace1, neighborVertex2inFace2, *mMesh );
2084 return crossProduct1 * crossProduct2 < 0;
2091 int neighborVertex1InFace1;
2092 int neighborVertex1InFace2;
2093 int neighborVertex2inFace1;
2094 int neighborVertex2inFace2;
2096 bool result = eitherSideFacesAndVertices(
2101 neighborVertex1InFace1,
2102 neighborVertex1InFace2,
2103 neighborVertex2inFace1,
2104 neighborVertex2inFace2 );
2115 int faceSize1 = face1.count();
2116 int faceSize2 = face2.count();
2118 int pos1 = vertexPositionInFace( vertexIndex1, face1 );
2119 int pos2 = vertexPositionInFace( vertexIndex2, face2 );
2132 for (
int i = 0; i < faceSize1 - 1; ++i )
2134 int currentPos = ( pos1 + i ) % faceSize1;
2135 newface.append( face1.at( currentPos ) );
2137 int currentNeighbor = mFacesNeighborhood.at( faceIndex1 ).at( currentPos );
2138 newNeighborhood.append( currentNeighbor );
2140 if ( currentNeighbor != -1 )
2142 int currentPosInNeighbor = vertexPositionInFace( *mMesh, face1.at( ( currentPos + 1 ) % faceSize1 ), currentNeighbor );
2143 changes.
mNeighborhoodChanges.append( {currentNeighbor, currentPosInNeighbor, faceIndex1, startIndex} );
2146 for (
int i = 0; i < faceSize2 - 1; ++i )
2148 int currentPos = ( pos2 + i ) % faceSize2;
2149 newface.append( face2.at( currentPos ) );
2151 int currentNeighbor = mFacesNeighborhood.at( faceIndex2 ).at( currentPos );
2152 newNeighborhood.append( currentNeighbor );
2154 if ( currentNeighbor != -1 )
2156 int currentPosInNeighbor = vertexPositionInFace( *mMesh, face2.at( ( currentPos + 1 ) % faceSize2 ), currentNeighbor );
2157 changes.
mNeighborhoodChanges.append( {currentNeighbor, currentPosInNeighbor, faceIndex2, startIndex} );
2161 for (
int i = 0; i < faceSize1; ++i )
2162 if ( mVertexToFace.at( face1.at( i ) ) == faceIndex1 )
2165 for (
int i = 0; i < faceSize2; ++i )
2166 if ( mVertexToFace.at( face2.at( i ) ) == faceIndex2 )
2181 return face.count() == 4;
2188 int faceSize = face.count();
2190 Q_ASSERT( faceSize == 4 );
2192 double maxAngle = 0;
2193 int splitVertexPos = -1;
2194 for (
int i = 0; i < faceSize; ++i )
2196 QgsVector vect1( mMesh->
vertex( face.at( i ) ) - mMesh->
vertex( face.at( ( i + 1 ) % faceSize ) ) );
2197 QgsVector vect2( mMesh->
vertex( face.at( ( i + 2 ) % faceSize ) ) - mMesh->
vertex( face.at( ( i + 1 ) % faceSize ) ) );
2199 double angle = std::abs( vect1.
angle( vect2 ) );
2201 if (
angle > maxAngle )
2204 splitVertexPos = ( i + 1 ) % faceSize;
2210 const QgsMeshFace newFace1 = {face.at( splitVertexPos ),
2211 face.at( ( splitVertexPos + 1 ) % faceSize ),
2212 face.at( ( splitVertexPos + 2 ) % faceSize )
2215 const QgsMeshFace newFace2 = {face.at( splitVertexPos ),
2216 face.at( ( splitVertexPos + 2 ) % faceSize ),
2217 face.at( ( splitVertexPos + 3 ) % faceSize )
2220 QVector<int> neighborIndex( faceSize );
2221 QVector<int> posInNeighbor( faceSize );
2223 for (
int i = 0; i < faceSize; ++i )
2225 neighborIndex[i] = mFacesNeighborhood.at( faceIndex ).at( ( splitVertexPos + i ) % faceSize );
2226 posInNeighbor[i] = vertexPositionInFace( *mMesh, face.at( ( splitVertexPos + i + 1 ) % faceSize ), neighborIndex[i] );
2238 mFacesNeighborhood.at( faceIndex ).at( ( splitVertexPos + 1 ) % faceSize ),
2241 mFacesNeighborhood.at( faceIndex ).at( ( splitVertexPos + 2 ) % faceSize ),
2242 mFacesNeighborhood.at( faceIndex ).at( ( splitVertexPos + 3 ) % faceSize )} );
2244 for (
int i = 0; i < faceSize; ++i )
2246 if ( neighborIndex[i] >= 0 )
2247 changes.
mNeighborhoodChanges.append( {neighborIndex[i], posInNeighbor[i], faceIndex, startIndex + int( i / 2 )} );
2249 int vertexIndex = face.at( ( splitVertexPos + i ) % faceSize );
2250 if ( mVertexToFace.at( vertexIndex ) == faceIndex )
2267 mVertexToFace.append( -1 );
2271 const FaceNeighbors includingFaceNeighborhood = mFacesNeighborhood.at( includingFaceIndex );
2272 int includingFaceSize = includingFace.count();
2274 for (
int i = 0; i < includingFaceSize; ++i )
2279 face[1] = includingFace.at( i );
2280 face[2] = includingFace.at( ( i + 1 ) % includingFaceSize );
2281 mMesh->
faces.append( face );
2284 int currentVertexIndex = includingFace.at( i );
2285 if ( mVertexToFace.at( currentVertexIndex ) == includingFaceIndex )
2287 int newFaceIndex = mMesh->
faceCount() - 1;
2288 mVertexToFace[currentVertexIndex] = newFaceIndex;
2292 int includingFaceNeighbor = includingFaceNeighborhood.at( i );
2296 includingFaceNeighbor,
2299 mFacesNeighborhood.append( neighbors );
2302 if ( includingFaceNeighbor != -1 )
2304 int indexInNeighbor = vertexPositionInFace( *mMesh, includingFace.at( ( i + 1 ) % includingFaceSize ), includingFaceNeighbor );
2305 int oldValue = mFacesNeighborhood[includingFaceNeighbor][indexInNeighbor];
2317 mVertexToFace[mVertexToFace.count() - 1] = mMesh->
faceCount() - 1;
2332 int newVertexPositionInFace1 = position + 1;
2334 auto triangulate = [
this, &changes](
int removedFaceIndex,
const QgsMeshVertex & newVertex,
int newVertexPosition, QVector<int> &edgeFacesIndexes )->
bool
2340 const int addedVertexIndex = mMesh->
vertexCount();
2343 int localStartIndex = changes.
mFacesToAdd.count();
2345 QVector<int> newBoundary = initialFace;
2346 newBoundary.insert( newVertexPosition, addedVertexIndex );
2350 QHash<p2t::Point *, int> mapPoly2TriPointToVertex;
2351 std::vector<p2t::Point *> faceToFill( newBoundary.count() );
2352 for (
int i = 0; i < newBoundary.count(); ++i )
2356 if ( newBoundary.at( i ) == addedVertexIndex )
2359 vert = mMesh->
vertex( newBoundary.at( i ) );
2361 faceToFill[i] =
new p2t::Point( vert.
x(), vert.
y() );
2362 mapPoly2TriPointToVertex.insert( faceToFill[i], newBoundary.at( i ) );
2365 std::unique_ptr<p2t::CDT> cdt(
new p2t::CDT( faceToFill ) );
2367 std::vector<p2t::Triangle *> triangles = cdt->GetTriangles();
2368 QVector<QgsMeshFace> newFaces( triangles.size() );
2369 for (
size_t i = 0; i < triangles.size(); ++i )
2373 for (
int j = 0; j < 3; j++ )
2375 int vertInd = mapPoly2TriPointToVertex.value( triangles.at( i )->GetPoint( j ), -1 );
2376 if ( vertInd == -1 )
2377 throw std::exception();
2385 throw std::exception();
2391 const QList<int> &verticesToFaceToChange = topologicalFaces.mVerticesToFace.keys();
2392 for (
const int vtc : verticesToFaceToChange )
2393 if ( vtc != addedVertexIndex && mVertexToFace.at( vtc ) == removedFaceIndex )
2398 topologicalFaces.
vertexToFace( vtc ) + faceStartGlobalIndex
2402 for (
int i = 0; i < topologicalFaces.mFaces.count(); ++i )
2405 for (
int n = 0; n < faceNeighbors.count(); ++n )
2407 if ( faceNeighbors.at( n ) != -1 )
2408 faceNeighbors[n] += faceStartGlobalIndex;
2412 edgeFacesIndexes.resize( 2 );
2414 for (
int i = 0 ; i < newBoundary.count(); ++i )
2416 int vertexIndex = newBoundary.at( i );
2419 int newFaceBoundaryLocalIndex = localStartIndex + circulator.
currentFaceIndex();
2421 int newFaceBoundaryIndexInMesh = faceStartGlobalIndex;
2423 int meshFaceBoundaryIndex;
2424 if ( i == newVertexPosition )
2426 meshFaceBoundaryIndex = -1;
2427 edgeFacesIndexes[0] = newFaceBoundaryLocalIndex;
2429 else if ( i == ( newVertexPosition + newBoundary.count() - 1 ) % newBoundary.count() )
2431 meshFaceBoundaryIndex = -1;
2432 edgeFacesIndexes[1] = newFaceBoundaryLocalIndex;
2435 meshFaceBoundaryIndex = mFacesNeighborhood.at( removedFaceIndex ).at( vertexPositionInFace( vertexIndex, initialFace ) );
2438 int positionInNewFaces = vertexPositionInFace( vertexIndex, newFace );
2440 if ( meshFaceBoundaryIndex != -1 )
2443 int positionInMeshFaceBoundary = vertexPositionInFace( *mMesh, vertexIndex, meshFaceBoundaryIndex );
2444 positionInMeshFaceBoundary = ( positionInMeshFaceBoundary - 1 + meshFace.count() ) % meshFace.count();
2447 positionInMeshFaceBoundary,
2449 newFaceBoundaryIndexInMesh +
2456 qDeleteAll( faceToFill );
2466 QVector<int> edgeFacesIndexes;
2467 if ( !triangulate( faceIndex, vertexToInsert, newVertexPositionInFace1, edgeFacesIndexes ) )
2475 int face2Index = mFacesNeighborhood.at( faceIndex ).at( position );
2476 if ( face2Index != -1 )
2479 int vertexPositionInFace2 = vertexPositionInFace( face1.at( position ), face2 );
2480 QVector<int> edgeFacesIndexesFace2;
2481 if ( !triangulate( face2Index, vertexToInsert, vertexPositionInFace2, edgeFacesIndexesFace2 ) )
2486 int pos1InFaceSide1 = vertexPositionInFace( addedVertexIndex, firstFaceSide1 );
2489 int pos2InFaceSide1 = vertexPositionInFace( addedVertexIndex, secondFaceSide1 );
2490 pos2InFaceSide1 = ( pos2InFaceSide1 + secondFaceSide1.size() - 1 ) % secondFaceSide1.size();
2493 int pos1InFaceSide2 = vertexPositionInFace( addedVertexIndex, firstFaceSide2 );
2496 int pos2InFaceSide2 = vertexPositionInFace( addedVertexIndex, secondFaceSide2 );
2497 pos2InFaceSide2 = ( pos2InFaceSide2 + secondFaceSide1.size() - 1 ) % secondFaceSide1.size();
2511 Q_ASSERT( verticesIndexes.count() == newValues.count() );
2514 changes.
mNewZValues.reserve( verticesIndexes.count() );
2515 changes.
mOldZValues.reserve( verticesIndexes.count() );
2516 for (
int i = 0; i < verticesIndexes.count(); ++i )
2530 Q_ASSERT( verticesIndexes.count() == newValues.count() );
2533 changes.
mNewXYValues.reserve( verticesIndexes.count() );
2534 changes.
mOldXYValues.reserve( verticesIndexes.count() );
2535 QSet<int> concernedFace;
2536 for (
int i = 0; i < verticesIndexes.count(); ++i )
2541 concernedFace.unite( qgis::listToSet(
facesAroundVertex( verticesIndexes.at( i ) ) ) );
@ 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) SIP_HOLDGIL
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 SIP_HOLDGIL
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...
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 facesCanBeRemoved(const QList< int > facesIndexes)
Returns whether faces with index in faceIndexes can be removed/ The method an error object with type ...
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...
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...
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.
Changes removeFaces(const QList< int > facesIndexes)
Removes faces with index in faceIndexes.
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 tha tis 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 SIP_HOLDGIL
Returns the angle of the vector in radians.
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)
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.