IntersectionPool.h

//===========================================================================
// GoTools - SINTEF Geometry Tools
//
// GoTools module: Intersections, version 1.0
//
// Copyright (C) 2000-2007 SINTEF ICT, Applied Mathematics, Norway.
//
// This program is free software; you can redistribute it and/or          
// modify it under the terms of the GNU General Public License            
// as published by the Free Software Foundation version 2 of the License. 
//
// This program is distributed in the hope that it will be useful,        
// but WITHOUT ANY WARRANTY; without even the implied warranty of         
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          
// GNU General Public License for more details.                           
//
// You should have received a copy of the GNU General Public License      
// along with this program; if not, write to the Free Software            
// Foundation, Inc.,                                                      
// 59 Temple Place - Suite 330,                                           
// Boston, MA  02111-1307, USA.                                           
//
// Contact information: E-mail: tor.dokken@sintef.no                      
// SINTEF ICT, Department of Applied Mathematics,                         
// P.O. Box 124 Blindern,                                                 
// 0314 Oslo, Norway.                                                     
//
// Other licenses are also available for this software, notably licenses
// for:
// - Building commercial software.                                        
// - Building software whose source code you wish to keep private.        
//===========================================================================
#ifndef _INTERSECTIONPOOL_H
#define _INTERSECTIONPOOL_H


#include "ParamObjectInt.h"
#include "IntersectionPoint.h"
#include "IntersectionCurve.h"
#include "Point.h"
#include <boost/shared_ptr.hpp>
#include <vector>
#include <set>
#include <ostream>


namespace Go {



class IntersectionPool;
struct BoundaryIntersectionData;



class IntersectionPool {
public:

    IntersectionPool(boost::shared_ptr<ParamObjectInt> obj1, 
                     boost::shared_ptr<ParamObjectInt> obj2,
                     boost::shared_ptr<IntersectionPool> parent
                     = boost::shared_ptr<IntersectionPool>(),
                     int missing_dir = -1,
                     double missing_value = 0);

    virtual ~IntersectionPool() {}

    void addParamPoints(int nmb_int_pts, 
                        double* pointpar1, 
                        double* pointpar2,
                        boost::shared_ptr<GeoTol> epsge);

    template<class ip_iterator>
    void addCurves(int nmb_int_cvs, 
                   ip_iterator* start_iterators, 
                   ip_iterator* end_iterators);

    template<class ip_iterator>
    void addCurve(ip_iterator start, ip_iterator end);

    void getBoundaryIntersections(std::vector<boost::
                                  shared_ptr<IntersectionPoint> >& bd_ints);

    // @@@ VSK, Change name when implementing.
    // This function is not currently in use.
    bool  checkIfBothPointsLieOnOneEndpointAndNotOfTheSameCurve();


    void getSortedIntersections(std::vector<boost::
                                shared_ptr<IntersectionPoint> >& int_pts);

    std::vector<double> getSortedInnerInts(int pardir);

    void getSortedBdInts(const Point& vec,
                         std::vector<boost::
                         shared_ptr<IntersectionPoint> >& result,
                         int obj_nmb = -1);

    // @@@jbt - NB: Find out about the return value...
    bool checkSortingDir(Point& vec, int sorting_obj);

    // This function is not yet implemented
    void getSortedInts(/* AROUND_BOUNDARIES ,*/
                       std::vector<boost::
                       shared_ptr<IntersectionPoint> >& result)
    { }

    // This function is not yet implemented
    void getAllIntersections(std::vector<boost::
                             shared_ptr<IntersectionPoint> >& result)
    { }

    void getBranchPoints(std::vector<boost::
                         shared_ptr<IntersectionPoint> > & pts);

    void getMidParameter(double *mid);

    // @@@ VSK. Let addIntersection point return the new intersection
    // point. It is sometimes useful.

    boost::shared_ptr<IntersectionPoint>
    addIntersectionPoint(boost::shared_ptr<ParamObjectInt> obj_int1_, 
                         boost::shared_ptr<ParamObjectInt> obj_int2_,
                         boost::shared_ptr<GeoTol> epsge,
                         double *par1, double *par2);

    void includeReducedInts(boost::shared_ptr<IntersectionPool>
                            lower_order_pool);

    void selfIntersectParamReorganise(boost::
                                      shared_ptr<IntersectionPool> sub_pool);

    // This function is to be used only in self intersection context, when
    // boundary intersections are computed.
    void mirrorIntersectionPoints(size_t first);


    bool hasPointsInInner(int pardir);

    bool hasIntersectionPoints() const
    { return (int_points_.size() > 0); }
    
    int numIntersectionPoints() const
    { return int_points_.size(); }

    int numSingularIntersectionPoints();

    bool isInDomain(IntersectionPoint *pnt) const;

    bool closestInDomain(double param[],
                         boost::shared_ptr<IntersectionPoint>& pnt) const;

    bool closestInDomain(const double param[],
                         boost::shared_ptr<IntersectionPoint>& pnt) const;

    bool existIntersectionPoint(int dir, double par);

    int inInfluenceArea(int pardir, double par, bool first_outside = true);

    int inInfluenceArea(int pardir, 
                        double par, 
                        std::vector<boost::
                        shared_ptr<IntersectionPoint> >& int_pts, 
                        bool first_outside = true);

    void getIntersectionPoints(std::vector<boost::
                               shared_ptr<IntersectionPoint> >& int_pts) const;
    
    void getIntersectionCurves(std::vector<boost::
                               shared_ptr<IntersectionCurve> >&
                               int_curves) const;
    
    std::vector<boost::shared_ptr<IntersectionPoint> >&
    getIntersectionPoints();

    const std::vector<boost::shared_ptr<IntersectionPoint> >&
    getIntersectionPoints() const;

    const std::vector<boost::shared_ptr<IntersectionCurve> >&
    getIntersectionCurves() const;

    void getIntersectionPoints(int dir, double par,
                               std::vector<boost::
                               shared_ptr<IntersectionPoint> >& result) const;

    bool hasIntersectionPoints(int dir, double par) const;

    bool checkIntersectionPoints(std::vector<IntPtInfo>& int_pt_info) const;

    bool checkIntersectionLinks() const;

    void removeDoublePoints();

    // Remove ordinary intersection points with only one neighbour when these
    // points lie reasonably close, their tangents point roughly in the same
    // direction, and the neighbour has significantly better accuracy.
    void removeLooseEnds();

    // Check ordinary intersection points to check if the links they belong to
    // are consistent
    void removeFalseCorners();

    void removeDefectLinks();

    void getAllLinks(std::set<boost::shared_ptr<IntersectionLink> >& links);

    void getResult(std::vector<boost::
                   shared_ptr<IntersectionPoint> >& int_points, 
                   std::vector<boost::
                   shared_ptr<IntersectionCurve> >& int_curves) ;

    int lackingParameter() const;

    double lackingParameterValue() const;

    bool atSameBoundary(boost::shared_ptr<IntersectionPoint> pt1,
                        boost::shared_ptr<IntersectionPoint> pt2);

    bool atDifferentBoundary(boost::shared_ptr<IntersectionPoint> pt1,
                             boost::shared_ptr<IntersectionPoint> pt2);

    bool isBoundaryIntersection(boost::shared_ptr<IntersectionPoint> pt1,
                                boost::shared_ptr<IntersectionPoint> pt2);

    bool isBoundaryPoint(boost::shared_ptr<IntersectionPoint> pt1)
        {
            return isBoundaryPoint(pt1.get());
        }

    bool isBoundaryPoint(IntersectionPoint* pt1);

    // @@@ VSK. Yet some new functions. I just make a dummy implementation

    bool fetchLoops(std::vector<std::vector<boost::
                    shared_ptr<IntersectionPoint> > >& loop_ints);

    bool isPAC(std::vector<boost::shared_ptr<IntersectionPoint> >& int_loop);

    void setCoincidence(std::vector<boost::
                        shared_ptr<IntersectionPoint> >& int_loop);

    // Check if there is a connection between the given points through
    // the points in the intersection pool. For the time being

    bool isConnectedInside(boost::shared_ptr<IntersectionPoint> pt1,
                           boost::shared_ptr<IntersectionPoint> pt2);

    void makeIntersectionCurves();

    void getOrigPoints(std::vector<boost::
                       shared_ptr<IntersectionPoint> >& int_pts) const;

    void writeDebug(int singular = 0);

    void splitIntersectionLinks(int fixed_dir, double fixed_val);

    int numParams() const
    { return obj1_->numParams() + obj2_->numParams(); }

    double startParam(int dir) const;

    double endParam(int dir) const;

    void includeCoveredNeighbourPoints();

    void insertInInfluenceInterval(boost::
                                   shared_ptr<IntersectionPoint> pt_in_pool,
                                   double *parvals, int pardir);

    void synchronizePool();

    void cleanUpPool(int first_idx = 0, double epsge=1.0e-15);


    void removeIntPoint(boost::shared_ptr<IntersectionPoint> int_point);
    
    void removeIntPoint2(boost::shared_ptr<IntersectionPoint> int_point);
    
    void removeIntPoints(double* frompar, double* topar, bool only_inner = false);
    
    void intersectAlongCommonBoundary(double frac,
                                      std::vector<BoundaryIntersectionData>&
                                      isects);

    void removeBoundaryIntersections(bool single_pt=true);

    bool
    verifyIntersectionLink(const boost::shared_ptr<IntersectionLink>& link,
                           int recursion_limit = 10)
        const;

    bool 
        checkIntersectionChain(IntersectionPoint *pnt,
                               IntersectionPoint *first, 
                               IntersectionPoint *prev = 0);

    bool validate() const;

    // Remove unnecessary or harmful intersection points (called
    // before making IntersectionCurves.
    void weedOutClutterPoints() ; 

    void writeIntersectionPoints() const;

    void writeIntersectionLinks() const;

    friend class SfSfIntersector;

private:
    // Data members

    // The intersecting objects
    boost::shared_ptr<ParamObjectInt> obj1_;
    boost::shared_ptr<ParamObjectInt> obj2_;

    // Intersection points (both isolated and on curves)
    std::vector<boost::shared_ptr<IntersectionPoint> > int_points_;

    // Intersection curves
    std::vector<boost::shared_ptr<IntersectionCurve> > int_curves_;

    int missing_param_index_;
    double missing_param_value_;

    boost::shared_ptr<IntersectionPool> prev_pool_;
//     static const double REL_PAR_RES_; // a tolerance - @move this
//                                    // somewhere else??

    // Functions

    void add_point_and_propagate_upwards(boost::
                                         shared_ptr<IntersectionPoint> point);

    void iterateToSplitPoint(boost::shared_ptr<IntersectionLink> link,
                             int fixed_dir, double fixed_value,
                             double par[], double& dist);

    void fetch_relevant_points(const std::vector<boost::
                               shared_ptr<IntersectionPoint> >& ipoints,
                               int missing_dir,
                               double missing_value);

    void constructor_implementation(boost::shared_ptr<ParamObjectInt> obj1, 
                                    boost::shared_ptr<ParamObjectInt> obj2,
                                    boost::shared_ptr<IntersectionPool> parent,
                                    int missing_dir,
                                    double missing_value);

    void associate_parent_points(std::vector<boost::
                                 shared_ptr<IntersectionPoint> >& children,
                                 int lacking_ix,
                                 double lacking_val);

    void transfer_links_to_parent_points(std::vector<boost::
                                         shared_ptr<IntersectionPoint> >&
                                         children,
                                         int lacking_ix);

    void get_param_limits(int pardir,
                          double& min_param, double& max_param) const;

    void
    set_correct_differentiating_domain(boost::
                                       shared_ptr<IntersectionPoint> ip) const;

    void separate_isoparametric_curves(std::vector<std::vector<int> >&
                                       curve_indices) const;

    void separate_at_problematic_points(std::vector<std::vector<int> >&
                                        curve_indices) const;

    int endof_noniso_curve(const std::vector<int>& cur_cv,
                           int start_ix) const;

    int endof_isoparametric_curve(const std::vector<int>& cur_cv,
                                  int start_ix) const;

    // Remove curves which are judged unnecessary or just 'clutter'.
    void weedOutClutterCurves(std::vector<std::vector<int> >& curves) const;

    void locateEdgepoints(Array<std::vector<boost::
                          shared_ptr<IntersectionPoint> >, 4>& obj1_edges,
                          Array<std::vector<boost::
                          shared_ptr<IntersectionPoint> >, 4>& obj2_edges);

    void determine_free_dir_parameter(double* par, 
                                      boost::shared_ptr<IntersectionLink> link,
                                      int free_dir,
                                      int fixed_dir,
                                      double fx_val);
};


//===========================================================================
//                  IMPLEMENTATION OF INLINE METHODS
//===========================================================================


//===========================================================================
inline void 
IntersectionPool::
getIntersectionPoints(std::vector<boost::
                      shared_ptr<IntersectionPoint> >& int_pts) const
//===========================================================================
{
    int_pts = int_points_;
}


//===========================================================================
inline void 
IntersectionPool::
getIntersectionCurves(std::vector<boost::
                      shared_ptr<IntersectionCurve> >& int_curves) const
//===========================================================================
{
    int_curves = int_curves_;
}


//===========================================================================
inline std::vector<boost::shared_ptr<IntersectionPoint> >&
IntersectionPool::getIntersectionPoints()
//===========================================================================
{
    return int_points_;
}


//===========================================================================
inline const std::vector<boost::shared_ptr<IntersectionPoint> >& 
IntersectionPool::getIntersectionPoints() const
//===========================================================================
{
    return int_points_;
}


//===========================================================================
inline const std::vector<boost::shared_ptr<IntersectionCurve> >&
IntersectionPool::getIntersectionCurves() const 
//===========================================================================
{
    return int_curves_;
}


//===========================================================================
template<class ip_iterator>
inline void IntersectionPool::addCurves(int nmb_int_cvs, 
                                        ip_iterator* start_iterators, 
                                        ip_iterator* end_iterators)
//===========================================================================
{
    for (int i = 0; i < nmb_int_cvs; ++i) {
        addCurve(start_iterators[i], end_iterators[i]);
    }
}


//===========================================================================
template<class ip_iterator>
inline void IntersectionPool::addCurve(ip_iterator start, ip_iterator end)
//===========================================================================
{
    boost::shared_ptr<IntersectionCurve>
        temp(new IntersectionCurve(start, end));
    int_curves_.push_back(temp);
}


//===========================================================================
inline int IntersectionPool::lackingParameter() const
//===========================================================================
{
    return missing_param_index_;
}


//===========================================================================
inline double IntersectionPool::lackingParameterValue() const
//===========================================================================
{
    return missing_param_value_;
}



//===========================================================================
struct BoundaryIntersectionData {
//===========================================================================

    int dir[2];

    double par[2];

    std::vector<boost::shared_ptr<IntersectionPoint> > pts;

};


} // namespace Go


#endif  // _INTERSECTIONPOOL_H

---