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