From f110eb63ab21edb33e7abc9aba8e3e96f3d21544 Mon Sep 17 00:00:00 2001 From: azv Date: Wed, 28 May 2014 16:19:27 +0400 Subject: [PATCH] Splitting of constraint groups was implemented --- .../SketchSolver_ConstraintGroup.cpp | 269 ++++++++++++------ .../SketchSolver_ConstraintGroup.h | 17 +- .../SketchSolver_ConstraintManager.cpp | 12 +- 3 files changed, 203 insertions(+), 95 deletions(-) diff --git a/src/SketchSolver/SketchSolver_ConstraintGroup.cpp b/src/SketchSolver/SketchSolver_ConstraintGroup.cpp index b3ea650c7..df5111e6d 100644 --- a/src/SketchSolver/SketchSolver_ConstraintGroup.cpp +++ b/src/SketchSolver/SketchSolver_ConstraintGroup.cpp @@ -12,7 +12,6 @@ #include #include #include -#include #include #include @@ -603,111 +602,117 @@ void SketchSolver_ConstraintGroup::mergeGroups( } // ============================================================================ -// Function: updateGroup +// Function: splitGroup // Class: SketchSolver_ConstraintGroup -// Purpose: search removed entities and constraints +// Purpose: divide the group into several subgroups // ============================================================================ -bool SketchSolver_ConstraintGroup::updateGroup() +void SketchSolver_ConstraintGroup::splitGroup(std::vector& theCuts) { - // Check for valid sketch - if (!mySketch->data()->isValid()) - return true; - - // Fast check for constraint validity. If all constraints are valid, no need to update the group - std::map, Slvs_hConstraint>::reverse_iterator - aConstrIter = myConstraintMap.rbegin(); - bool isAllValid = true; - for ( ; isAllValid && aConstrIter != myConstraintMap.rend(); aConstrIter++) - if (!aConstrIter->first->data()->isValid()) - isAllValid = false; - if (isAllValid) - return false; - - // Remove invalid constraints. - // There only constraint will be deleted (parameters and entities) will be removed below - std::list< boost::shared_ptr > aConstrToDelete; - std::map anEntToDelete; // entities will be removed if no valid constraints use them - std::map aCoincPtToDelete; // list of entities (points) used in coincidence constaints which will be removed; - for (aConstrIter = myConstraintMap.rbegin(); aConstrIter != myConstraintMap.rend(); aConstrIter++) + // Divide constraints and entities into several groups + std::vector< std::set > aGroupsEntities; + std::vector< std::set > aGroupsConstr; + int aMaxNbEntities = 0; // index of the group with maximal nuber of elements (this group will be left in the current) + std::vector::const_iterator aConstrIter = myConstraints.begin(); + for ( ; aConstrIter != myConstraints.end(); aConstrIter++) { - bool isValid = aConstrIter->first->data()->isValid(); - - int aConstrPos = Search(aConstrIter->second, myConstraints); - if (aConstrPos < (int)myConstraints.size()) + Slvs_hEntity aConstrEnt[] = { + aConstrIter->ptA, aConstrIter->ptB, + aConstrIter->entityA, aConstrIter->entityB}; + // Go through the groupped entities and find even one of entities of current constraint + std::vector< std::set >::iterator aGrEntIter; + for (aGrEntIter = aGroupsEntities.begin(); aGrEntIter != aGroupsEntities.end(); aGrEntIter++) { - Slvs_hEntity aConstrEnt[] = { - myConstraints[aConstrPos].ptA, myConstraints[aConstrPos].ptB, - myConstraints[aConstrPos].entityA, myConstraints[aConstrPos].entityB}; - for (int i = 0; i < 4; i++) - if (aConstrEnt[i] != SLVS_E_UNKNOWN) - { - if (anEntToDelete.find(aConstrEnt[i]) == anEntToDelete.end()) - { - anEntToDelete[aConstrEnt[i]] = !isValid; - aCoincPtToDelete[aConstrEnt[i]] = !isValid && (myConstraints[aConstrPos].type == SLVS_C_POINTS_COINCIDENT); - } - else if (isValid) // constraint is valid => no need to remove its entities - { - anEntToDelete[aConstrEnt[i]] = false; - aCoincPtToDelete[aConstrEnt[i]] = false; - } - } - if (!isValid) + bool isFound = false; + for (int i = 0; i < 4 && !isFound; i++) + if (aConstrEnt[i] != 0) + isFound = (aGrEntIter->find(aConstrEnt[i]) != aGrEntIter->end()); + if (isFound) { - myConstraints.erase(myConstraints.begin() + aConstrPos); - if (aConstrIter->second == myConstrMaxID) // When the constraint with highest ID is removed, decrease indexer - myConstrMaxID--; - aConstrToDelete.push_front(aConstrIter->first); + for (int i = 0; i < 4; i++) + if (aConstrEnt[i] != 0) + aGrEntIter->insert(aConstrEnt[i]); + aGroupsConstr[aGrEntIter - aGroupsEntities.begin()].insert(aConstrIter->h); + if (aGrEntIter->size() > aGroupsEntities[aMaxNbEntities].size()) + aMaxNbEntities = aGrEntIter - aGroupsEntities.begin(); + break; } } - } - std::list< boost::shared_ptr >::iterator aDelIter; - for (aDelIter = aConstrToDelete.begin(); aDelIter != aConstrToDelete.end(); aDelIter++) - myConstraintMap.erase(*aDelIter); - - // Remove invalid and unused entities - std::map::reverse_iterator aEDelIter; - std::map::reverse_iterator aPtDelIter = aCoincPtToDelete.rbegin(); - for (aEDelIter = anEntToDelete.rbegin(); aEDelIter != anEntToDelete.rend(); aEDelIter++, aPtDelIter++) - { - if (aEDelIter->second) // remove entity + // Add new group is no one is found + if (aGrEntIter == aGroupsEntities.end()) { - int anEntPos = Search(aEDelIter->first, myEntities); - std::vector::iterator aEntIter = myEntities.begin() + anEntPos; - // Number of parameters for the entity - int aNbParams = 0; - while (aEntIter->param[aNbParams]) aNbParams++; - if (aNbParams == 0) continue; - // Decrease parameter indexer if there are deleted parameter with higher IDs - if (aEntIter->param[aNbParams-1] == myParamMaxID) - myParamMaxID -= aNbParams; - // Remove parameters of the entity - int aParamPos = Search(aEntIter->param[0], myParams); - myParams.erase(myParams.begin() + aParamPos, - myParams.begin() + aParamPos + aNbParams); - - // Remove entity - if (aEDelIter->first == myEntityMaxID) - myEntityMaxID--; - myEntities.erase(myEntities.begin() + anEntPos); - // Remove such entity from myEntityMap - std::map, Slvs_hEntity>::iterator - anEntMapIter = myEntityMap.begin(); - for ( ; anEntMapIter != myEntityMap.end(); anEntMapIter++) - if (anEntMapIter->second == aEDelIter->first) - break; - if (anEntMapIter != myEntityMap.end()) - myEntityMap.erase(anEntMapIter); + std::set aNewGrEnt; + for (int i = 0; i < 4; i++) + if (aConstrEnt[i] != 0) + aNewGrEnt.insert(aConstrEnt[i]); + std::set aNewGrConstr; + aNewGrConstr.insert(aConstrIter->h); + + aGroupsEntities.push_back(aNewGrEnt); + aGroupsConstr.push_back(aNewGrConstr); + if (aNewGrEnt.size() > aGroupsEntities[aMaxNbEntities].size()) + aMaxNbEntities = aGroupsEntities.size() - 1; } - if (aPtDelIter->second) // remove link for this entity from list of coincident points + } + + if (aGroupsEntities.size() <= 1) + return ; + + // Remove the group with maximum elements as it will be left in the current group + aGroupsEntities.erase(aGroupsEntities.begin() + aMaxNbEntities); + aGroupsConstr.erase(aGroupsConstr.begin() + aMaxNbEntities); + + // Add new groups of constraints and divide current group + std::vector aNewGroups; + for (int i = aGroupsEntities.size(); i > 0; i--) + { + SketchSolver_ConstraintGroup* aG = new SketchSolver_ConstraintGroup(mySketch); + aNewGroups.push_back(aG); + } + std::map, Slvs_hConstraint>::const_iterator + aConstrMapIter = myConstraintMap.begin(); + int aConstrMapPos = 0; // position of iterator in the map (used to restore iterator after removing constraint) + while (aConstrMapIter != myConstraintMap.end()) + { + std::vector< std::set >::const_iterator aGIter = aGroupsConstr.begin(); + std::vector::iterator aGroup = aNewGroups.begin(); + for ( ; aGIter != aGroupsConstr.end(); aGIter++, aGroup++) + if (aGIter->find(aConstrMapIter->second) != aGIter->end()) + { + (*aGroup)->changeConstraint(aConstrMapIter->first); + removeConstraint(aConstrMapIter->first); + // restore iterator + aConstrMapIter = myConstraintMap.begin(); + for (int i = 0; i < aConstrMapPos; i++) + aConstrMapIter++; + break; + } + if (aGIter == aGroupsConstr.end()) { - std::vector< std::set >::iterator aCoPtIter = myCoincidentPoints.begin(); - for ( ; aCoPtIter != myCoincidentPoints.end(); aCoPtIter++) - aCoPtIter->erase(aPtDelIter->first); + aConstrMapIter++; + aConstrMapPos++; } } - return false; + theCuts.insert(theCuts.end(), aNewGroups.begin(), aNewGroups.end()); +} + +// ============================================================================ +// Function: updateGroup +// Class: SketchSolver_ConstraintGroup +// Purpose: search removed entities and constraints +// ============================================================================ +bool SketchSolver_ConstraintGroup::updateGroup() +{ + std::map, Slvs_hConstraint>::reverse_iterator + aConstrIter = myConstraintMap.rbegin(); + bool isAllValid = true; + for ( ; isAllValid && aConstrIter != myConstraintMap.rend(); aConstrIter++) + if (!aConstrIter->first->data()->isValid()) + { + removeConstraint(aConstrIter->first); + isAllValid = false; + } + return !isAllValid; } // ============================================================================ @@ -879,6 +884,86 @@ void SketchSolver_ConstraintGroup::removeTemporaryConstraints() myTempPointWhereDragged.clear(); } +// ============================================================================ +// Function: removeConstraint +// Class: SketchSolver_ConstraintGroup +// Purpose: remove constraint and all unused entities +// ============================================================================ +void SketchSolver_ConstraintGroup::removeConstraint(boost::shared_ptr theConstraint) +{ + std::map, Slvs_hConstraint>::iterator + anIterToRemove = myConstraintMap.find(theConstraint); + if (anIterToRemove == myConstraintMap.end()) + return ; + + Slvs_hConstraint aCnstrToRemove = anIterToRemove->second; + // Remove constraint from the map + myConstraintMap.erase(anIterToRemove); + + // Find unused entities + int aConstrPos = Search(aCnstrToRemove, myConstraints); + std::set anEntToRemove; + Slvs_hEntity aCnstEnt[] = {myConstraints[aConstrPos].ptA, myConstraints[aConstrPos].ptB, + myConstraints[aConstrPos].entityA, myConstraints[aConstrPos].entityB}; + for (int i = 0; i < 4; i++) + if (aCnstEnt[i] != 0) + anEntToRemove.insert(aCnstEnt[i]); + myConstraints.erase(myConstraints.begin() + aConstrPos); + if (aCnstrToRemove == myConstrMaxID) + myConstrMaxID--; + std::vector::const_iterator aConstrIter = myConstraints.begin(); + for ( ; aConstrIter != myConstraints.end(); aConstrIter++) + { + Slvs_hEntity aEnts[] = {aConstrIter->ptA, aConstrIter->ptB, + aConstrIter->entityA, aConstrIter->entityB}; + for (int i = 0; i < 4; i++) + if (aEnts[i] != 0 && anEntToRemove.find(aEnts[i]) != anEntToRemove.end()) + anEntToRemove.erase(aEnts[i]); + } + + if (anEntToRemove.empty()) + return ; + + // Remove unused entities + std::map, Slvs_hEntity>::iterator + anEntMapIter = myEntityMap.begin(); + while (anEntMapIter != myEntityMap.end()) + { + if (anEntToRemove.find(anEntMapIter->second) != anEntToRemove.end()) + { + std::map, Slvs_hEntity>::iterator + aRemovedIter = anEntMapIter; + anEntMapIter++; + myEntityMap.erase(aRemovedIter); + } + else anEntMapIter++; + } + std::set::const_reverse_iterator aRemIter = anEntToRemove.rbegin(); + for ( ; aRemIter != anEntToRemove.rend(); aRemIter++) + { + unsigned int anEntPos = Search(*aRemIter, myEntities); + if (anEntPos >= myEntities.size()) + continue; + unsigned int aParamPos = Search(myEntities[anEntPos].param[0], myParams); + if (aParamPos >= myParams.size()) + continue; + int aNbParams = 0; + while (myEntities[anEntPos].param[aNbParams] != 0) + aNbParams++; + if (myEntities[anEntPos].param[aNbParams-1] == myParamMaxID) + myParamMaxID -= aNbParams; + myParams.erase(myParams.begin() + aParamPos, myParams.begin() + aParamPos + aNbParams); + if (*aRemIter == myEntityMaxID) + myEntityMaxID--; + myEntities.erase(myEntities.begin() + anEntPos); + + // Remove entity's ID from the lists of conincident points + std::vector< std::set >::iterator aCoPtIter = myCoincidentPoints.begin(); + for ( ; aCoPtIter != myCoincidentPoints.end(); aCoPtIter++) + aCoPtIter->erase(*aRemIter); + } +} + // ======================================================== diff --git a/src/SketchSolver/SketchSolver_ConstraintGroup.h b/src/SketchSolver/SketchSolver_ConstraintGroup.h index d182233a5..c24268f30 100644 --- a/src/SketchSolver/SketchSolver_ConstraintGroup.h +++ b/src/SketchSolver/SketchSolver_ConstraintGroup.h @@ -9,6 +9,7 @@ #include #include +#include #include #include @@ -39,6 +40,10 @@ public: inline bool isEmpty() const {return myConstraints.empty();} + /// \brief Check for valid sketch data + inline bool isWorkplaneValid() const + {return mySketch->data()->isValid();} + /** \brief Adds or updates a constraint in the group * \param[in] theConstraint constraint to be changed * \return \c true if the constraint added or updated successfully @@ -71,7 +76,7 @@ public: void updateEntityIfPossible(boost::shared_ptr theEntity); /** \brief Searches invalid features and constraints in the group and avoids them - * \return \c true if the group's sketch is invalid and the group should be removed + * \return \c true if the group several constraints were removed */ bool updateGroup(); @@ -80,6 +85,11 @@ public: */ void mergeGroups(const SketchSolver_ConstraintGroup& theGroup); + /** \brief Cut from the group several subgroups, which are not connected to the current one by any constraint + * \param[out] theCuts enlarge this list by newly created groups + */ + void splitGroup(std::vector& theCuts); + /** \brief Start solution procedure if necessary and update attributes of features */ void resolveConstraints(); @@ -121,6 +131,11 @@ protected: Slvs_hParam changeParameter(const double& theParam, std::vector::const_iterator& thePrmIter); + /** \brief Removes constraints from the group + * \param[in] theConstraint constraint to be removed + */ + void removeConstraint(boost::shared_ptr theConstraint); + /** \brief Change values of attribute by parameters received from SolveSpace solver * \param[in,out] theAttribute pointer to the attribute to be changed * \param[in] theEntityID identifier of SolveSpace entity, which contains updated data diff --git a/src/SketchSolver/SketchSolver_ConstraintManager.cpp b/src/SketchSolver/SketchSolver_ConstraintManager.cpp index d1a19edcf..dd502982b 100644 --- a/src/SketchSolver/SketchSolver_ConstraintManager.cpp +++ b/src/SketchSolver/SketchSolver_ConstraintManager.cpp @@ -114,17 +114,25 @@ void SketchSolver_ConstraintManager::processEvent(const Events_Message* theMessa if (aFGrIter != aFeatureGroups.end()) { std::vector::iterator aGroupIter = myGroups.begin(); + std::vector aSeparatedGroups; while (aGroupIter != myGroups.end()) { - if ((*aGroupIter)->updateGroup()) + if (!(*aGroupIter)->isWorkplaneValid()) { // the group should be removed delete *aGroupIter; int aShift = aGroupIter - myGroups.begin(); myGroups.erase(aGroupIter); aGroupIter = myGroups.begin() + aShift; + continue; + } + if ((*aGroupIter)->updateGroup()) + { // some constraints were removed, try to split the group + (*aGroupIter)->splitGroup(aSeparatedGroups); } - else aGroupIter++; + aGroupIter++; } + if (aSeparatedGroups.size() > 0) + myGroups.insert(myGroups.end(), aSeparatedGroups.begin(), aSeparatedGroups.end()); } } } -- 2.39.2