QGIS API Documentation 3.29.0-Master (ade4f0cf0f)
qgstopologicalmesh.cpp
Go to the documentation of this file.
1/***************************************************************************
2 qgstopologicalmesh.cpp - QgsTopologicalMesh
3
4 ---------------------
5 begin : 18.6.2021
6 copyright : (C) 2021 by Vincent Cloarec
7 email : vcloarec at gmail dot com
8 ***************************************************************************
9 * *
10 * This program is free software; you can redistribute it and/or modify *
11 * it under the terms of the GNU General Public License as published by *
12 * the Free Software Foundation; either version 2 of the License, or *
13 * (at your option) any later version. *
14 * *
15 ***************************************************************************/
16
17#include "qgis.h"
18#include "qgstopologicalmesh.h"
19#include "qgsmesheditor.h"
20#include "qgsmessagelog.h"
21#include "qgsgeometryutils.h"
22
23#include <poly2tri.h>
24#include <QSet>
25#include <QQueue>
26
27static int vertexPositionInFace( int vertexIndex, const QgsMeshFace &face )
28{
29 return face.indexOf( vertexIndex );
30}
31
32static int vertexPositionInFace( const QgsMesh &mesh, int vertexIndex, int faceIndex )
33{
34 if ( faceIndex < 0 || faceIndex >= mesh.faceCount() )
35 return -1;
36
37 return vertexPositionInFace( vertexIndex, mesh.face( faceIndex ) );
38}
39
40static double crossProduct( int centralVertex, int vertex1, int vertex2, const QgsMesh &mesh )
41{
42 QgsMeshVertex vc = mesh.vertices.at( centralVertex );
43 QgsMeshVertex v1 = mesh.vertices.at( vertex1 );
44 QgsMeshVertex v2 = mesh.vertices.at( vertex2 );
45
46 double ux1 = v1.x() - vc.x();
47 double uy1 = v1.y() - vc.y();
48 double vx1 = v2.x() - vc.x();
49 double vy1 = v2.y() - vc.y();
50
51 return ux1 * vy1 - uy1 * vx1;
52}
53
54
56 : mFaces( topologicalMesh.mMesh->faces )
57 , mFacesNeighborhood( topologicalMesh.mFacesNeighborhood )
58 , mVertexIndex( vertexIndex )
59{
60 if ( vertexIndex >= 0 && vertexIndex < topologicalMesh.mMesh->vertexCount() )
61 {
62 mCurrentFace = topologicalMesh.mVertexToFace[vertexIndex];
63 mIsValid = vertexPositionInFace( *topologicalMesh.mesh(), vertexIndex, mCurrentFace ) != -1;
64 }
65 else
66 {
67 mIsValid = false;
68 }
69
70 if ( mIsValid )
71 mLastValidFace = mCurrentFace;
72}
73
74QgsMeshVertexCirculator::QgsMeshVertexCirculator( const QgsTopologicalMesh::TopologicalFaces &topologicalFaces, int faceIndex, int vertexIndex )
75 : mFaces( topologicalFaces.mFaces )
76 , mFacesNeighborhood( topologicalFaces.mFacesNeighborhood )
77 , mVertexIndex( vertexIndex )
78{
79 const QgsMeshFace &face = topologicalFaces.mFaces.at( faceIndex );
80 mIsValid = vertexPositionInFace( vertexIndex, face ) != -1;
81
82 mCurrentFace = faceIndex;
83 mLastValidFace = mCurrentFace;
84}
85
87 : mFaces( topologicalFaces.mFaces )
88 , mFacesNeighborhood( topologicalFaces.mFacesNeighborhood )
89 , mVertexIndex( vertexIndex )
90{
91 if ( topologicalFaces.mVerticesToFace.contains( vertexIndex ) )
92 mCurrentFace = topologicalFaces.mVerticesToFace.values( vertexIndex ).first();
93 mLastValidFace = mCurrentFace;
94 mIsValid = mCurrentFace != -1;
95}
96
98{
99 if ( mCurrentFace == -1 )
100 mCurrentFace = mLastValidFace;
101 else
102 {
103 int currentPos = positionInCurrentFace();
104 Q_ASSERT( currentPos != -1 );
105
106 const QgsMeshFace &currentFace = mFaces.at( mCurrentFace );
107 int faceSize = currentFace.size();
108 mLastValidFace = mCurrentFace;
109 mCurrentFace = mFacesNeighborhood.at( mCurrentFace ).at( ( currentPos + faceSize - 1 ) % currentFace.count() );
110 }
111
112 return mCurrentFace;
113}
114
116{
117 if ( mCurrentFace == -1 )
118 mCurrentFace = mLastValidFace;
119 else
120 {
121 int currentPos = positionInCurrentFace();
122 Q_ASSERT( currentPos != -1 );
123
124 const QgsMeshFace &currentFace = mFaces.at( mCurrentFace );
125 int faceSize = currentFace.size();
126 mLastValidFace = mCurrentFace;
127 mCurrentFace = mFacesNeighborhood.at( mCurrentFace ).at( ( currentPos ) % faceSize );
128 }
129
130 return mCurrentFace;
131}
132
134{
135 return mCurrentFace;
136}
137
139{
140 if ( mCurrentFace != -1 )
141 return mFaces.at( mCurrentFace );
142 else
143 return QgsMeshFace();
144}
145
147{
148 if ( !isValid() )
149 return false;
150
151 if ( mCurrentFace == -1 )
152 mCurrentFace = mLastValidFace;
153
154 int firstFace = mCurrentFace;
155
156 while ( turnClockwise() != -1 && currentFaceIndex() != firstFace ) {}
157 if ( mCurrentFace == firstFace )
158 return false; // a complete turn, so the vertex is not a boundary vertex, something went wrong
159
160 return ( turnCounterClockwise() != -1 );
161}
162
164{
165 if ( !isValid() )
166 return false;
167
168 if ( mCurrentFace == -1 )
169 mCurrentFace = mLastValidFace;
170
171 int firstFace = mCurrentFace;
172
173 while ( turnCounterClockwise() != -1 && currentFaceIndex() != firstFace ) {}
174 if ( mCurrentFace == firstFace )
175 return false; // a complete turn, so the vertex is not a boundary vertex, something went wrong
176
177 return ( turnClockwise() != -1 );
178}
179
181{
182 if ( mCurrentFace == -1 )
183 return -1;
184
185 const QgsMeshFace &face = currentFace();
186
187 if ( face.isEmpty() )
188 return -1;
189
190 int vertexPosition = vertexPositionInFace( mVertexIndex, currentFace() );
191
192 if ( vertexPosition == -1 )
193 return -1;
194
195 return face.at( ( vertexPosition + 1 ) % face.count() );
196}
197
199{
200 if ( mCurrentFace == -1 )
201 return -1;
202
203 const QgsMeshFace &face = currentFace();
204
205 if ( face.isEmpty() )
206 return -1;
207
208 int vertexPosition = vertexPositionInFace( mVertexIndex, currentFace() );
209
210 if ( vertexPosition == -1 )
211 return -1;
212
213 return face.at( ( vertexPosition - 1 + face.count() ) % face.count() );
214}
215
217{
218 return mIsValid;
219}
220
222{
223 QList<int> ret;
224 if ( !isValid() )
225 return ret;
226
227 if ( mCurrentFace != -1 )
228 ret.append( mCurrentFace );
229 while ( turnCounterClockwise() != ret.first() && currentFaceIndex() != -1 )
230 ret.append( currentFaceIndex() );
231
232
233 if ( currentFaceIndex() == -1 ) //we encounter a boundary, restart with other direction
234 {
235 ret.clear();
236 if ( turnClockwise() == -1 )
237 return ret;
238 ret.append( currentFaceIndex() );
239 while ( turnClockwise() != -1 )
240 {
241 ret.append( currentFaceIndex() );
242 }
243 }
244
245 return ret;
246}
247
249{
250 if ( mDegree != -1 )
251 return mDegree;
252
253 mDegree = 0;
254 if ( !mIsValid )
255 return mDegree;
256
257 // if we are on the boundary, we count one more to take account of the circulator will
258 // not cover the last vertex (the other vertex on boundary)
260 mDegree = 2;
261 else
262 mDegree = 1;
263
264 int firstFace = currentFaceIndex();
265
266 while ( turnClockwise() != firstFace && currentFaceIndex() != -1 )
267 ++mDegree;
268
269 return mDegree;
270}
271
272
273int QgsMeshVertexCirculator::positionInCurrentFace() const
274{
275 if ( mCurrentFace < 0 || mCurrentFace > mFaces.count() )
276 return -1;
277
278 return vertexPositionInFace( mVertexIndex, mFaces.at( mCurrentFace ) );
279}
280
282{
283 Changes changes;
284 changes.mFacesToAdd = topologicalFaces.mFaces;
285 changes.mAddedFacesFirstIndex = mMesh->faceCount();
286
287 changes.mFacesNeighborhoodToAdd.resize( changes.mFacesToAdd.count() );
288 for ( int i = 0; i < changes.mFacesToAdd.count(); ++i )
289 changes.mFacesNeighborhoodToAdd[i] = QVector<int>( changes.mFacesToAdd.at( i ).count(), -1 );
290
291 for ( int boundary : topologicalFaces.mBoundaries )
292 {
293 //if the boundary is a free vertex in the destination mesh, no need to check
294 if ( mVertexToFace.at( boundary ) == -1 )
295 continue;
296
297 const QList<int> &linkedFaces = topologicalFaces.mVerticesToFace.values( boundary );
298 for ( int linkedFace : linkedFaces )
299 {
300 QgsMeshVertexCirculator newFacesCirculator( topologicalFaces, linkedFace, boundary );
301 //search for face boundary on clockwise side of new faces
302 newFacesCirculator.goBoundaryClockwise();
303 int oppositeVertexForNewFace = newFacesCirculator.oppositeVertexClockwise();
304 if ( mVertexToFace.at( oppositeVertexForNewFace ) == -1 )
305 continue;
306
307 QgsMeshVertexCirculator meshCirculator = vertexCirculator( boundary );
308 meshCirculator.goBoundaryCounterClockwise();
309 int oppositeVertexForMeshFace = meshCirculator.oppositeVertexCounterClockwise();
310
311 const QgsMeshFace &newFaceBoundary = newFacesCirculator.currentFace();
312 int boundaryPositionInNewFace = vertexPositionInFace( boundary, newFaceBoundary );
313
314 if ( oppositeVertexForMeshFace != oppositeVertexForNewFace )
315 {
316 changes.mFacesNeighborhoodToAdd[newFacesCirculator.currentFaceIndex()][boundaryPositionInNewFace] = -1 ;
317 }
318 else
319 {
320 const QgsMeshFace &meshFaceBoundary = meshCirculator.currentFace();
321 int boundaryPositionInMeshFace = vertexPositionInFace( meshCirculator.oppositeVertexCounterClockwise(), meshFaceBoundary );
322
323 changes.mNeighborhoodChanges.append( std::array<int, 4>(
324 {
325 meshCirculator.currentFaceIndex(),
326 boundaryPositionInMeshFace,
327 -1,
328 changes.addedFaceIndexInMesh( newFacesCirculator.currentFaceIndex() )
329 } ) );
330
331 changes.mFacesNeighborhoodToAdd[newFacesCirculator.currentFaceIndex()][boundaryPositionInNewFace] = meshCirculator.currentFaceIndex();
332 }
333 }
334 }
335
336 for ( int f = 0; f < changes.mFacesToAdd.count(); ++f )
337 for ( int n = 0; n < changes.mFacesToAdd.at( f ).count(); ++n )
338 if ( changes.mFacesNeighborhoodToAdd.at( f ).at( n ) == -1 )
339 changes.mFacesNeighborhoodToAdd[f][n] = changes.addedFaceIndexInMesh( topologicalFaces.mFacesNeighborhood.at( f ).at( n ) );
340
341 const QList<int> &verticesToFaceToChange = topologicalFaces.mVerticesToFace.keys();
342 for ( const int vtc : verticesToFaceToChange )
343 if ( mVertexToFace.at( vtc ) == -1 )
344 changes.mVerticesToFaceChanges.append( {vtc,
345 mVertexToFace.at( vtc ),
346 changes.addedFaceIndexInMesh( topologicalFaces.mVerticesToFace.values( vtc ).first() ) } );
347
348 applyChanges( changes );
349
350 return changes;
351}
352
354{
355 int initialVerticesCount = mMesh->vertices.count();
356 if ( !changes.mVerticesToAdd.empty() )
357 {
358 int newSize = mMesh->vertices.count() + changes.mVerticesToAdd.count();
359 mMesh->vertices.resize( newSize );
360 mVertexToFace.resize( newSize );
361 }
362
363 if ( !changes.mFacesToAdd.empty() )
364 {
365 int newSize = mMesh->faceCount() + changes.mFacesToAdd.count();
366 mMesh->faces.resize( newSize );
367 mFacesNeighborhood.resize( newSize );
368 }
369
370 for ( int i = 0; i < changes.mFacesToRemove.count(); ++i )
371 {
372 mMesh->faces[changes.removedFaceIndexInMesh( i )] = QgsMeshFace();
373 mFacesNeighborhood[changes.removedFaceIndexInMesh( i )] = FaceNeighbors();//changes.facesNeighborhoodToRemove[i];
374 }
375
376 for ( int i = 0; i < changes.mVerticesToRemoveIndexes.count(); ++i )
377 {
378 int vertexIndex = changes.mVerticesToRemoveIndexes.at( i );
379 if ( mVertexToFace.at( vertexIndex ) == -1 )
380 dereferenceAsFreeVertex( vertexIndex );
381 mMesh->vertices[vertexIndex] = QgsMeshVertex();
382 mVertexToFace[vertexIndex] = -1;
383 }
384
385 for ( int i = 0; i < changes.mVerticesToAdd.count(); ++i )
386 {
387 mMesh->vertices[initialVerticesCount + i] = changes.mVerticesToAdd.at( i );
388 mVertexToFace[initialVerticesCount + i] = changes.mVertexToFaceToAdd.at( i );
389 if ( changes.mVertexToFaceToAdd.at( i ) == -1 )
390 referenceAsFreeVertex( initialVerticesCount + i );
391 }
392
393 for ( int i = 0; i < changes.mFacesToAdd.count(); ++i )
394 {
395 mMesh->faces[changes.addedFaceIndexInMesh( i )] = changes.mFacesToAdd.at( i );
396 mFacesNeighborhood[changes.addedFaceIndexInMesh( i )] = changes.mFacesNeighborhoodToAdd.at( i );
397 }
398
399 for ( const std::array<int, 4> neigborChange : std::as_const( changes.mNeighborhoodChanges ) )
400 {
401 const int faceIndex = neigborChange.at( 0 );
402 const int positionInFace = neigborChange.at( 1 );
403 const int valueToApply = neigborChange.at( 3 );
404 mFacesNeighborhood[faceIndex][positionInFace] = valueToApply;
405 }
406
407 for ( const std::array<int, 3> vertexToFaceChange : std::as_const( changes.mVerticesToFaceChanges ) )
408 {
409 int vertexIndex = vertexToFaceChange.at( 0 );
410 mVertexToFace[vertexToFaceChange.at( 0 )] = vertexToFaceChange.at( 2 );
411
412 if ( vertexToFaceChange.at( 2 ) == -1 &&
413 vertexToFaceChange.at( 1 ) != -1 &&
414 !mMesh->vertices.at( vertexIndex ).isEmpty() )
415 referenceAsFreeVertex( vertexIndex );
416
417 if ( vertexToFaceChange.at( 1 ) == -1 && vertexToFaceChange.at( 2 ) != -1 )
418 dereferenceAsFreeVertex( vertexIndex );
419 }
420
421 for ( int i = 0; i < changes.mChangeCoordinateVerticesIndexes.count(); ++i )
422 {
423 int vertexIndex = changes.mChangeCoordinateVerticesIndexes.at( i );
424 if ( !changes.mNewZValues.isEmpty() )
425 mMesh->vertices[vertexIndex].setZ( changes.mNewZValues.at( i ) );
426 if ( !changes.mNewXYValues.isEmpty() )
427 {
428 const QgsPointXY &pt = changes.mNewXYValues.at( i );
429 mMesh->vertices[vertexIndex].setX( pt.x() );
430 mMesh->vertices[vertexIndex].setY( pt.y() );
431 }
432 }
433}
434
436{
437 for ( const std::array<int, 4> neigborChange : std::as_const( changes.mNeighborhoodChanges ) )
438 {
439 const int faceIndex = neigborChange.at( 0 );
440 const int positionInFace = neigborChange.at( 1 );
441 const int valueToApply = neigborChange.at( 2 );
442 mFacesNeighborhood[faceIndex][positionInFace] = valueToApply;
443 }
444
445 for ( int i = 0; i < changes.mFacesToRemove.count(); ++i )
446 {
447 mMesh->faces[changes.removedFaceIndexInMesh( i )] = changes.mFacesToRemove.at( i );
448 mFacesNeighborhood[changes.removedFaceIndexInMesh( i )] = changes.mFacesNeighborhoodToRemove.at( i );
449 }
450
451 for ( int i = 0; i < changes.mVerticesToRemoveIndexes.count(); ++i )
452 {
453 int vertexIndex = changes.mVerticesToRemoveIndexes.at( i );
454 mMesh->vertices[vertexIndex] = changes.mRemovedVertices.at( i );
455 mVertexToFace[vertexIndex] = changes.mVerticesToFaceRemoved.at( i );
456 if ( mVertexToFace.at( vertexIndex ) == -1 )
457 referenceAsFreeVertex( vertexIndex );
458 }
459
460 int verticesToFaceChangesCount = changes.mVerticesToFaceChanges.count();
461 for ( int i = 0; i < verticesToFaceChangesCount; ++i )
462 {
463 const std::array<int, 3> vertexToFaceChange = changes.mVerticesToFaceChanges.at( verticesToFaceChangesCount - i - 1 );
464 int vertexIndex = vertexToFaceChange.at( 0 );
465 mVertexToFace[vertexIndex] = vertexToFaceChange.at( 1 );
466
467 if ( vertexToFaceChange.at( 2 ) == -1 && vertexToFaceChange.at( 1 ) != -1 )
468 dereferenceAsFreeVertex( vertexIndex );
469
470 if ( vertexToFaceChange.at( 1 ) == -1 &&
471 vertexToFaceChange.at( 2 ) != -1 &&
472 !mMesh->vertex( vertexIndex ).isEmpty() )
473 referenceAsFreeVertex( vertexIndex );
474 }
475
476 if ( !changes.mFacesToAdd.empty() )
477 {
478 int newSize = mMesh->faceCount() - changes.mFacesToAdd.count();
479 mMesh->faces.resize( newSize );
480 mFacesNeighborhood.resize( newSize );
481 }
482
483 if ( !changes.mVerticesToAdd.isEmpty() )
484 {
485 int newSize = mMesh->vertexCount() - changes.mVerticesToAdd.count();
486
487 for ( int i = newSize; i < mMesh->vertexCount(); ++i )
488 if ( mVertexToFace.at( i ) == -1 )
489 dereferenceAsFreeVertex( i );
490
491 mMesh->vertices.resize( newSize );
492 mVertexToFace.resize( newSize );
493 }
494
495 for ( int i = 0; i < changes.mChangeCoordinateVerticesIndexes.count(); ++i )
496 {
497 int vertexIndex = changes.mChangeCoordinateVerticesIndexes.at( i );
498 if ( !changes.mOldZValues.isEmpty() )
499 mMesh->vertices[vertexIndex].setZ( changes.mOldZValues.at( i ) );
500 if ( !changes.mOldXYValues.isEmpty() )
501 {
502 const QgsPointXY &pt = changes.mOldXYValues.at( i );
503 mMesh->vertices[vertexIndex].setX( pt.x() );
504 mMesh->vertices[vertexIndex].setY( pt.y() );
505 }
506 }
507}
508
510{
511 return QgsMeshVertexCirculator( *this, vertexIndex );
512}
513
514QSet<int> QgsTopologicalMesh::concernedFacesBy( const QList<int> faceIndexes ) const
515{
516 QSet<int> faces;
517 for ( const int faceIndex : faceIndexes )
518 {
519 const QgsMeshFace &face = mMesh->face( faceIndex );
520 for ( int i = 0; i < face.count(); ++i )
521 {
522 const QList<int> around = facesAroundVertex( face.at( i ) );
523 faces.unite( QSet< int >( around.begin(), around.end() ) );
524 }
525 }
526 return faces;
527}
528
529void QgsTopologicalMesh::dereferenceAsFreeVertex( int vertexIndex )
530{
531 mFreeVertices.remove( vertexIndex );
532}
533
534void QgsTopologicalMesh::referenceAsFreeVertex( int vertexIndex )
535{
536 // QSet used to retrieve free vertex without going through all the vertices container.
537 // But maybe later we could use more sophisticated reference (spatial index?), to retrieve free vertex in an extent
538 mFreeVertices.insert( vertexIndex );
539}
540
542{
543 for ( int faceIndex = 0 ; faceIndex < mMesh->faces.count( ); ++faceIndex )
544 {
545 const QgsMeshFace &face = mMesh->faces.at( faceIndex );
546 const FaceNeighbors &neighborhood = mFacesNeighborhood.at( faceIndex );
547 if ( face.count() != neighborhood.count() )
549 for ( int i = 0; i < face.count(); ++i )
550 {
551 int vertexIndex = face.at( i );
552 // check if each vertices is linked to a face (not free vertex)
553 if ( mVertexToFace.at( vertexIndex ) == -1 )
555
556 int neighborIndex = neighborhood.at( i );
557 if ( neighborIndex != -1 )
558 {
559 const QgsMeshFace &neighborFace = mMesh->faces.at( neighborIndex );
560 if ( neighborFace.isEmpty() )
562 int neighborSize = neighborFace.size();
563 const FaceNeighbors &neighborhoodOfNeighbor = mFacesNeighborhood.at( neighborIndex );
564 int posInNeighbor = vertexPositionInFace( *mMesh, vertexIndex, neighborIndex );
565 if ( neighborhoodOfNeighbor.isEmpty() || neighborhoodOfNeighbor.at( ( posInNeighbor + neighborSize - 1 ) % neighborSize ) != faceIndex )
567 }
568 }
569 }
570
571 for ( int vertexIndex = 0; vertexIndex < mMesh->vertexCount(); ++vertexIndex )
572 {
573 if ( mVertexToFace.at( vertexIndex ) != -1 )
574 {
575 if ( !mMesh->face( mVertexToFace.at( vertexIndex ) ).contains( vertexIndex ) )
577
578 if ( facesAroundVertex( vertexIndex ).count() == 0 )
580 }
581 }
582
583 return QgsMeshEditingError();
584}
585
587{
588 QgsMesh temp = mesh;
590 createTopologicalMesh( &temp, maxVerticesPerFace, error );
591 return error;
592}
593
595{
596 return mMesh;
597}
598
599int QgsTopologicalMesh::firstFaceLinked( int vertexIndex ) const
600{
601 if ( vertexIndex < 0 || vertexIndex >= mMesh->vertexCount() )
602 return -1;
603 return mVertexToFace.at( vertexIndex );
604}
605
606bool QgsTopologicalMesh::isVertexOnBoundary( int vertexIndex ) const
607{
608 QgsMeshVertexCirculator circulator = vertexCirculator( vertexIndex );
609
610 if ( circulator.isValid() )
611 return circulator.goBoundaryClockwise();
612
613 return false;
614}
615
616bool QgsTopologicalMesh::isVertexFree( int vertexIndex ) const
617{
618 if ( vertexIndex < 0 || vertexIndex >= mMesh->vertexCount() )
619 return false;
620
621 if ( mMesh->vertices.at( vertexIndex ).isEmpty() )
622 return false;
623
624 return mVertexToFace.at( vertexIndex ) == -1;
625}
626
628{
629 return QList<int>( mFreeVertices.begin(), mFreeVertices.end() );
630}
631
633{
634 // First check if the face is convex and put it counter clockwise
635 // If the index are not well ordered (edges intersect), invalid face --> return false
636 int faceSize = face.count();
637 if ( faceSize < 3 )
639
640 int direction = 0;
641 for ( int i = 0; i < faceSize; ++i )
642 {
643 int iv0 = face[i];
644 int iv1 = face[( i + 1 ) % faceSize];
645 int iv2 = face[( i + 2 ) % faceSize];
646
647 if ( iv0 < 0 || iv0 >= mesh->vertexCount() )
649
650 if ( iv1 < 0 || iv1 >= mesh->vertexCount() )
652
653 if ( iv2 < 0 || iv2 >= mesh->vertexCount() )
655
656 const QgsMeshVertex &v0 = mesh->vertices.at( iv0 ) ;
657 const QgsMeshVertex &v1 = mesh->vertices.at( iv1 ) ;
658 const QgsMeshVertex &v2 = mesh->vertices.at( iv2 ) ;
659
660 if ( v0.isEmpty() )
662
663 if ( v1.isEmpty() )
665
666 if ( v2.isEmpty() )
668
669 double crossProd = crossProduct( iv1, iv0, iv2, *mesh ); //if cross product>0, we have two edges clockwise
670 if ( direction != 0 && crossProd * direction < 0 ) // We have a convex face or a (partially) flat face
672 else if ( crossProd == 0 )
674 else if ( direction == 0 && crossProd != 0 )
675 direction = crossProd / std::fabs( crossProd );
676 }
677
678 if ( direction > 0 )// clockwise --> reverse the order of the index;
679 {
680 for ( int i = 0; i < faceSize / 2; ++i )
681 {
682 int temp = face[i];
683 face[i] = face.at( faceSize - i - 1 );
684 face[faceSize - i - 1] = temp;
685 }
686 }
687
689}
690
692{
693 QVector<int> oldToNewIndex( mMesh->vertices.count(), -1 );
694 int verticesTotalCount = mMesh->vertexCount();
695 int oldIndex = 0;
696 int newIndex = 0;
697 while ( oldIndex < verticesTotalCount )
698 {
699 if ( mMesh->vertex( oldIndex ).isEmpty() )
700 {
701 oldIndex++;
702 }
703 else
704 {
705 oldToNewIndex[oldIndex] = newIndex;
706 if ( oldIndex != newIndex )
707 mMesh->vertices[newIndex] = mMesh->vertices[oldIndex];
708 oldToNewIndex[oldIndex] = newIndex;
709 oldIndex++;
710 newIndex++;
711 }
712 }
713
714 mMesh->vertices.resize( newIndex );
715
716 oldIndex = 0;
717 newIndex = 0;
718 int facesTotalCount = mMesh->faceCount();
719 while ( oldIndex < facesTotalCount )
720 {
721 if ( mMesh->face( oldIndex ).isEmpty() )
722 oldIndex++;
723 else
724 {
725 if ( oldIndex != newIndex )
726 mMesh->faces[newIndex] = mMesh->faces[oldIndex];
727 QgsMeshFace &face = mMesh->faces[newIndex];
728 for ( int i = 0; i < face.count(); ++i )
729 face[i] = oldToNewIndex[face.at( i )];
730 newIndex++;
731 oldIndex++;
732 }
733 }
734
735 mMesh->faces.resize( newIndex );
736
737 mVertexToFace.clear();
738 mFacesNeighborhood.clear();
739}
740
742{
743 QVector<int> oldToNewVerticesIndexes;
744 if ( !renumberVertices( oldToNewVerticesIndexes ) )
745 return false;
746
747
748 QVector<int> oldToNewFacesIndexes;
749
750 if ( !renumberFaces( oldToNewFacesIndexes ) )
751 return false;
752
753 // If we are here, we can apply the renumbering
754
755 QVector<QgsMeshVertex> tempVertices( mMesh->vertices.count() );
756 for ( int i = 0; i < oldToNewVerticesIndexes.count(); ++i )
757 {
758 tempVertices[oldToNewVerticesIndexes.at( i )] = mMesh->vertex( i );
759 }
760 mMesh->vertices = tempVertices;
761
762 QVector<QgsMeshFace> tempFaces( mMesh->faces.count() );
763 for ( int i = 0; i < oldToNewFacesIndexes.count(); ++i )
764 {
765 tempFaces[oldToNewFacesIndexes.at( i )] = mMesh->face( i );
766
767 QgsMeshFace &face = tempFaces[oldToNewFacesIndexes.at( i )];
768
769 for ( int fi = 0; fi < face.count(); ++fi )
770 {
771 face[fi] = oldToNewVerticesIndexes.at( face.at( fi ) );
772 }
773 }
774
775 mMesh->faces = tempFaces;
776
777 return true;
778
779}
780
781bool QgsTopologicalMesh::renumberVertices( QVector<int> &oldToNewIndex ) const
782{
783 std::vector<QgsMeshVertexCirculator> circulators;
784 circulators.reserve( mMesh->vertices.count() );
785 int minDegree = std::numeric_limits<int>::max();
786 int minDegreeVertex = -1;
787
788 QQueue<int> queue;
789 QSet<int> nonThreadedVertex;
790 oldToNewIndex = QVector<int> ( mMesh->vertexCount(), -1 );
791 for ( int i = 0; i < mMesh->vertexCount(); ++i )
792 {
793 circulators.emplace_back( *this, i );
794 const QgsMeshVertexCirculator &circulator = circulators.back();
795 if ( circulators.back().degree() < minDegree )
796 {
797 minDegreeVertex = circulators.size() - 1;
798 minDegree = circulator.degree();
799 }
800 nonThreadedVertex.insert( i );
801 }
802
803 auto sortedNeighbor = [ = ]( QList<int> &neighbors, int index )
804 {
805 const QgsMeshVertexCirculator &circ = circulators.at( index );
806
807 if ( !circ.isValid() )
808 return;
809
811 neighbors.append( circ.oppositeVertexCounterClockwise() );
812
813 int firsrFace = circ.currentFaceIndex();
814 do
815 {
816 int neighborIndex = circ.oppositeVertexClockwise();
817 int degree = circulators.at( neighborIndex ).degree();
818 QList<int>::Iterator it = neighbors.begin();
819 while ( it != neighbors.end() )
820 {
821 if ( degree <= circulators.at( *it ).degree() )
822 {
823 neighbors.insert( it, neighborIndex );
824 break;
825 }
826 it++;
827 }
828 if ( it == neighbors.end() )
829 neighbors.append( neighborIndex );
830 }
831 while ( circ.turnClockwise() != firsrFace && circ.currentFaceIndex() != -1 );
832 };
833
834 int newIndex = 0;
835 int currentVertex = minDegreeVertex;
836 nonThreadedVertex.remove( minDegreeVertex );
837
838 while ( newIndex < mMesh->vertexCount() )
839 {
840 if ( oldToNewIndex[currentVertex] == -1 )
841 oldToNewIndex[currentVertex] = newIndex++;
842
843 if ( circulators.at( currentVertex ).isValid() )
844 {
845 QList<int> neighbors;
846 sortedNeighbor( neighbors, currentVertex );
847
848 for ( const int i : std::as_const( neighbors ) )
849 if ( oldToNewIndex.at( i ) == -1 && nonThreadedVertex.contains( i ) )
850 {
851 queue.enqueue( i );
852 nonThreadedVertex.remove( i );
853 }
854 }
855
856 if ( queue.isEmpty() )
857 {
858 if ( nonThreadedVertex.isEmpty() && newIndex < mMesh->vertexCount() )
859 return false;
860
861 const QList<int> remainingVertex( nonThreadedVertex.constBegin(), nonThreadedVertex.constEnd() );
862 int minRemainingDegree = std::numeric_limits<int>::max();
863 int minRemainingVertex = -1;
864 for ( const int i : remainingVertex )
865 {
866 int degree = circulators.at( i ).degree();
867 if ( degree < minRemainingDegree )
868 {
869 minRemainingDegree = degree;
870 minRemainingVertex = i;
871 }
872 }
873 currentVertex = minRemainingVertex;
874 nonThreadedVertex.remove( currentVertex );
875 }
876 else
877 {
878 currentVertex = queue.dequeue();
879 }
880 }
881
882 return true;
883}
884
885bool QgsTopologicalMesh::renumberFaces( QVector<int> &oldToNewIndex ) const
886{
887 QQueue<int> queue;
888 QSet<int> nonThreadedFaces;
889
890 oldToNewIndex = QVector<int>( mMesh->faceCount(), -1 );
891
892 QVector<int> faceDegrees( mMesh->faceCount(), 0 );
893
894 int minDegree = std::numeric_limits<int>::max();
895 int minDegreeFace = -1;
896 for ( int faceIndex = 0; faceIndex < mMesh->faceCount(); ++faceIndex )
897 {
898 const FaceNeighbors &neighbors = mFacesNeighborhood.at( faceIndex );
899
900 int degree = 0;
901 for ( int n = 0; n < neighbors.size(); ++n )
902 {
903 if ( neighbors.at( n ) != -1 )
904 degree++;
905 }
906
907 if ( degree < minDegree )
908 {
909 minDegree = degree;
910 minDegreeFace = faceIndex;
911 }
912
913 faceDegrees[faceIndex] = degree;
914 nonThreadedFaces.insert( faceIndex );
915 }
916
917 int newIndex = 0;
918 int currentFace = minDegreeFace;
919 nonThreadedFaces.remove( minDegreeFace );
920
921 auto sortedNeighbor = [ = ]( QList<int> &neighbors, int index )
922 {
923 const FaceNeighbors &neighborhood = mFacesNeighborhood.at( index );
924
925 for ( int i = 0; i < neighborhood.count(); ++i )
926 {
927 int neighborIndex = neighborhood.at( i );
928 if ( neighborIndex == -1 )
929 continue;
930
931 int degree = faceDegrees.at( neighborIndex );
932 if ( neighbors.isEmpty() )
933 neighbors.append( neighborIndex );
934 else
935 {
936 QList<int>::Iterator it = neighbors.begin();
937 while ( it != neighbors.end() )
938 {
939 if ( degree <= faceDegrees.at( *it ) )
940 {
941 neighbors.insert( it, neighborIndex );
942 break;
943 }
944 it++;
945 }
946 if ( it == neighbors.end() )
947 neighbors.append( neighborIndex );
948 }
949 }
950 };
951
952 while ( newIndex < mMesh->faceCount() )
953 {
954 if ( oldToNewIndex[currentFace] == -1 )
955 oldToNewIndex[currentFace] = newIndex++;
956
957 QList<int> neighbors;
958 sortedNeighbor( neighbors, currentFace );
959
960 for ( const int i : std::as_const( neighbors ) )
961 if ( oldToNewIndex.at( i ) == -1 && nonThreadedFaces.contains( i ) )
962 {
963 queue.enqueue( i );
964 nonThreadedFaces.remove( i );
965 }
966
967 if ( queue.isEmpty() )
968 {
969 if ( nonThreadedFaces.isEmpty() && newIndex < mMesh->faceCount() )
970 return false;
971
972 const QList<int> remainingFace( nonThreadedFaces.constBegin(), nonThreadedFaces.constEnd() );
973 int minRemainingDegree = std::numeric_limits<int>::max();
974 int minRemainingFace = -1;
975 for ( const int i : remainingFace )
976 {
977 int degree = faceDegrees.at( i );
978 if ( degree < minRemainingDegree )
979 {
980 minRemainingDegree = degree;
981 minRemainingFace = i;
982 }
983 }
984 currentFace = minRemainingFace;
985 nonThreadedFaces.remove( currentFace );
986 }
987 else
988 {
989 currentFace = queue.dequeue();
990 }
991
992 }
993
994 return true;
995}
996
997QVector<QgsMeshFace> QgsTopologicalMesh::Changes::addedFaces() const
998{
999 return mFacesToAdd;
1000}
1001
1003{
1004 return mFacesToRemove;
1005}
1006
1008{
1009 return mFaceIndexesToRemove;
1010}
1011
1013{
1014 return mVerticesToAdd;
1015}
1016
1018{
1019 return mChangeCoordinateVerticesIndexes;
1020}
1021
1023{
1024 return mNewZValues;
1025}
1026
1028{
1029 return mNewXYValues;
1030}
1031
1033{
1034 return mOldXYValues;
1035}
1036
1038{
1039 return mNativeFacesIndexesGeometryChanged;
1040}
1041
1043{
1044 return ( mFaceIndexesToRemove.isEmpty() &&
1045 mFacesToAdd.isEmpty() &&
1046 mFacesNeighborhoodToAdd.isEmpty() &&
1047 mFacesToRemove.isEmpty() &&
1048 mFacesNeighborhoodToRemove.isEmpty() &&
1049 mNeighborhoodChanges.isEmpty() &&
1050 mVerticesToAdd.isEmpty() &&
1051 mVertexToFaceToAdd.isEmpty() &&
1052 mVerticesToRemoveIndexes.isEmpty() &&
1053 mRemovedVertices.isEmpty() &&
1054 mVerticesToFaceRemoved.isEmpty() &&
1055 mVerticesToFaceChanges.isEmpty() &&
1056 mChangeCoordinateVerticesIndexes.isEmpty() &&
1057 mNewZValues.isEmpty() &&
1058 mOldZValues.isEmpty() &&
1059 mNewXYValues.isEmpty() &&
1060 mOldXYValues.isEmpty() &&
1061 mNativeFacesIndexesGeometryChanged.isEmpty() );
1062}
1063
1065{
1066 return mVerticesToRemoveIndexes;
1067}
1068
1069int QgsTopologicalMesh::Changes::addedFaceIndexInMesh( int internalIndex ) const
1070{
1071 if ( internalIndex == -1 )
1072 return -1;
1073
1074 return internalIndex + mAddedFacesFirstIndex;
1075}
1076
1077int QgsTopologicalMesh::Changes::removedFaceIndexInMesh( int internalIndex ) const
1078{
1079 if ( internalIndex == -1 )
1080 return -1;
1081
1082 return mFaceIndexesToRemove.at( internalIndex );
1083}
1084
1086{
1087 mAddedFacesFirstIndex = 0;
1088 mFaceIndexesToRemove.clear();
1089 mFacesToAdd.clear();
1090 mFacesNeighborhoodToAdd.clear();
1091 mFacesToRemove.clear();
1092 mFacesNeighborhoodToRemove.clear();
1093 mNeighborhoodChanges.clear();
1094
1095 mVerticesToAdd.clear();
1096 mVertexToFaceToAdd.clear();
1097 mVerticesToRemoveIndexes.clear();
1098 mRemovedVertices.clear();
1099 mVerticesToFaceRemoved.clear();
1100 mVerticesToFaceChanges.clear();
1101
1102 mChangeCoordinateVerticesIndexes.clear();
1103 mNewZValues.clear();
1104 mOldZValues.clear();
1105 mNewXYValues.clear();
1106 mOldXYValues.clear();
1107 mNativeFacesIndexesGeometryChanged.clear();
1108}
1109
1111{
1112 Changes changes;
1113 changes.mVerticesToAdd.append( vertex );
1114 changes.mVertexToFaceToAdd.append( -1 );
1115
1116 mMesh->vertices.append( vertex );
1117 mVertexToFace.append( -1 );
1118 referenceAsFreeVertex( mMesh->vertices.count() - 1 );
1119
1120 return changes;
1121}
1122
1123// Returns the orientation of the polygon formed by mesh vertices, <0 counter clockwise; >0 clockwise
1124static double vertexPolygonOrientation( const QgsMesh &mesh, const QList<int> &vertexIndexes )
1125{
1126 if ( vertexIndexes.count() < 3 )
1127 return 0.0;
1128
1129 int hullDomainVertexPos = -1;
1130 double xMin = std::numeric_limits<double>::max();
1131 double yMin = std::numeric_limits<double>::max();
1132 for ( int i = 0; i < vertexIndexes.count(); ++i )
1133 {
1134 const QgsMeshVertex &vertex = mesh.vertices.at( vertexIndexes.at( i ) );
1135 if ( xMin >= vertex.x() && yMin > vertex.y() )
1136 {
1137 hullDomainVertexPos = i;
1138 xMin = vertex.x();
1139 yMin = vertex.y();
1140 }
1141 }
1142
1143 if ( hullDomainVertexPos >= 0 )
1144 {
1145 int iv1 = vertexIndexes.at( ( hullDomainVertexPos - 1 + vertexIndexes.count() ) % vertexIndexes.count() );
1146 int iv2 = vertexIndexes.at( ( hullDomainVertexPos + 1 ) % vertexIndexes.count() );
1147 int ivc = vertexIndexes.at( ( hullDomainVertexPos ) );
1148 double cp = crossProduct( ivc, iv1, iv2, mesh );
1149 return cp;
1150 }
1151
1152 return 0.0;
1153}
1154
1156{
1157 if ( vertexIndex >= mVertexToFace.count() )
1158 return Changes();
1159
1160 if ( mVertexToFace.at( vertexIndex ) == -1 ) //it is a free vertex
1161 {
1162 Changes changes;
1163 changes.mRemovedVertices.append( mMesh->vertices.at( vertexIndex ) );
1164 changes.mVerticesToRemoveIndexes.append( vertexIndex );
1165 changes.mVerticesToFaceRemoved.append( -1 );
1166 dereferenceAsFreeVertex( vertexIndex );
1167 mMesh->vertices[vertexIndex] = QgsMeshVertex();
1168 return changes;
1169 }
1170
1171 //search concerned faces
1172 QgsMeshVertexCirculator circulator = vertexCirculator( vertexIndex );
1173 circulator.goBoundaryClockwise();
1174 QList<int> boundariesVertexIndex;
1175 QList<int> associateFaceToBoundaries;
1176 QList<int> removedFacesIndexes;
1177 QSet<int> boundaryInGlobalMesh;
1178
1179 do
1180 {
1181 removedFacesIndexes.append( circulator.currentFaceIndex() );
1182 boundariesVertexIndex.append( circulator.oppositeVertexClockwise() );
1183 Q_ASSERT( !mMesh->vertices.at( boundariesVertexIndex.last() ).isEmpty() );
1184 const QgsMeshFace &currentFace = circulator.currentFace();
1185 associateFaceToBoundaries.append( mFacesNeighborhood.at( circulator.currentFaceIndex() ).at(
1186 vertexPositionInFace( boundariesVertexIndex.last(), currentFace ) ) );
1187
1188 if ( currentFace.count() > 3 ) // quad or more, need other vertices
1189 {
1190 int posInface = vertexPositionInFace( vertexIndex, currentFace );
1191 for ( int i = 2; i < currentFace.count() - 1; ++i )
1192 {
1193 boundariesVertexIndex.append( currentFace.at( ( posInface + i ) % currentFace.count() ) );
1194 Q_ASSERT( !mMesh->vertices.at( boundariesVertexIndex.last() ).isEmpty() );
1195 associateFaceToBoundaries.append( mFacesNeighborhood.at( circulator.currentFaceIndex() ).at(
1196 vertexPositionInFace( boundariesVertexIndex.last(), currentFace ) ) );
1197 }
1198 }
1199 }
1200 while ( circulator.turnCounterClockwise() != -1 && circulator.currentFaceIndex() != removedFacesIndexes.first() );
1201
1202 bool boundaryFill = false;
1203 if ( circulator.currentFaceIndex() == -1 ) //we are on boundary of the mesh
1204 {
1205 boundaryFill = true;
1206 //we need to add last vertex/boundary faces that was not added because we are on mesh boundary
1207 circulator.goBoundaryCounterClockwise();
1208 int lastVertexIndex = circulator.oppositeVertexCounterClockwise();
1209 boundariesVertexIndex.append( lastVertexIndex );
1210
1211 // but we can be on the case where the last vertex share an edge with the first point,
1212 // in the case, the associate face on boundarie is not -1, but the face on the other side of the edge
1213 QgsMeshVertexCirculator boundaryCirculator = vertexCirculator( lastVertexIndex );
1214 boundaryCirculator.goBoundaryCounterClockwise();
1215 if ( boundaryCirculator.oppositeVertexCounterClockwise() == boundariesVertexIndex.first() )
1216 {
1217 associateFaceToBoundaries.append( boundaryCirculator.currentFaceIndex() );
1218 boundaryFill = false; //we are not a boundary fill anymore
1219 }
1220 else
1221 associateFaceToBoundaries.append( -1 );
1222
1223 for ( const int index : std::as_const( boundariesVertexIndex ) )
1224 {
1225 if ( isVertexOnBoundary( index ) )
1226 boundaryInGlobalMesh.insert( index );
1227 }
1228 }
1229
1230 int currentVertexToFace = mVertexToFace.at( vertexIndex );
1231 // here, we use the method removeFaces that effectivly removes and then constructs changes
1232 Changes changes = removeFaces( removedFacesIndexes );
1233
1234 QList<QList<int>> holes;
1235 QList<QList<int>> associateMeshFacesToHoles;
1236
1237 bool cancelOperation = false;
1238
1239 if ( boundaryFill )
1240 {
1241 // The hole is not a closed polygon, we need to close it, but the closing segment can intersect another segments/vertices.
1242 // In this case we consider as many polygons as necessary.
1243
1244 int startPos = 0;
1245 int finalPos = boundariesVertexIndex.count() - 1;
1246 QList<int> uncoveredVertex;
1247
1248 QList<int> partToCheck = boundariesVertexIndex.mid( startPos, finalPos - startPos + 1 );
1249 QList<int> associateFacePart = associateFaceToBoundaries.mid( startPos, finalPos - startPos + 1 );
1250 while ( startPos < finalPos && !partToCheck.isEmpty() )
1251 {
1252 // check if we intersect an edge between first and second
1253 int secondPos = partToCheck.count() - 1;
1254 const QgsPoint &closingSegmentExtremety1 = mMesh->vertex( partToCheck.at( 0 ) );
1255 const QgsPoint &closingSegmentExtremety2 = mMesh->vertex( partToCheck.last() );
1256 bool isEdgeIntersect = false;
1257 for ( int i = 1; i < secondPos - 1; ++i )
1258 {
1259 const QgsPoint &p1 = mMesh->vertex( partToCheck.at( i ) );
1260 const QgsPoint &p2 = mMesh->vertex( partToCheck.at( i + 1 ) );
1261 bool isLineIntersection;
1262 QgsPoint intersectPoint;
1263 isEdgeIntersect = QgsGeometryUtils::segmentIntersection( closingSegmentExtremety1, closingSegmentExtremety2, p1, p2, intersectPoint, isLineIntersection, 1e-8, true );
1264 if ( isEdgeIntersect )
1265 break;
1266 }
1267
1268 int index = partToCheck.at( 0 );
1269 if ( boundaryInGlobalMesh.contains( index ) && index != boundariesVertexIndex.at( 0 ) )
1270 {
1271 cancelOperation = true;
1272 break;
1273 }
1274
1275 // if uncovered vertex is a boundary vertex in the global mesh (except first that is always a boundary in the global mesh)
1276 // This operation will leads to a unique shared vertex that is not allowed, you have to cancel the operation
1277 if ( isEdgeIntersect || vertexPolygonOrientation( *mMesh, partToCheck ) >= 0 )
1278 {
1279 partToCheck.removeLast();
1280 associateFacePart.removeAt( associateFacePart.count() - 2 );
1281 if ( partToCheck.count() == 1 )
1282 {
1283 uncoveredVertex.append( index );
1284 startPos = startPos + 1;
1285 partToCheck = boundariesVertexIndex.mid( startPos, finalPos - startPos + 1 );
1286 associateFacePart = associateFaceToBoundaries.mid( startPos, finalPos - startPos + 1 );
1287 }
1288 }
1289 else
1290 {
1291 // store the well defined hole
1292 holes.append( partToCheck );
1293 associateMeshFacesToHoles.append( associateFacePart );
1294
1295 startPos = startPos + partToCheck.count() - 1;
1296 uncoveredVertex.append( partToCheck.at( 0 ) );
1297 partToCheck = boundariesVertexIndex.mid( startPos, finalPos - startPos + 1 );
1298 associateFacePart = associateFaceToBoundaries.mid( startPos, finalPos - startPos + 1 );
1299 }
1300 }
1301 }
1302 else
1303 {
1304 holes.append( boundariesVertexIndex );
1305 associateMeshFacesToHoles.append( associateFaceToBoundaries );
1306 }
1307
1308 if ( cancelOperation )
1309 {
1310 reverseChanges( changes );
1311 return Changes();
1312 }
1313
1314 Q_ASSERT( holes.count() == associateMeshFacesToHoles.count() );
1315
1316 changes.mRemovedVertices.append( mMesh->vertices.at( vertexIndex ) );
1317 changes.mVerticesToRemoveIndexes.append( vertexIndex );
1318 changes.mVerticesToFaceRemoved.append( currentVertexToFace );
1319 // these changes contain information that will lead to reference the removed vertex as free vertex when reverse/reapply
1320 dereferenceAsFreeVertex( vertexIndex );
1321 mMesh->vertices[vertexIndex] = QgsMeshVertex();
1322 mVertexToFace[vertexIndex] = -1;
1323
1324 int oldFacesCount = mMesh->faceCount();
1325 for ( int h = 0; h < holes.count(); ++h )
1326 {
1327 const QList<int> &holeVertices = holes.at( h );
1328 const QList<int> &associateMeshFacesToHole = associateMeshFacesToHoles.at( h );
1329 QHash<p2t::Point *, int> mapPoly2TriPointToVertex;
1330 std::vector<p2t::Point *> holeToFill( holeVertices.count() );
1331 try
1332 {
1333 for ( int i = 0; i < holeVertices.count(); ++i )
1334 {
1335 const QgsMeshVertex &vertex = mMesh->vertex( holeVertices.at( i ) );
1336 holeToFill[i] = new p2t::Point( vertex.x(), vertex.y() );
1337 mapPoly2TriPointToVertex.insert( holeToFill[i], holeVertices.at( i ) );
1338 }
1339
1340 std::unique_ptr<p2t::CDT> cdt( new p2t::CDT( holeToFill ) );
1341
1342 cdt->Triangulate();
1343 std::vector<p2t::Triangle *> triangles = cdt->GetTriangles();
1344 QVector<QgsMeshFace> newFaces( triangles.size() );
1345 for ( size_t i = 0; i < triangles.size(); ++i )
1346 {
1347 QgsMeshFace &face = newFaces[i];
1348 face.resize( 3 );
1349 for ( int j = 0; j < 3; j++ )
1350 {
1351 int vertInd = mapPoly2TriPointToVertex.value( triangles.at( i )->GetPoint( j ), -1 );
1352 if ( vertInd == -1 )
1353 throw std::exception();
1354 Q_ASSERT( !mMesh->vertices.at( vertInd ).isEmpty() );
1355 face[j] = vertInd;
1356 }
1357 }
1358
1359 QgsMeshEditingError error;
1360 QgsTopologicalMesh::TopologicalFaces topologicalFaces = createNewTopologicalFaces( newFaces, false, error );
1362 throw std::exception();
1363 int newFaceIndexStartIndex = mMesh->faceCount();
1364 QgsTopologicalMesh::Changes addChanges;
1365 addChanges.mAddedFacesFirstIndex = newFaceIndexStartIndex;
1366 addChanges.mFacesToAdd = topologicalFaces.meshFaces();
1367 addChanges.mFacesNeighborhoodToAdd = topologicalFaces.mFacesNeighborhood;
1368
1369 // vertices to face changes
1370 const QList<int> &verticesToFaceToChange = topologicalFaces.mVerticesToFace.keys();
1371 for ( const int vtc : verticesToFaceToChange )
1372 if ( mVertexToFace.at( vtc ) == -1 )
1373 addChanges.mVerticesToFaceChanges.append( {vtc,
1374 mVertexToFace.at( vtc ),
1375 addChanges.addedFaceIndexInMesh( topologicalFaces.mVerticesToFace.values( vtc ).first() ) } );
1376
1377
1378 // reindex neighborhood for new faces
1379 for ( int i = 0; i < topologicalFaces.mFaces.count(); ++i )
1380 {
1381 FaceNeighbors &faceNeighbors = addChanges.mFacesNeighborhoodToAdd[i];
1382 faceNeighbors = topologicalFaces.mFacesNeighborhood.at( i );
1383 for ( int n = 0; n < faceNeighbors.count(); ++n )
1384 {
1385 if ( faceNeighbors.at( n ) != -1 )
1386 faceNeighbors[n] += newFaceIndexStartIndex; //reindex internal neighborhood
1387 }
1388 }
1389
1390 // link neighborhood for boundaries of each side
1391 for ( int i = 0 ; i < holeVertices.count(); ++i )
1392 {
1393 int vertexHoleIndex = holeVertices.at( i );
1394 int meshFaceBoundaryIndex = associateMeshFacesToHole.at( i );
1395
1396 const QgsMeshVertexCirculator circulator = QgsMeshVertexCirculator( topologicalFaces, vertexHoleIndex );
1397 circulator.goBoundaryClockwise();
1398 int newFaceBoundaryLocalIndex = circulator.currentFaceIndex();
1399 int newFaceBoundaryIndexInMesh = circulator.currentFaceIndex() + newFaceIndexStartIndex;
1400 const QgsMeshFace &newFace = circulator.currentFace();
1401 int positionInNewFaces = vertexPositionInFace( vertexHoleIndex, newFace );
1402
1403 if ( meshFaceBoundaryIndex != -1 )
1404 {
1405 const QgsMeshFace meshFace = mMesh->face( meshFaceBoundaryIndex );
1406 int positionInMeshFaceBoundary = vertexPositionInFace( *mMesh, vertexHoleIndex, meshFaceBoundaryIndex );
1407 positionInMeshFaceBoundary = ( positionInMeshFaceBoundary - 1 + meshFace.count() ) % meshFace.count(); //take the position just before
1408
1409 addChanges.mNeighborhoodChanges.append( {meshFaceBoundaryIndex, positionInMeshFaceBoundary, -1, newFaceBoundaryIndexInMesh} );
1410 }
1411
1412 addChanges.mFacesNeighborhoodToAdd[newFaceBoundaryLocalIndex][positionInNewFaces] = meshFaceBoundaryIndex;
1413 }
1414
1415 applyChanges( addChanges );
1416
1417 changes.mFacesToAdd.append( addChanges.mFacesToAdd );
1418 changes.mFacesNeighborhoodToAdd.append( addChanges.mFacesNeighborhoodToAdd );
1419 //for each neighborhood change, check if a corresponding change already exist and merge them, if not just append
1420 for ( const std::array<int, 4> &neighborChangeToAdd : std::as_const( addChanges.mNeighborhoodChanges ) )
1421 {
1422 bool merged = false;
1423 for ( std::array<int, 4> &existingNeighborChange : changes.mNeighborhoodChanges )
1424 {
1425 if ( existingNeighborChange.at( 0 ) == neighborChangeToAdd.at( 0 ) &&
1426 existingNeighborChange.at( 1 ) == neighborChangeToAdd.at( 1 ) )
1427 {
1428 merged = true;
1429 Q_ASSERT( existingNeighborChange.at( 3 ) == neighborChangeToAdd.at( 2 ) );
1430 existingNeighborChange[3] = neighborChangeToAdd.at( 3 );
1431 }
1432 }
1433 if ( !merged )
1434 changes.mNeighborhoodChanges.append( neighborChangeToAdd );
1435 }
1436 //for each vertex to face change, check if a corresponding change already exist and merge them, if not just append
1437 for ( const std::array<int, 3> &verticesToFaceToAdd : std::as_const( addChanges.mVerticesToFaceChanges ) )
1438 {
1439 bool merged = false;
1440 for ( std::array<int, 3> &existingVerticesToFace : changes.mVerticesToFaceChanges )
1441 {
1442 if ( existingVerticesToFace.at( 0 ) == verticesToFaceToAdd.at( 0 ) )
1443 {
1444 merged = true;
1445 Q_ASSERT( existingVerticesToFace.at( 2 ) == verticesToFaceToAdd.at( 1 ) );
1446 existingVerticesToFace[2] = verticesToFaceToAdd.at( 2 );
1447 }
1448 }
1449 if ( !merged )
1450 changes.mVerticesToFaceChanges.append( verticesToFaceToAdd );
1451 }
1452
1453 qDeleteAll( holeToFill );
1454 }
1455 catch ( ... )
1456 {
1457 qDeleteAll( holeToFill );
1458 QgsMessageLog::logMessage( QObject::tr( "Triangulation failed. Skipping holeā€¦" ), QObject::tr( "Mesh Editing" ) );
1459 }
1460 }
1461 changes.mAddedFacesFirstIndex = oldFacesCount;
1462
1463
1464
1465 changes.mAddedFacesFirstIndex = oldFacesCount;
1466
1467 return changes;
1468}
1469
1471{
1472 QSet<int> facesIndex;
1473 //Search for associated faces
1474 for ( int vertexIndex : vertices )
1475 {
1476 const QList< int > faces = facesAroundVertex( vertexIndex );
1477 facesIndex.unite( QSet< int >( faces.begin(), faces.end() ) );
1478 }
1479
1480 // remove the faces
1481 Changes changes = removeFaces( facesIndex.values() );
1482
1483 // removes the vertices
1484 for ( int vertexIndex : vertices )
1485 {
1486 int currentVertexToFace = mVertexToFace.at( vertexIndex );
1487 // here, we use the method removeFaces that effectivly removes and then constructs changes
1488 changes.mRemovedVertices.append( mMesh->vertices.at( vertexIndex ) );
1489 changes.mVerticesToRemoveIndexes.append( vertexIndex );
1490 changes.mVerticesToFaceRemoved.append( currentVertexToFace );
1491 // these changes contain information that will lead to reference the removed vertex as free vertex when reverse/reapply
1492 dereferenceAsFreeVertex( vertexIndex );
1493 mMesh->vertices[vertexIndex] = QgsMeshVertex();
1494 mVertexToFace[vertexIndex] = -1;
1495 }
1496
1497 return changes;
1498}
1499
1501{
1502 QList<int> boundariesToCheckClockwiseInNewFaces = topologicFaces.mBoundaries;
1503 QList<std::array<int, 2>> boundariesToCheckCounterClockwiseInNewFaces; //couple boundary / associate face in topologicFaces.mVerticesToFace
1504 QList<int> uniqueSharedVertexBoundary;
1505
1506
1507 // Go through the boundary and search for opposite boundary vertex clockwise in new faces and compare
1508 // with boundary opposite vertices on the mesh
1509 // If, in the mesh, the opposite vertex counter clockwise is not the same , another check will be done
1510 // later with counter clockwise in new faces
1511 // If, in the mesh, the opposite vertex clockwise is the same, this is an error
1512 while ( !boundariesToCheckClockwiseInNewFaces.isEmpty() )
1513 {
1514 int boundary = boundariesToCheckClockwiseInNewFaces.takeLast();
1515
1516 const QList<int> &linkedFaces = topologicFaces.mVerticesToFace.values( boundary );
1517
1518 for ( int const linkedFace : linkedFaces )
1519 {
1520
1521 //if the boundary is a free vertex in the destination mesh, no need to check
1522 if ( mVertexToFace.at( boundary ) == -1 )
1523 continue;
1524
1525 QgsMeshVertexCirculator newFacescirculator( topologicFaces, linkedFace, boundary );
1526 QgsMeshVertexCirculator meshCirculator = vertexCirculator( boundary );
1527
1528 if ( !newFacescirculator.isValid() )
1530
1531 //Get the opposite vertex on the clockwise side with new faces block
1532 if ( !newFacescirculator.goBoundaryClockwise() )
1534
1535 int oppositeVertexInNewFaces = newFacescirculator.oppositeVertexClockwise();
1536
1537 if ( !meshCirculator.goBoundaryCounterClockwise() )
1539
1540 int oppositeVertexCCWInMesh = meshCirculator.oppositeVertexCounterClockwise();
1541
1542 if ( oppositeVertexCCWInMesh == oppositeVertexInNewFaces ) //this boundary is OK, continue wit next one
1543 continue;
1544 else
1545 {
1546 //to avoid manifold face that could pass through the check, compare not only the boundary edges but also with the opposite internal edge in new face
1547 const QgsMeshFace &newFaceOnBoundary = newFacescirculator.currentFace();
1548 int faceSize = newFaceOnBoundary.size();
1549 int posInNewFace = vertexPositionInFace( boundary, newFaceOnBoundary );
1550 int previousVertexIndex = ( posInNewFace + faceSize - 1 ) % faceSize;
1551 if ( newFaceOnBoundary.at( previousVertexIndex ) == oppositeVertexCCWInMesh )
1553 }
1554
1555 meshCirculator.goBoundaryClockwise();
1556
1557 int oppositeVertexCWInMesh = meshCirculator.oppositeVertexClockwise();
1558
1559 if ( oppositeVertexCWInMesh == oppositeVertexInNewFaces )
1561
1562 //if we are here we need more checks
1563 boundariesToCheckCounterClockwiseInNewFaces.append( {boundary, linkedFace} );
1564 }
1565 }
1566
1567 // Check now with opposite boundary vertex counter clockwise in new faces
1568 while ( !boundariesToCheckCounterClockwiseInNewFaces.isEmpty() )
1569 {
1570 std::array<int, 2> boundaryLinkedface = boundariesToCheckCounterClockwiseInNewFaces.takeLast();
1571 int boundary = boundaryLinkedface.at( 0 );
1572 int linkedFace = boundaryLinkedface.at( 1 );
1573
1574 QgsMeshVertexCirculator newFacescirculator( topologicFaces, linkedFace, boundary );
1575 QgsMeshVertexCirculator meshCirculator = vertexCirculator( boundary );
1576
1577 if ( !newFacescirculator.goBoundaryCounterClockwise() )
1579
1580 int oppositeVertexInNewFaces = newFacescirculator.oppositeVertexCounterClockwise();
1581
1582 if ( !meshCirculator.goBoundaryClockwise() )
1584
1585 int oppositeVertexCWInMesh = meshCirculator.oppositeVertexClockwise();
1586
1587 if ( oppositeVertexCWInMesh == oppositeVertexInNewFaces ) //this boundary is OK, continue with next one
1588 continue;
1589
1590 meshCirculator.goBoundaryCounterClockwise();
1591
1592 int oppositeVertexCCWInMesh = meshCirculator.oppositeVertexCounterClockwise();
1593
1594 if ( oppositeVertexCCWInMesh == oppositeVertexInNewFaces )
1596
1597 uniqueSharedVertexBoundary.append( boundary );
1598 }
1599
1600 if ( !uniqueSharedVertexBoundary.isEmpty() )
1601 return QgsMeshEditingError( Qgis::MeshEditingErrorType::UniqueSharedVertex, uniqueSharedVertexBoundary.first() );
1602
1603 // Check if internal vertices of new faces block are free in the mesh
1604 QSet<int> boundaryVertices( topologicFaces.mBoundaries.constBegin(), topologicFaces.mBoundaries.constEnd() );
1605 for ( const QgsMeshFace &newFace : std::as_const( topologicFaces.mFaces ) )
1606 {
1607 for ( const int vertexIndex : newFace )
1608 {
1609 if ( boundaryVertices.contains( vertexIndex ) )
1610 continue;
1611 if ( mVertexToFace.at( vertexIndex ) != -1 )
1613 }
1614 }
1615
1616 return QgsMeshEditingError();
1617}
1618
1620{
1621 mFaces.clear();
1622 mFacesNeighborhood.clear();
1623 mVerticesToFace.clear();
1624 mBoundaries.clear();
1625}
1626
1627QVector<QgsTopologicalMesh::FaceNeighbors> QgsTopologicalMesh::TopologicalFaces::facesNeighborhood() const
1628{
1629 return mFacesNeighborhood;
1630}
1631
1633{
1634 if ( mVerticesToFace.contains( vertexIndex ) )
1635 return mVerticesToFace.values( vertexIndex ).at( 0 );
1636
1637 return -1;
1638}
1639
1641{
1642 QgsTopologicalMesh topologicMesh;
1643 topologicMesh.mMesh = mesh;
1644 topologicMesh.mVertexToFace = QVector<int>( mesh->vertexCount(), -1 );
1645 topologicMesh.mMaximumVerticesPerFace = maxVerticesPerFace;
1647
1648 for ( int i = 0; i < mesh->faceCount(); ++i )
1649 {
1650 if ( mesh->face( i ).isEmpty() )
1651 continue;
1652 if ( maxVerticesPerFace != 0 && mesh->face( i ).count() > maxVerticesPerFace )
1653 {
1655 break;
1656 }
1657
1658 error = counterClockwiseFaces( mesh->faces[i], mesh );
1660 {
1662 error.elementIndex = i;
1663 break;
1664 }
1665 }
1666
1668 {
1669 TopologicalFaces subMesh = createTopologicalFaces( mesh->faces, &topologicMesh.mVertexToFace, error, false );
1670 topologicMesh.mFacesNeighborhood = subMesh.mFacesNeighborhood;
1671
1672 for ( int i = 0; i < topologicMesh.mMesh->vertexCount(); ++i )
1673 {
1674 if ( topologicMesh.mVertexToFace.at( i ) == -1 )
1675 topologicMesh.mFreeVertices.insert( i );
1676 }
1677 }
1678
1679 return topologicMesh;
1680}
1681
1682QgsTopologicalMesh::TopologicalFaces QgsTopologicalMesh::createNewTopologicalFaces( const QVector<QgsMeshFace> &faces, bool uniqueSharedVertexAllowed, QgsMeshEditingError &error )
1683{
1684 return createTopologicalFaces( faces, nullptr, error, uniqueSharedVertexAllowed );
1685}
1686
1687
1688QgsTopologicalMesh::TopologicalFaces QgsTopologicalMesh::createTopologicalFaces(
1689 const QVector<QgsMeshFace> &faces,
1690 QVector<int> *globalVertexToFace,
1691 QgsMeshEditingError &error,
1692 bool allowUniqueSharedVertex )
1693{
1694 int facesCount = faces.count();
1695 QVector<FaceNeighbors> faceTopologies;
1696 QMultiHash<int, int> verticesToFace;
1697
1698 error = QgsMeshEditingError();
1699 TopologicalFaces ret;
1700
1701 // Contains for each vertex a map (opposite vertex # edge) --> face index
1702 // when turning counter clockwise, if v1 first vertex and v2 second one, [v1][v2]--> neighbor face
1703 QMap<int, QMap<int, int>> verticesToNeighbor;
1704
1705 for ( int faceIndex = 0; faceIndex < facesCount; ++faceIndex )
1706 {
1707 const QgsMeshFace &face = faces.at( faceIndex );
1708 int faceSize = face.count();
1709 //Fill vertices to neighbor faces
1710 for ( int i = 0; i < faceSize; ++i )
1711 {
1712 int v1 = face[i % faceSize];
1713 int v2 = face[( i + 1 ) % faceSize];
1714 if ( verticesToNeighbor[v2].contains( v1 ) )
1715 {
1717 return ret;
1718 }
1719 else
1720 verticesToNeighbor[v2].insert( v1, faceIndex );
1721 }
1722 }
1723
1724 faceTopologies = QVector<FaceNeighbors>( faces.count() );
1725
1726 QSet<int> boundaryVertices;
1727
1728 for ( int faceIndex = 0; faceIndex < facesCount; ++faceIndex )
1729 {
1730 const QgsMeshFace &face = faces.at( faceIndex );
1731 int faceSize = face.size();
1732 FaceNeighbors &faceTopology = faceTopologies[faceIndex];
1733 faceTopology.resize( faceSize );
1734
1735 for ( int i = 0; i < faceSize; ++i )
1736 {
1737 int v1 = face.at( i );
1738 int v2 = face.at( ( i + 1 ) % faceSize );
1739
1740 if ( globalVertexToFace )
1741 {
1742 if ( ( *globalVertexToFace )[v1] == -1 )
1743 ( *globalVertexToFace )[v1] = faceIndex ;
1744 }
1745 else
1746 {
1747 if ( allowUniqueSharedVertex || !verticesToFace.contains( v1 ) )
1748 verticesToFace.insert( v1, faceIndex ) ;
1749 }
1750
1751 QMap<int, int> &edges = verticesToNeighbor[v1];
1752 if ( edges.contains( v2 ) )
1753 faceTopology[i] = edges.value( v2 );
1754 else
1755 {
1756 faceTopology[i] = -1;
1757
1758 if ( !allowUniqueSharedVertex )
1759 {
1760 if ( boundaryVertices.contains( v1 ) )
1761 {
1762 error = QgsMeshEditingError( Qgis::MeshEditingErrorType::UniqueSharedVertex, v1 ); // if a vertices is more than one time in the boundary, that means faces share only one vertices
1763 return ret;
1764 }
1765 }
1766 boundaryVertices.insert( v1 );
1767 }
1768 }
1769 }
1770
1771 ret.mFaces = faces;
1772 ret.mFacesNeighborhood = faceTopologies;
1773 ret.mBoundaries = boundaryVertices.values();
1774 ret.mVerticesToFace = verticesToFace;
1775 return ret;
1776}
1777
1778QVector<int> QgsTopologicalMesh::neighborsOfFace( int faceIndex ) const
1779{
1780 return mFacesNeighborhood.at( faceIndex );
1781}
1782
1783QList<int> QgsTopologicalMesh::facesAroundVertex( int vertexIndex ) const
1784{
1785 QgsMeshVertexCirculator circ = vertexCirculator( vertexIndex );
1786
1787 return circ.facesAround();
1788}
1789
1791{
1792 QSet<int> removedFaces( facesIndexes.begin(), facesIndexes.end() );
1793 QSet<int> concernedFaces = concernedFacesBy( facesIndexes );
1794
1795 for ( const int f : std::as_const( removedFaces ) )
1796 concernedFaces.remove( f );
1797
1798 QVector<QgsMeshFace> remainingFaces;
1799 remainingFaces.reserve( concernedFaces.count() );
1800 for ( const int f : std::as_const( concernedFaces ) )
1801 remainingFaces.append( mMesh->face( f ) );
1802
1803 QgsMeshEditingError error;
1804 createTopologicalFaces( remainingFaces, nullptr, error, false );
1805
1806 return error;
1807}
1808
1809QgsTopologicalMesh::Changes QgsTopologicalMesh::removeFaces( const QList<int> facesIndexesToRemove )
1810{
1811 Changes changes;
1812 changes.mFaceIndexesToRemove = facesIndexesToRemove;
1813 changes.mFacesToRemove.resize( facesIndexesToRemove.count() );
1814 changes.mFacesNeighborhoodToRemove.resize( facesIndexesToRemove.count() );
1815
1816 QSet<int> indexSet( facesIndexesToRemove.begin(), facesIndexesToRemove.end() );
1817 QSet<int> threatedVertex;
1818
1819 for ( int i = 0; i < facesIndexesToRemove.count(); ++i )
1820 {
1821 const int faceIndex = facesIndexesToRemove.at( i );
1822 const QgsMeshFace &face = mMesh->face( faceIndex );
1823 changes.mFacesToRemove[i] = face;
1824 const FaceNeighbors &neighborhood = mFacesNeighborhood.at( faceIndex );
1825 changes.mFacesNeighborhoodToRemove[i] = neighborhood;
1826 for ( int j = 0; j < face.count(); ++j )
1827 {
1828 //change the neighborhood for each neighbor face
1829 int neighborIndex = neighborhood.at( j );
1830 if ( neighborIndex != -1 && !indexSet.contains( neighborIndex ) )
1831 {
1832 int positionInNeighbor = mFacesNeighborhood.at( neighborIndex ).indexOf( faceIndex );
1833 changes.mNeighborhoodChanges.append( {neighborIndex, positionInNeighbor, faceIndex, -1} );
1834 }
1835
1836 //change vertexToFace
1837 int vertexIndex = face.at( j );
1838 if ( !threatedVertex.contains( vertexIndex ) && indexSet.contains( mVertexToFace.at( vertexIndex ) ) )
1839 {
1840 int oldValue = mVertexToFace.at( vertexIndex );
1841 //look for another face linked to this vertex
1842 int refValue = -1;
1843 if ( neighborIndex != -1 && !indexSet.contains( neighborIndex ) ) //if exist, simpler to take it
1844 refValue = neighborIndex;
1845 else
1846 {
1847 QList<int> aroundFaces = facesAroundVertex( vertexIndex );
1848 aroundFaces.removeOne( faceIndex );
1849 if ( !aroundFaces.isEmpty() )
1850 {
1851 while ( !aroundFaces.isEmpty() && refValue == -1 )
1852 {
1853 if ( !indexSet.contains( aroundFaces.first() ) )
1854 refValue = aroundFaces.first();
1855 else
1856 aroundFaces.removeFirst();
1857 }
1858 }
1859 }
1860 changes.mVerticesToFaceChanges.append( {vertexIndex, oldValue, refValue} );
1861 threatedVertex.insert( vertexIndex );
1862 }
1863 }
1864 }
1865
1866 applyChanges( changes );
1867
1868 return changes;
1869}
1870
1871bool QgsTopologicalMesh::eitherSideFacesAndVertices( int vertexIndex1,
1872 int vertexIndex2,
1873 int &face1,
1874 int &face2,
1875 int &neighborVertex1InFace1,
1876 int &neighborVertex1InFace2,
1877 int &neighborVertex2inFace1,
1878 int &neighborVertex2inFace2 ) const
1879{
1880 QgsMeshVertexCirculator circulator1 = vertexCirculator( vertexIndex1 );
1881 QgsMeshVertexCirculator circulator2 = vertexCirculator( vertexIndex2 );
1882
1883 circulator1.goBoundaryClockwise();
1884 int firstFace1 = circulator1.currentFaceIndex();
1885 circulator2.goBoundaryClockwise();
1886 int firstFace2 = circulator2.currentFaceIndex();
1887
1888 if ( circulator1.oppositeVertexCounterClockwise() != vertexIndex2 )
1889 while ( circulator1.turnCounterClockwise() != -1 &&
1890 circulator1.currentFaceIndex() != firstFace1 &&
1891 circulator1.oppositeVertexCounterClockwise() != vertexIndex2 ) {}
1892
1893 if ( circulator2.oppositeVertexCounterClockwise() != vertexIndex1 )
1894 while ( circulator2.turnCounterClockwise() != -1 &&
1895 circulator2.currentFaceIndex() != firstFace2 &&
1896 circulator2.oppositeVertexCounterClockwise() != vertexIndex1 ) {}
1897
1898 if ( circulator1.oppositeVertexCounterClockwise() != vertexIndex2
1899 || circulator2.oppositeVertexCounterClockwise() != vertexIndex1 )
1900 return false;
1901
1902 face1 = circulator1.currentFaceIndex();
1903 face2 = circulator2.currentFaceIndex();
1904
1905 neighborVertex1InFace1 = circulator1.oppositeVertexClockwise();
1906 circulator1.turnCounterClockwise();
1907 neighborVertex1InFace2 = circulator1.oppositeVertexCounterClockwise();
1908
1909 neighborVertex2inFace2 = circulator2.oppositeVertexClockwise();
1910 circulator2.turnCounterClockwise();
1911 neighborVertex2inFace1 = circulator2.oppositeVertexCounterClockwise();
1912
1913 return true;
1914}
1915
1916bool QgsTopologicalMesh::edgeCanBeFlipped( int vertexIndex1, int vertexIndex2 ) const
1917{
1918 int faceIndex1;
1919 int faceIndex2;
1920 int oppositeVertexFace1;
1921 int oppositeVertexFace2;
1922 int supposedOppositeVertexFace1;
1923 int supposedoppositeVertexFace2;
1924
1925 bool result = eitherSideFacesAndVertices(
1926 vertexIndex1,
1927 vertexIndex2,
1928 faceIndex1,
1929 faceIndex2,
1930 oppositeVertexFace1,
1931 supposedoppositeVertexFace2,
1932 supposedOppositeVertexFace1,
1933 oppositeVertexFace2 );
1934
1935 if ( !result ||
1936 faceIndex1 < 0 ||
1937 faceIndex2 < 0 ||
1938 oppositeVertexFace1 < 0 ||
1939 oppositeVertexFace2 < 0 ||
1940 supposedOppositeVertexFace1 != oppositeVertexFace1 ||
1941 supposedoppositeVertexFace2 != oppositeVertexFace2 )
1942 return false;
1943
1944 const QgsMeshFace &face1 = mMesh->face( faceIndex1 );
1945 const QgsMeshFace &face2 = mMesh->face( faceIndex2 );
1946
1947
1948 if ( face1.count() != 3 || face2.count() != 3 )
1949 return false;
1950
1951 double crossProduct1 = crossProduct( vertexIndex1, oppositeVertexFace1, oppositeVertexFace2, *mMesh );
1952 double crossProduct2 = crossProduct( vertexIndex2, oppositeVertexFace1, oppositeVertexFace2, *mMesh );
1953
1954 return crossProduct1 * crossProduct2 < 0;
1955}
1956
1958{
1959 int faceIndex1;
1960 int faceIndex2;
1961 int oppositeVertexFace1;
1962 int oppositeVertexFace2;
1963 int supposedOppositeVertexFace1;
1964 int supposedoppositeVertexFace2;
1965
1966 bool result = eitherSideFacesAndVertices(
1967 vertexIndex1,
1968 vertexIndex2,
1969 faceIndex1,
1970 faceIndex2,
1971 oppositeVertexFace1,
1972 supposedoppositeVertexFace2,
1973 supposedOppositeVertexFace1,
1974 oppositeVertexFace2 );
1975
1976 if ( !result ||
1977 faceIndex1 < 0 ||
1978 faceIndex2 < 0 ||
1979 oppositeVertexFace1 < 0 ||
1980 oppositeVertexFace2 < 0 ||
1981 supposedOppositeVertexFace1 != oppositeVertexFace1 ||
1982 supposedoppositeVertexFace2 != oppositeVertexFace2 )
1983 return Changes();
1984
1985
1986 Changes changes;
1987
1988 const QgsMeshFace &face1 = mMesh->face( faceIndex1 );
1989 const QgsMeshFace &face2 = mMesh->face( faceIndex2 );
1990
1991 Q_ASSERT( face1.count() == 3 );
1992 Q_ASSERT( face2.count() == 3 );
1993
1994 int pos1 = vertexPositionInFace( vertexIndex1, face1 );
1995 int pos2 = vertexPositionInFace( vertexIndex2, face2 );
1996
1997 int neighborFace1 = mFacesNeighborhood.at( faceIndex1 ).at( pos1 );
1998 int posInNeighbor1 = vertexPositionInFace( *mMesh, oppositeVertexFace1, neighborFace1 );
1999 int neighborFace2 = mFacesNeighborhood.at( faceIndex1 ).at( ( pos1 + 1 ) % 3 );
2000 int posInNeighbor2 = vertexPositionInFace( *mMesh, vertexIndex2, neighborFace2 );
2001 int neighborFace3 = mFacesNeighborhood.at( faceIndex2 ).at( pos2 );
2002 int posInNeighbor3 = vertexPositionInFace( *mMesh, oppositeVertexFace2, neighborFace3 );
2003 int neighborFace4 = mFacesNeighborhood.at( faceIndex2 ).at( ( pos2 + 1 ) % 3 );
2004 int posInNeighbor4 = vertexPositionInFace( *mMesh, vertexIndex1, neighborFace4 );
2005
2006 changes.mFaceIndexesToRemove.append( faceIndex1 );
2007 changes.mFaceIndexesToRemove.append( faceIndex2 );
2008 changes.mFacesToRemove.append( face1 );
2009 changes.mFacesToRemove.append( face2 );
2010 changes.mFacesNeighborhoodToRemove.append( mFacesNeighborhood.at( faceIndex1 ) );
2011 changes.mFacesNeighborhoodToRemove.append( mFacesNeighborhood.at( faceIndex2 ) );
2012 int startIndex = mMesh->faceCount();
2013 changes.mAddedFacesFirstIndex = startIndex;
2014 changes.mFacesToAdd.append( {oppositeVertexFace1, oppositeVertexFace2, vertexIndex1} );
2015 changes.mFacesToAdd.append( {oppositeVertexFace2, oppositeVertexFace1, vertexIndex2} );
2016 changes.mFacesNeighborhoodToAdd.append( {startIndex + 1,
2017 mFacesNeighborhood.at( faceIndex2 ).at( ( pos2 + 1 ) % 3 ),
2018 mFacesNeighborhood.at( faceIndex1 ).at( pos1 )} );
2019 changes.mFacesNeighborhoodToAdd.append( {startIndex,
2020 mFacesNeighborhood.at( faceIndex1 ).at( ( pos1 + 1 ) % 3 ),
2021 mFacesNeighborhood.at( faceIndex2 ).at( pos2 )} );
2022
2023 if ( neighborFace1 >= 0 )
2024 changes.mNeighborhoodChanges.append( {neighborFace1, posInNeighbor1, faceIndex1, startIndex} );
2025 if ( neighborFace2 >= 0 )
2026 changes.mNeighborhoodChanges.append( {neighborFace2, posInNeighbor2, faceIndex1, startIndex + 1} );
2027 if ( neighborFace3 >= 0 )
2028 changes.mNeighborhoodChanges.append( {neighborFace3, posInNeighbor3, faceIndex2, startIndex + 1} );
2029 if ( neighborFace4 >= 0 )
2030 changes.mNeighborhoodChanges.append( {neighborFace4, posInNeighbor4, faceIndex2, startIndex} );
2031
2032
2033 if ( mVertexToFace.at( vertexIndex1 ) == faceIndex1 || mVertexToFace.at( vertexIndex1 ) == faceIndex2 )
2034 changes.mVerticesToFaceChanges.append( {vertexIndex1, mVertexToFace.at( vertexIndex1 ), startIndex} );
2035 if ( mVertexToFace.at( vertexIndex2 ) == faceIndex1 || mVertexToFace.at( vertexIndex2 ) == faceIndex2 )
2036 changes.mVerticesToFaceChanges.append( {vertexIndex2, mVertexToFace.at( vertexIndex2 ), startIndex + 1} );
2037
2038 if ( mVertexToFace.at( oppositeVertexFace1 ) == faceIndex1 )
2039 changes.mVerticesToFaceChanges.append( {oppositeVertexFace1, faceIndex1, startIndex} );
2040
2041 if ( mVertexToFace.at( oppositeVertexFace2 ) == faceIndex2 )
2042 changes.mVerticesToFaceChanges.append( {oppositeVertexFace2, faceIndex2, startIndex + 1} );
2043
2044 applyChanges( changes );
2045
2046 return changes;
2047}
2048
2049bool QgsTopologicalMesh::canBeMerged( int vertexIndex1, int vertexIndex2 ) const
2050{
2051 int faceIndex1;
2052 int faceIndex2;
2053 int neighborVertex1InFace1;
2054 int neighborVertex1InFace2;
2055 int neighborVertex2inFace1;
2056 int neighborVertex2inFace2;
2057
2058 bool result = eitherSideFacesAndVertices(
2059 vertexIndex1,
2060 vertexIndex2,
2061 faceIndex1,
2062 faceIndex2,
2063 neighborVertex1InFace1,
2064 neighborVertex1InFace2,
2065 neighborVertex2inFace1,
2066 neighborVertex2inFace2 );
2067
2068 if ( !result ||
2069 faceIndex1 < 0 ||
2070 faceIndex2 < 0 )
2071 return false;
2072
2073 const QgsMeshFace &face1 = mMesh->face( faceIndex1 );
2074 const QgsMeshFace &face2 = mMesh->face( faceIndex2 );
2075
2076 if ( face1.count() + face2.count() - 2 > mMaximumVerticesPerFace )
2077 return false;
2078
2079 QgsMeshVertex v1 = mMesh->vertices.at( vertexIndex1 );
2080 QgsMeshVertex v2 = mMesh->vertices.at( vertexIndex2 );
2081 QgsMeshVertex nv11 = mMesh->vertices.at( neighborVertex1InFace1 );
2082 QgsMeshVertex nv12 = mMesh->vertices.at( neighborVertex1InFace2 );
2083 QgsMeshVertex nv21 = mMesh->vertices.at( neighborVertex2inFace1 );
2084 QgsMeshVertex nv22 = mMesh->vertices.at( neighborVertex2inFace2 );
2085
2086 double crossProduct1 = crossProduct( vertexIndex1, neighborVertex1InFace1, neighborVertex1InFace2, *mMesh );
2087 double crossProduct2 = crossProduct( vertexIndex2, neighborVertex2inFace1, neighborVertex2inFace2, *mMesh );
2088
2089 return crossProduct1 * crossProduct2 < 0;
2090}
2091
2092QgsTopologicalMesh::Changes QgsTopologicalMesh::merge( int vertexIndex1, int vertexIndex2 )
2093{
2094 int faceIndex1;
2095 int faceIndex2;
2096 int neighborVertex1InFace1;
2097 int neighborVertex1InFace2;
2098 int neighborVertex2inFace1;
2099 int neighborVertex2inFace2;
2100
2101 bool result = eitherSideFacesAndVertices(
2102 vertexIndex1,
2103 vertexIndex2,
2104 faceIndex1,
2105 faceIndex2,
2106 neighborVertex1InFace1,
2107 neighborVertex1InFace2,
2108 neighborVertex2inFace1,
2109 neighborVertex2inFace2 );
2110
2111 if ( !result ||
2112 faceIndex1 < 0 ||
2113 faceIndex2 < 0 )
2114 return Changes();
2115
2116 Changes changes;
2117
2118 const QgsMeshFace &face1 = mMesh->face( faceIndex1 );
2119 const QgsMeshFace &face2 = mMesh->face( faceIndex2 );
2120 int faceSize1 = face1.count();
2121 int faceSize2 = face2.count();
2122
2123 int pos1 = vertexPositionInFace( vertexIndex1, face1 );
2124 int pos2 = vertexPositionInFace( vertexIndex2, face2 );
2125
2126 changes.mFaceIndexesToRemove.append( faceIndex1 );
2127 changes.mFaceIndexesToRemove.append( faceIndex2 );
2128 changes.mFacesToRemove.append( face1 );
2129 changes.mFacesToRemove.append( face2 );
2130 changes.mFacesNeighborhoodToRemove.append( mFacesNeighborhood.at( faceIndex1 ) );
2131 changes.mFacesNeighborhoodToRemove.append( mFacesNeighborhood.at( faceIndex2 ) );
2132 int startIndex = mMesh->faceCount();
2133 changes.mAddedFacesFirstIndex = startIndex;
2134
2135 QgsMeshFace newface;
2136 FaceNeighbors newNeighborhood;
2137 for ( int i = 0; i < faceSize1 - 1; ++i )
2138 {
2139 int currentPos = ( pos1 + i ) % faceSize1;
2140 newface.append( face1.at( currentPos ) ); //add vertex of face1
2141
2142 int currentNeighbor = mFacesNeighborhood.at( faceIndex1 ).at( currentPos );
2143 newNeighborhood.append( currentNeighbor );
2144
2145 if ( currentNeighbor != -1 )
2146 {
2147 int currentPosInNeighbor = vertexPositionInFace( *mMesh, face1.at( ( currentPos + 1 ) % faceSize1 ), currentNeighbor );
2148 changes.mNeighborhoodChanges.append( {currentNeighbor, currentPosInNeighbor, faceIndex1, startIndex} );
2149 }
2150 }
2151 for ( int i = 0; i < faceSize2 - 1; ++i )
2152 {
2153 int currentPos = ( pos2 + i ) % faceSize2;
2154 newface.append( face2.at( currentPos ) ); //add vertex of face2
2155
2156 int currentNeighbor = mFacesNeighborhood.at( faceIndex2 ).at( currentPos );
2157 newNeighborhood.append( currentNeighbor );
2158
2159 if ( currentNeighbor != -1 )
2160 {
2161 int currentPosInNeighbor = vertexPositionInFace( *mMesh, face2.at( ( currentPos + 1 ) % faceSize2 ), currentNeighbor );
2162 changes.mNeighborhoodChanges.append( {currentNeighbor, currentPosInNeighbor, faceIndex2, startIndex} );
2163 }
2164 }
2165
2166 for ( int i = 0; i < faceSize1; ++i )
2167 if ( mVertexToFace.at( face1.at( i ) ) == faceIndex1 )
2168 changes.mVerticesToFaceChanges.append( {face1.at( i ), faceIndex1, startIndex} );
2169
2170 for ( int i = 0; i < faceSize2; ++i )
2171 if ( mVertexToFace.at( face2.at( i ) ) == faceIndex2 )
2172 changes.mVerticesToFaceChanges.append( {face2.at( i ), faceIndex2, startIndex} );
2173
2174 changes.mFacesToAdd.append( newface );
2175 changes.mFacesNeighborhoodToAdd.append( newNeighborhood );
2176
2177 applyChanges( changes );
2178
2179 return changes;
2180}
2181
2182bool QgsTopologicalMesh::canBeSplit( int faceIndex ) const
2183{
2184 const QgsMeshFace face = mMesh->face( faceIndex );
2185
2186 return face.count() == 4;
2187}
2188
2190{
2191 //search for the spliited angle (greater angle)
2192 const QgsMeshFace &face = mMesh->face( faceIndex );
2193 int faceSize = face.count();
2194
2195 Q_ASSERT( faceSize == 4 );
2196
2197 double maxAngle = 0;
2198 int splitVertexPos = -1;
2199 for ( int i = 0; i < faceSize; ++i )
2200 {
2201 QgsVector vect1( mMesh->vertex( face.at( i ) ) - mMesh->vertex( face.at( ( i + 1 ) % faceSize ) ) );
2202 QgsVector vect2( mMesh->vertex( face.at( ( i + 2 ) % faceSize ) ) - mMesh->vertex( face.at( ( i + 1 ) % faceSize ) ) );
2203
2204 double angle = std::abs( vect1.angle( vect2 ) );
2205 angle = std::min( angle, 2.0 * M_PI - angle );
2206 if ( angle > maxAngle )
2207 {
2208 maxAngle = angle;
2209 splitVertexPos = ( i + 1 ) % faceSize;
2210 }
2211 }
2212
2213 Changes changes;
2214
2215 const QgsMeshFace newFace1 = {face.at( splitVertexPos ),
2216 face.at( ( splitVertexPos + 1 ) % faceSize ),
2217 face.at( ( splitVertexPos + 2 ) % faceSize )
2218 };
2219
2220 const QgsMeshFace newFace2 = {face.at( splitVertexPos ),
2221 face.at( ( splitVertexPos + 2 ) % faceSize ),
2222 face.at( ( splitVertexPos + 3 ) % faceSize )
2223 };
2224
2225 QVector<int> neighborIndex( faceSize );
2226 QVector<int> posInNeighbor( faceSize );
2227
2228 for ( int i = 0; i < faceSize; ++i )
2229 {
2230 neighborIndex[i] = mFacesNeighborhood.at( faceIndex ).at( ( splitVertexPos + i ) % faceSize );
2231 posInNeighbor[i] = vertexPositionInFace( *mMesh, face.at( ( splitVertexPos + i + 1 ) % faceSize ), neighborIndex[i] );
2232 }
2233
2234 changes.mFaceIndexesToRemove.append( faceIndex );
2235 changes.mFacesToRemove.append( face );
2236 changes.mFacesNeighborhoodToRemove.append( mFacesNeighborhood.at( faceIndex ) );
2237 int startIndex = mMesh->faceCount();
2238 changes.mAddedFacesFirstIndex = startIndex;
2239 changes.mFacesToAdd.append( newFace1 );
2240 changes.mFacesToAdd.append( newFace2 );
2241
2242 changes.mFacesNeighborhoodToAdd.append( {mFacesNeighborhood.at( faceIndex ).at( splitVertexPos ),
2243 mFacesNeighborhood.at( faceIndex ).at( ( splitVertexPos + 1 ) % faceSize ),
2244 startIndex + 1} );
2245 changes.mFacesNeighborhoodToAdd.append( {startIndex,
2246 mFacesNeighborhood.at( faceIndex ).at( ( splitVertexPos + 2 ) % faceSize ),
2247 mFacesNeighborhood.at( faceIndex ).at( ( splitVertexPos + 3 ) % faceSize )} );
2248
2249 for ( int i = 0; i < faceSize; ++i )
2250 {
2251 if ( neighborIndex[i] >= 0 )
2252 changes.mNeighborhoodChanges.append( {neighborIndex[i], posInNeighbor[i], faceIndex, startIndex + int( i / 2 )} );
2253
2254 int vertexIndex = face.at( ( splitVertexPos + i ) % faceSize );
2255 if ( mVertexToFace.at( vertexIndex ) == faceIndex )
2256 changes.mVerticesToFaceChanges.append( {vertexIndex, faceIndex, startIndex + int( i / 2 )} );
2257 }
2258
2259 applyChanges( changes );
2260
2261 return changes;
2262}
2263
2264
2266{
2267 Changes changes;
2268 changes.mVerticesToAdd.append( vertex );
2269 changes.mVertexToFaceToAdd.append( -1 );
2270
2271 mMesh->vertices.append( vertex );
2272 mVertexToFace.append( -1 );
2273 changes.mAddedFacesFirstIndex = mMesh->faceCount();
2274
2275 const QgsMeshFace includingFace = mMesh->face( includingFaceIndex );
2276 const FaceNeighbors includingFaceNeighborhood = mFacesNeighborhood.at( includingFaceIndex );
2277 int includingFaceSize = includingFace.count();
2278
2279 for ( int i = 0; i < includingFaceSize; ++i )
2280 {
2281 // add a new face
2282 QgsMeshFace face( 3 );
2283 face[0] = mMesh->vertexCount() - 1;
2284 face[1] = includingFace.at( i );
2285 face[2] = includingFace.at( ( i + 1 ) % includingFaceSize );
2286 mMesh->faces.append( face );
2287 changes.mFacesToAdd.append( face );
2288
2289 int currentVertexIndex = includingFace.at( i );
2290 if ( mVertexToFace.at( currentVertexIndex ) == includingFaceIndex )
2291 {
2292 int newFaceIndex = mMesh->faceCount() - 1;
2293 mVertexToFace[currentVertexIndex] = newFaceIndex;
2294 changes.mVerticesToFaceChanges.append( {currentVertexIndex, includingFaceIndex, newFaceIndex} );
2295 }
2296
2297 int includingFaceNeighbor = includingFaceNeighborhood.at( i );
2298 FaceNeighbors neighbors(
2299 {
2300 changes.mAddedFacesFirstIndex + ( i + includingFaceSize - 1 ) % includingFaceSize,
2301 includingFaceNeighbor,
2302 changes.mAddedFacesFirstIndex + ( i + includingFaceSize + 1 ) % includingFaceSize
2303 } );
2304 mFacesNeighborhood.append( neighbors );
2305 changes.mFacesNeighborhoodToAdd.append( neighbors );
2306
2307 if ( includingFaceNeighbor != -1 )
2308 {
2309 int indexInNeighbor = vertexPositionInFace( *mMesh, includingFace.at( ( i + 1 ) % includingFaceSize ), includingFaceNeighbor );
2310 int oldValue = mFacesNeighborhood[includingFaceNeighbor][indexInNeighbor];
2311 mFacesNeighborhood[includingFaceNeighbor][indexInNeighbor] = changes.mAddedFacesFirstIndex + i;
2312 changes.mNeighborhoodChanges.append( {includingFaceNeighbor, indexInNeighbor, oldValue, changes.mAddedFacesFirstIndex + i} );
2313 }
2314 }
2315
2316 changes.mFacesToRemove.append( includingFace );
2317 changes.mFaceIndexesToRemove.append( includingFaceIndex );
2318 changes.mFacesNeighborhoodToRemove.append( includingFaceNeighborhood );
2319
2320 mFacesNeighborhood[includingFaceIndex] = FaceNeighbors();
2321 mMesh->faces[includingFaceIndex] = QgsMeshFace();
2322 mVertexToFace[mVertexToFace.count() - 1] = mMesh->faceCount() - 1;
2323 changes.mVertexToFaceToAdd[changes.mVertexToFaceToAdd.count() - 1] = mMesh->faceCount() - 1 ;
2324
2325 return changes;
2326}
2327
2329{
2330 const QgsMeshFace face1 = mMesh->face( faceIndex );
2331
2332 Changes changes;
2333 changes.mVerticesToAdd.append( vertexToInsert );
2334 changes.mAddedFacesFirstIndex = mMesh->faceCount();
2335
2336 // triangulate the first face
2337 int newVertexPositionInFace1 = position + 1;
2338
2339 auto triangulate = [this, &changes]( int removedFaceIndex, const QgsMeshVertex & newVertex, int newVertexPosition, QVector<int> &edgeFacesIndexes )->bool
2340 {
2341 const QgsMeshFace &initialFace = mMesh->face( removedFaceIndex );
2342 changes.mFacesToRemove.append( initialFace );
2343 changes.mFaceIndexesToRemove.append( removedFaceIndex );
2344 changes.mFacesNeighborhoodToRemove.append( mFacesNeighborhood.at( removedFaceIndex ) );
2345 const int addedVertexIndex = mMesh->vertexCount();
2346
2347 int faceStartGlobalIndex = mMesh->faceCount() + changes.mFacesToAdd.count();
2348 int localStartIndex = changes.mFacesToAdd.count();
2349
2350 QVector<int> newBoundary = initialFace;
2351 newBoundary.insert( newVertexPosition, addedVertexIndex );
2352
2353 try
2354 {
2355 QHash<p2t::Point *, int> mapPoly2TriPointToVertex;
2356 std::vector<p2t::Point *> faceToFill( newBoundary.count() );
2357 for ( int i = 0; i < newBoundary.count(); ++i )
2358 {
2359 QgsMeshVertex vert;
2360
2361 if ( newBoundary.at( i ) == addedVertexIndex )
2362 vert = newVertex;
2363 else
2364 vert = mMesh->vertex( newBoundary.at( i ) );
2365
2366 faceToFill[i] = new p2t::Point( vert.x(), vert.y() );
2367 mapPoly2TriPointToVertex.insert( faceToFill[i], newBoundary.at( i ) );
2368 }
2369
2370 std::unique_ptr<p2t::CDT> cdt( new p2t::CDT( faceToFill ) );
2371 cdt->Triangulate();
2372 std::vector<p2t::Triangle *> triangles = cdt->GetTriangles();
2373 QVector<QgsMeshFace> newFaces( triangles.size() );
2374 for ( size_t i = 0; i < triangles.size(); ++i )
2375 {
2376 QgsMeshFace &face = newFaces[i];
2377 face.resize( 3 );
2378 for ( int j = 0; j < 3; j++ )
2379 {
2380 int vertInd = mapPoly2TriPointToVertex.value( triangles.at( i )->GetPoint( j ), -1 );
2381 if ( vertInd == -1 )
2382 throw std::exception();
2383 face[j] = vertInd;
2384 }
2385 }
2386
2387 QgsMeshEditingError error;
2388 QgsTopologicalMesh::TopologicalFaces topologicalFaces = createNewTopologicalFaces( newFaces, false, error );
2390 throw std::exception();
2391
2392 changes.mFacesToAdd.append( topologicalFaces.meshFaces() );
2393 changes.mFacesNeighborhoodToAdd.append( topologicalFaces.mFacesNeighborhood );
2394
2395 // vertices to face changes
2396 const QList<int> &verticesToFaceToChange = topologicalFaces.mVerticesToFace.keys();
2397 for ( const int vtc : verticesToFaceToChange )
2398 if ( vtc != addedVertexIndex && mVertexToFace.at( vtc ) == removedFaceIndex )
2399 changes.mVerticesToFaceChanges.append(
2400 {
2401 vtc,
2402 removedFaceIndex,
2403 topologicalFaces.vertexToFace( vtc ) + faceStartGlobalIndex
2404 } );
2405
2406 // reindex neighborhood for new faces
2407 for ( int i = 0; i < topologicalFaces.mFaces.count(); ++i )
2408 {
2409 FaceNeighbors &faceNeighbors = changes.mFacesNeighborhoodToAdd[i + localStartIndex];
2410 for ( int n = 0; n < faceNeighbors.count(); ++n )
2411 {
2412 if ( faceNeighbors.at( n ) != -1 )
2413 faceNeighbors[n] += faceStartGlobalIndex; //reindex internal neighborhood
2414 }
2415 }
2416
2417 edgeFacesIndexes.resize( 2 );
2418 // link neighborhood for boundaries of each side
2419 for ( int i = 0 ; i < newBoundary.count(); ++i )
2420 {
2421 int vertexIndex = newBoundary.at( i );
2422 QgsMeshVertexCirculator circulator = QgsMeshVertexCirculator( topologicalFaces, vertexIndex );
2423 circulator.goBoundaryClockwise();
2424 int newFaceBoundaryLocalIndex = localStartIndex + circulator.currentFaceIndex();
2425
2426 int newFaceBoundaryIndexInMesh = faceStartGlobalIndex;
2427
2428 int meshFaceBoundaryIndex;
2429 if ( i == newVertexPosition )
2430 {
2431 meshFaceBoundaryIndex = -1; //face that are on the opposite side of the edge, filled later
2432 edgeFacesIndexes[0] = newFaceBoundaryLocalIndex;
2433 }
2434 else if ( i == ( newVertexPosition + newBoundary.count() - 1 ) % newBoundary.count() )
2435 {
2436 meshFaceBoundaryIndex = -1; //face that are on the opposite side of the edge, filled later
2437 edgeFacesIndexes[1] = newFaceBoundaryLocalIndex;
2438 }
2439 else
2440 meshFaceBoundaryIndex = mFacesNeighborhood.at( removedFaceIndex ).at( vertexPositionInFace( vertexIndex, initialFace ) );
2441
2442 const QgsMeshFace &newFace = circulator.currentFace();
2443 int positionInNewFaces = vertexPositionInFace( vertexIndex, newFace );
2444
2445 if ( meshFaceBoundaryIndex != -1 )
2446 {
2447 const QgsMeshFace meshFace = mMesh->face( meshFaceBoundaryIndex );
2448 int positionInMeshFaceBoundary = vertexPositionInFace( *mMesh, vertexIndex, meshFaceBoundaryIndex );
2449 positionInMeshFaceBoundary = ( positionInMeshFaceBoundary - 1 + meshFace.count() ) % meshFace.count(); //take the position just before
2450
2451 changes.mNeighborhoodChanges.append( {meshFaceBoundaryIndex,
2452 positionInMeshFaceBoundary,
2453 removedFaceIndex,
2454 newFaceBoundaryIndexInMesh +
2455 circulator.currentFaceIndex()} );
2456 }
2457
2458 changes.mFacesNeighborhoodToAdd[newFaceBoundaryLocalIndex][positionInNewFaces] = meshFaceBoundaryIndex;
2459 }
2460
2461 qDeleteAll( faceToFill );
2462 }
2463 catch ( ... )
2464 {
2465 return false;
2466 }
2467
2468 return true;
2469 };
2470
2471 QVector<int> edgeFacesIndexes;
2472 if ( !triangulate( faceIndex, vertexToInsert, newVertexPositionInFace1, edgeFacesIndexes ) )
2473 return Changes();
2474
2475 changes.mVertexToFaceToAdd.append( edgeFacesIndexes.at( 0 ) + changes.mAddedFacesFirstIndex );
2476
2477 int addedVertexIndex = mMesh->vertexCount();
2478
2479 //if exist, triangulate the second face if exists
2480 int face2Index = mFacesNeighborhood.at( faceIndex ).at( position );
2481 if ( face2Index != -1 )
2482 {
2483 const QgsMeshFace &face2 = mMesh->face( face2Index );
2484 int vertexPositionInFace2 = vertexPositionInFace( face1.at( position ), face2 );
2485 QVector<int> edgeFacesIndexesFace2;
2486 if ( !triangulate( face2Index, vertexToInsert, vertexPositionInFace2, edgeFacesIndexesFace2 ) )
2487 return Changes();
2488
2489 //link neighborhood with other side
2490 const QgsMeshFace &firstFaceSide1 = changes.mFacesToAdd.at( edgeFacesIndexes.at( 0 ) );
2491 int pos1InFaceSide1 = vertexPositionInFace( addedVertexIndex, firstFaceSide1 );
2492
2493 const QgsMeshFace &secondFaceSide1 = changes.mFacesToAdd.at( edgeFacesIndexes.at( 1 ) );
2494 int pos2InFaceSide1 = vertexPositionInFace( addedVertexIndex, secondFaceSide1 );
2495 pos2InFaceSide1 = ( pos2InFaceSide1 + secondFaceSide1.size() - 1 ) % secondFaceSide1.size();
2496
2497 const QgsMeshFace &firstFaceSide2 = changes.mFacesToAdd.at( edgeFacesIndexesFace2.at( 0 ) );
2498 int pos1InFaceSide2 = vertexPositionInFace( addedVertexIndex, firstFaceSide2 );
2499
2500 const QgsMeshFace &secondFaceSide2 = changes.mFacesToAdd.at( edgeFacesIndexesFace2.at( 1 ) );
2501 int pos2InFaceSide2 = vertexPositionInFace( addedVertexIndex, secondFaceSide2 );
2502 pos2InFaceSide2 = ( pos2InFaceSide2 + secondFaceSide1.size() - 1 ) % secondFaceSide1.size();
2503
2504 changes.mFacesNeighborhoodToAdd[edgeFacesIndexes.at( 0 )][pos1InFaceSide1] = edgeFacesIndexesFace2.at( 1 ) + changes.mAddedFacesFirstIndex;
2505 changes.mFacesNeighborhoodToAdd[edgeFacesIndexes.at( 1 )][pos2InFaceSide1] = edgeFacesIndexesFace2.at( 0 ) + changes.mAddedFacesFirstIndex;
2506 changes.mFacesNeighborhoodToAdd[edgeFacesIndexesFace2.at( 0 )][pos1InFaceSide2] = edgeFacesIndexes.at( 1 ) + changes.mAddedFacesFirstIndex;
2507 changes.mFacesNeighborhoodToAdd[edgeFacesIndexesFace2.at( 1 )][pos2InFaceSide2] = edgeFacesIndexes.at( 0 ) + changes.mAddedFacesFirstIndex;
2508 }
2509
2510 applyChanges( changes );
2511 return changes;
2512}
2513
2514QgsTopologicalMesh::Changes QgsTopologicalMesh::changeZValue( const QList<int> &verticesIndexes, const QList<double> &newValues )
2515{
2516 Q_ASSERT( verticesIndexes.count() == newValues.count() );
2517 Changes changes;
2518 changes.mChangeCoordinateVerticesIndexes.reserve( verticesIndexes.count() );
2519 changes.mNewZValues.reserve( verticesIndexes.count() );
2520 changes.mOldZValues.reserve( verticesIndexes.count() );
2521 for ( int i = 0; i < verticesIndexes.count(); ++i )
2522 {
2523 changes.mChangeCoordinateVerticesIndexes.append( verticesIndexes.at( i ) );
2524 changes.mOldZValues.append( mMesh->vertices.at( verticesIndexes.at( i ) ).z() );
2525 changes.mNewZValues.append( newValues.at( i ) );
2526 }
2527
2528 applyChanges( changes );
2529
2530 return changes;
2531}
2532
2533QgsTopologicalMesh::Changes QgsTopologicalMesh::changeXYValue( const QList<int> &verticesIndexes, const QList<QgsPointXY> &newValues )
2534{
2535 Q_ASSERT( verticesIndexes.count() == newValues.count() );
2536 Changes changes;
2537 changes.mChangeCoordinateVerticesIndexes.reserve( verticesIndexes.count() );
2538 changes.mNewXYValues.reserve( verticesIndexes.count() );
2539 changes.mOldXYValues.reserve( verticesIndexes.count() );
2540 QSet<int> concernedFace;
2541 for ( int i = 0; i < verticesIndexes.count(); ++i )
2542 {
2543 changes.mChangeCoordinateVerticesIndexes.append( verticesIndexes.at( i ) );
2544 changes.mOldXYValues.append( mMesh->vertices.at( verticesIndexes.at( i ) ) );
2545 changes.mNewXYValues.append( newValues.at( i ) );
2546 const QList< int > faces = facesAroundVertex( verticesIndexes.at( i ) );
2547 concernedFace.unite( QSet< int>( faces.begin(), faces.end() ) );
2548 }
2549
2550 changes.mNativeFacesIndexesGeometryChanged = concernedFace.values();
2551
2552 applyChanges( changes );
2553
2554 return changes;
2555}
@ 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.
Definition: qgsmesheditor.h:43
Qgis::MeshEditingErrorType errorType
Definition: qgsmesheditor.h:52
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.
Definition: qgspointxy.h:59
double y
Definition: qgspointxy.h:63
Q_GADGET double x
Definition: qgspointxy.h:62
Point geometry type, with support for z-dimension and m-values.
Definition: qgspoint.h:49
bool isEmpty() const override SIP_HOLDGIL
Returns true if the geometry is empty.
Definition: qgspoint.cpp:767
Q_GADGET double x
Definition: qgspoint.h:52
double y
Definition: qgspoint.h:53
Class that contains topological differences between two states of a topological mesh,...
QList< int > mChangeCoordinateVerticesIndexes
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 > 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.
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.
QList< QgsPointXY > newVerticesXYValues() const
Returns the new (X,Y) values of vertices that have changed their coordinates.
QVector< QgsMeshFace > mFacesToRemove
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.
Definition: qgsvector.h:30
double angle() const SIP_HOLDGIL
Returns the angle of the vector in radians.
Definition: qgsvector.h:172
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)
Definition: MathUtils.cpp:786
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.