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