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