+ return q1.crit2() < q2.crit2();
+ }
+ };
+
+ //================================================================================
+ /*!
+ * \brief Unite EDGEs to get a required number of sides
+ * \param [in] theNbCorners - the required number of sides
+ * \param [in] theConsiderMesh - to considered only meshed VERTEXes
+ * \param [in] theFaceSide - the FACE EDGEs
+ * \param [out] theVertices - the found corner vertices
+ */
+ //================================================================================
+
+ void uniteEdges( const int theNbCorners,
+ const bool theConsiderMesh,
+ const StdMeshers_FaceSide& theFaceSide,
+ const TopoDS_Shape& theBaseVertex,
+ std::vector<TopoDS_Vertex>& theVertices,
+ bool& theHaveConcaveVertices)
+ {
+ // form a circular list of EDGEs
+ std::vector< Edge > edges( theFaceSide.NbEdges() );
+ boost::intrusive::circular_list_algorithms< Edge > circularList;
+ circularList.init_header( &edges[0] );
+ edges[0].myEdge = theFaceSide.Edge( 0 );
+ edges[0].myIndex = 0;
+ edges[0].myNbSegments = 0;
+ for ( int i = 1; i < theFaceSide.NbEdges(); ++i )
+ {
+ edges[ i ].myEdge = theFaceSide.Edge( i );
+ edges[ i ].myIndex = i;
+ edges[ i ].myNbSegments = 0;
+ circularList.link_after( &edges[ i-1 ], &edges[ i ] );
+ }
+ // remove degenerated edges
+ int nbEdges = edges.size();
+ Edge* edge0 = &edges[0];
+ for ( size_t i = 0; i < edges.size(); ++i )
+ if ( SMESH_Algo::isDegenerated( edges[i].myEdge ))
+ {
+ edge0 = circularList.unlink( &edges[i] );
+ --nbEdges;
+ }
+
+ // sort edges by angle
+ std::multimap< double, Edge* > edgeByAngle;
+ int i, iBase = -1, nbConvexAngles = 0, nbSharpAngles = 0;
+ const double angTol = 5. / 180 * M_PI;
+ const double sharpAngle = 0.5 * M_PI - angTol;
+ Edge* e = edge0;
+ for ( i = 0; i < nbEdges; ++i, e = e->myNext )
+ {
+ e->my1stVertex = SMESH_MesherHelper::IthVertex( 0, e->myEdge );
+ if ( e->my1stVertex.IsSame( theBaseVertex ))
+ iBase = e->myIndex;
+
+ e->myAngle = -2 * M_PI;
+ if ( !theConsiderMesh || theFaceSide.VertexNode( e->myIndex ))
+ {
+ e->myAngle = SMESH_MesherHelper::GetAngle( e->myPrev->myEdge, e->myEdge,
+ theFaceSide.Face(), e->my1stVertex );
+ if ( e->myAngle > 2 * M_PI ) // GetAngle() failed
+ e->myAngle *= -1.;
+ }
+ edgeByAngle.insert( std::make_pair( e->myAngle, e ));
+ nbConvexAngles += ( e->myAngle > angTol );
+ nbSharpAngles += ( e->myAngle > sharpAngle );
+ }
+
+ theHaveConcaveVertices = ( nbConvexAngles < nbEdges );
+
+ if ((int) theVertices.size() == theNbCorners )
+ return;
+
+ theVertices.clear();
+
+ if ( !theConsiderMesh || theNbCorners < 4 ||
+ nbConvexAngles <= theNbCorners ||
+ nbSharpAngles == theNbCorners )
+ {
+ if ( nbEdges == theNbCorners ) // return all vertices
+ {
+ for ( e = edge0; (int) theVertices.size() < theNbCorners; e = e->myNext )
+ theVertices.push_back( e->my1stVertex );
+ return;
+ }
+
+ // return corners with maximal angles
+
+ std::set< int > cornerIndices;
+ if ( iBase != -1 )
+ cornerIndices.insert( iBase );
+
+ std::multimap< double, Edge* >::reverse_iterator a2e = edgeByAngle.rbegin();
+ for (; (int) cornerIndices.size() < theNbCorners; ++a2e )
+ cornerIndices.insert( a2e->second->myIndex );
+
+ std::set< int >::iterator i = cornerIndices.begin();
+ for ( ; i != cornerIndices.end(); ++i )
+ theVertices.push_back( edges[ *i ].my1stVertex );
+
+ return;
+ }
+
+ // get nb of segments
+ int totNbSeg = 0; // tatal nb segments
+ std::vector<const SMDS_MeshNode*> nodes;
+ for ( i = 0, e = edge0; i < nbEdges; ++i, e = e->myNext )
+ {
+ nodes.clear();
+ theFaceSide.GetEdgeNodes( e->myIndex, nodes, /*addVertex=*/true, true );
+ if ( nodes.size() == 2 && nodes[0] == nodes[1] ) // all nodes merged
+ {
+ e->myAngle = -1; // to remove
+ }
+ else
+ {
+ e->myNbSegments += nodes.size() - 1;
+ totNbSeg += nodes.size() - 1;
+ }
+
+ // join with the previous edge those edges with concave angles
+ if ( e->myAngle <= 0 )
+ {
+ e->myPrev->myNbSegments += e->myNbSegments;
+ e = circularList.unlink( e )->myPrev;
+ --nbEdges;
+ --i;
+ }
+ }
+
+ if ( edge0->myNext->myPrev != edge0 ) // edge0 removed, find another edge0
+ for ( size_t i = 0; i < edges.size(); ++i )
+ if ( edges[i].myNext->myPrev == & edges[i] )
+ {
+ edge0 = &edges[i];
+ break;
+ }
+
+
+ // sort different variants by quality
+
+ QuadQuality::set quadVariants;
+
+ // find index of a corner most opposite to corner of edge0
+ int iOpposite0, nbHalf = 0;
+ for ( e = edge0; nbHalf <= totNbSeg / 2; e = e->myNext )
+ nbHalf += e->myNbSegments;
+ iOpposite0 = e->myIndex;
+
+ // compose different variants of quadrangles
+ QuadQuality quad;
+ for ( ; edge0->myIndex != iOpposite0; edge0 = edge0->myNext )
+ {
+ quad.myCornerE[ 0 ] = edge0;
+
+ // find opposite corner 2
+ for ( nbHalf = 0, e = edge0; nbHalf < totNbSeg / 2; e = e->myNext )
+ nbHalf += e->myNbSegments;
+ if ( e == edge0->myNext ) // no space for corner 1
+ e = e->myNext;
+ quad.myCornerE[ 2 ] = e;
+
+ bool moreVariants2 = ( totNbSeg % 2 || nbHalf != totNbSeg / 2 );
+
+ // enumerate different variants of corners 1 and 3
+ for ( Edge* e1 = edge0->myNext; e1 != quad.myCornerE[ 2 ]; e1 = e1->myNext )
+ {
+ quad.myCornerE[ 1 ] = e1;
+
+ // find opposite corner 3
+ for ( nbHalf = 0, e = e1; nbHalf < totNbSeg / 2; e = e->myNext )
+ nbHalf += e->myNbSegments;
+ if ( e == quad.myCornerE[ 2 ] )
+ e = e->myNext;
+ quad.myCornerE[ 3 ] = e;
+
+ bool moreVariants3 = ( totNbSeg % 2 || nbHalf != totNbSeg / 2 );
+
+ quad.AddSelf( quadVariants );
+
+ // another variants
+ if ( moreVariants2 )
+ {
+ quad.myCornerE[ 2 ] = quad.myCornerE[ 2 ]->myPrev;
+ quad.AddSelf( quadVariants );
+ quad.myCornerE[ 2 ] = quad.myCornerE[ 2 ]->myNext;
+ }
+ if ( moreVariants3 )
+ {
+ quad.myCornerE[ 3 ] = quad.myCornerE[ 3 ]->myPrev;
+ quad.AddSelf( quadVariants );
+
+ if ( moreVariants2 )
+ {
+ quad.myCornerE[ 2 ] = quad.myCornerE[ 2 ]->myPrev;
+ quad.AddSelf( quadVariants );
+ quad.myCornerE[ 2 ] = quad.myCornerE[ 2 ]->myNext;
+ }
+ }
+ }
+ }
+
+ const QuadQuality& bestQuad = *quadVariants.begin();
+ theVertices.resize( 4 );
+ theVertices[ 0 ] = bestQuad.myCornerE[ 0 ]->my1stVertex;
+ theVertices[ 1 ] = bestQuad.myCornerE[ 1 ]->my1stVertex;
+ theVertices[ 2 ] = bestQuad.myCornerE[ 2 ]->my1stVertex;
+ theVertices[ 3 ] = bestQuad.myCornerE[ 3 ]->my1stVertex;
+
+ return;
+ }
+
+} // namespace
+
+//================================================================================
+/*!
+ * \brief Finds vertices at the most sharp face corners
+ * \param [in] theFace - the FACE
+ * \param [in,out] theWire - the ordered edges of the face. It can be modified to
+ * have the first VERTEX of the first EDGE in \a vertices
+ * \param [out] theVertices - the found corner vertices in the order corresponding to
+ * the order of EDGEs in \a theWire
+ * \param [out] theNbDegenEdges - nb of degenerated EDGEs in theFace
+ * \param [in] theConsiderMesh - if \c true, only meshed VERTEXes are considered
+ * as possible corners
+ * \return int - number of quad sides found: 0, 3 or 4
+ */
+//================================================================================
+
+int StdMeshers_Quadrangle_2D::getCorners(const TopoDS_Face& theFace,
+ SMESH_Mesh & theMesh,
+ std::list<TopoDS_Edge>& theWire,
+ std::vector<TopoDS_Vertex>& theVertices,
+ int & theNbDegenEdges,
+ const bool theConsiderMesh)
+{
+ theNbDegenEdges = 0;
+
+ SMESH_MesherHelper helper( theMesh );
+ if ( myHelper )
+ helper.CopySubShapeInfo( *myHelper );
+
+ StdMeshers_FaceSide faceSide( theFace, theWire, &theMesh,
+ /*isFwd=*/true, /*skipMedium=*/true, &helper );
+
+ // count degenerated EDGEs and possible corner VERTEXes
+ for ( int iE = 0; iE < faceSide.NbEdges(); ++iE )
+ {
+ if ( SMESH_Algo::isDegenerated( faceSide.Edge( iE )))
+ ++theNbDegenEdges;
+ else if ( !theConsiderMesh || faceSide.VertexNode( iE ))
+ theVertices.push_back( faceSide.FirstVertex( iE ));
+ }
+
+ // find out required nb of corners (3 or 4)
+ int nbCorners = 4;
+ TopoDS_Shape triaVertex = helper.GetMeshDS()->IndexToShape( myTriaVertexID );
+ if ( !triaVertex.IsNull() &&
+ triaVertex.ShapeType() == TopAbs_VERTEX &&
+ helper.IsSubShape( triaVertex, theFace ) &&
+ theVertices.size() != 4 )
+ nbCorners = 3;
+ else
+ triaVertex.Nullify();
+
+ // check nb of available EDGEs
+ if ( faceSide.NbEdges() < nbCorners )
+ return error(COMPERR_BAD_SHAPE,
+ TComm("Face must have 4 sides but not ") << faceSide.NbEdges() );
+
+ if ( theConsiderMesh )
+ {
+ const int nbSegments = Max( faceSide.NbPoints()-1, faceSide.NbSegments() );
+ if ( nbSegments < nbCorners )
+ return error(COMPERR_BAD_INPUT_MESH, TComm("Too few boundary nodes: ") << nbSegments);
+ }
+
+ if ( nbCorners == 3 )
+ {
+ if ( theVertices.size() < 3 )
+ return error(COMPERR_BAD_SHAPE,
+ TComm("Face must have 3 meshed sides but not ") << theVertices.size() );
+ }
+ else // triaVertex not defined or invalid
+ {
+ if ( theVertices.size() == 3 && theNbDegenEdges == 0 )
+ {
+ if ( myTriaVertexID < 1 )
+ return error(COMPERR_BAD_PARMETERS,
+ "No Base vertex provided for a trilateral geometrical face");
+
+ TComm comment("Invalid Base vertex: ");
+ comment << myTriaVertexID << ", which is not in [ ";
+ comment << helper.GetMeshDS()->ShapeToIndex( faceSide.FirstVertex(0) ) << ", ";
+ comment << helper.GetMeshDS()->ShapeToIndex( faceSide.FirstVertex(1) ) << ", ";
+ comment << helper.GetMeshDS()->ShapeToIndex( faceSide.FirstVertex(2) ) << " ]";
+ return error(COMPERR_BAD_PARMETERS, comment );
+ }
+ if ( theVertices.size() + theNbDegenEdges < 4 )
+ return error(COMPERR_BAD_SHAPE,
+ TComm("Face must have 4 meshed sides but not ") << theVertices.size() );
+ }
+
+ myCheckOri = false;
+ if ( theVertices.size() > 3 )
+ {
+ uniteEdges( nbCorners, theConsiderMesh, faceSide, triaVertex, theVertices, myCheckOri );
+ }
+
+ if ( nbCorners == 3 && !triaVertex.IsSame( theVertices[0] ))
+ {
+ // make theVertices begin from triaVertex
+ for ( size_t i = 0; i < theVertices.size(); ++i )
+ if ( triaVertex.IsSame( theVertices[i] ))
+ {
+ theVertices.erase( theVertices.begin(), theVertices.begin() + i );
+ break;
+ }
+ else
+ {
+ theVertices.push_back( theVertices[i] );
+ }
+ }
+
+ // make theWire begin from the 1st corner vertex
+ while ( !theVertices[0].IsSame( helper.IthVertex( 0, theWire.front() )) ||
+ SMESH_Algo::isDegenerated( theWire.front() ))
+ theWire.splice( theWire.end(), theWire, theWire.begin() );
+
+ return nbCorners;