lineapproximator.h

这是一个GPS相关的程序

		{	
			point.x=(point.x-m_xm)/m_dx;
			point.y=(point.y-m_ym)/m_dy;
			return 0;
		};
	};

	template<typename T>
	struct DeNormalizePoint : public std::unary_function< TPoint<T>& , int>, public Rect<T>
	{
		DeNormalizePoint( T xm, T ym, T dx, T dy)
			: Rect<T>(xm,ym,dx,dy){};
		int operator() ( TPoint<T>& point)
		{	
			point.x=m_xm+point.x*m_dx;
			point.y=m_ym+point.y*m_dy;
			return 0;
		};
	};
};

template <typename T, typename TPointContainer, typename TKeyContainer>
void TLine<T, TPointContainer, TKeyContainer>::NormalizePoints()
{
	T xm,ym,dx,dy;
	// normalizing...
	xm=m_limits.GetCenterX();
	ym=m_limits.GetCenterY();
	dx=m_limits.GetWidth();
	dy=m_limits.GetHeight();

	std::for_each( 
		m_cPoints.begin(), 
		m_cPoints.end(), 
		priv::NormalizePoint<T>( xm, ym, dx, dy) 
		);
}

template <typename T, typename TPointContainer, typename TKeyContainer>
void TLine<T, TPointContainer, TKeyContainer>::DeNormalizePoints()
{
	T xm,ym,dx,dy;
	// normalizing...
	xm=m_limits.GetCenterX();
	ym=m_limits.GetCenterY();
	dx=m_limits.GetWidth();
	dy=m_limits.GetHeight();

	std::for_each( 
		m_cPoints.begin(), 
		m_cPoints.end(), 
		priv::DeNormalizePoint<T>( xm, ym, dx, dy) 
		);
}

template <typename T, typename TPointContainer, typename TKeyContainer>
void TLine<T, TPointContainer, TKeyContainer>::DiscardDoublePoints()
{
	// creating a list...
	TPointContainer& pc=GetPoints();
	TPointContainer::iterator it, it1;
	T epsilon2=std::numeric_limits<T>::epsilon();

#ifdef _DEBUG
	size_t count=0;
#endif
	
	it1=it=pc.begin();
	++it1;
	while (it !=pc.end() && it1!=pc.end())
	{
		if ( SqrDist(it, it1) < epsilon2 )
		{
			it1=pc.erase(it1);
		}
		else
		{
			++it; ++it1;
		}
	}

#ifdef _DEBUG
	TRACE( _T("Numer of (double) points erased: %d\n"), count);
#endif
};

template <typename T, typename TPointContainer, typename TKeyContainer>
void TLine<T, TPointContainer, TKeyContainer>::SetPoints( const std::vector<T>& vX, const std::vector<T>& vY)
{
	TPointContainer& pc=GetPoints();
	const size_t n = __min( vX.size(), vY.size());

	pc.resize(n);
	for (size_t i=0;i<n;i++)
	{
		pc[i]= TPoint<T>( vX[i], vY[i]);
	}
};

template <typename T, typename TPointContainer, typename TKeyContainer>
void TLine<T, TPointContainer, TKeyContainer>::GetKeys( std::vector<T>& vX, std::vector<T>& vY) const
{
	const TKeyContainer& kc=GetKeys();
	TKeyContainer::const_iterator it;
	size_t i;

	vX.resize(kc.size());
	vY.resize(kc.size());

	for (it=kc.begin(), i=0;it!=kc.end();it++, i++)
	{
		vX[i]=(*it)->x;
		vY[i]=(*it)->y;
	}
};

template <typename T, typename TPointContainer, typename TKeyContainer>
void TLine<T, TPointContainer, TKeyContainer>::FindLoop(size_t uStartPoint, size_t& uEndPoint)
{
};


/*! \brief Base class for line approximators

	

  \ingroup LAGroup
*/
template <typename T, typename TPointContainer, typename TKeyContainer>
class TLineApproximator : virtual public TLine<T,TPointContainer, TKeyContainer>
{
public:

	//! \name Constructor
	//@{
	TLineApproximator(): m_dTol(0)
	{m_limits.dMinX=m_limits.dMinY=0;m_limits.dMaxX=m_limits.dMaxY=1;};
	~TLineApproximator(){};
	//@}


	//! \name Tolerance
	//@{
	//! sets the tolerance
	void SetTol( double dTol)				{	m_dTol = __max( dTol, 0);};
	//! return current tolerance
	double GetTol() const					{	return m_dTol;};
	//@}

	//! \name Simplification functions
	//@{
	//! Initialize simplification
	void ClearKeys()								{	m_cKeys.clear();};
	//! Compute the keys
	void Simplify();
	/*! Shrink to compression level 
	
	\param dScale scaling to apply [0...1]
	\param dScaleTol [optional] tolerance with respect to dScale, default is 0.05
	\param eTolRight [optional] first estimate on right tolerance
	\param nMaxIter [optional] maximum number of iterations, default is 250
	\return number of estimations
	*/
	size_t ShrinkNorm( T dScale, T dScaleTol = 0.05, T eTolRight = -1, size_t nMaxIter = 250);

	/*! Shrink to a specified number of points
	
	\param n desired number of points in the approximate curve
	\param nTol [optional] tolerance with respect to n, default is 10
	\param eTolRight [optional] first estimate on right tolerance
	\param nMaxIter [optional] maximum number of iterations, default is 250
	\return number of estimations
	*/
	size_t Shrink( size_t nDesiredPoints, size_t nTol = 10, T eTolRight = -1, size_t nMaxIter = 250);
	//@}

protected:
	//! \name Virtual functions
	//@{
	/*! \brief Virtual approximation function

	This function must be overriden in inherited classes. To implement your own algorithm,
	override this function.
	*/
	virtual void ComputeKeys()		{	ClearKeys();};
	//@}

private:
	T m_dTol;
};


template <typename T, typename TPointContainer, typename TKeyContainer>
size_t TLineApproximator<T,TPointContainer,TKeyContainer>::ShrinkNorm( T dScale, T dScaleTol, T eTolRight ,size_t nMaxIter)
{
	// number of points wanted...
	size_t uWantedPoints= __min(m_cPoints.size(), __max(2, static_cast<size_t>(floor(m_cPoints.size()*dScale))));
	size_t uTol = __min(m_cPoints.size(), __max(0, static_cast<size_t>(floor(m_cPoints.size()*dScaleTol)) ));

	return Shrink( uWantedPoints, uTol, eTolRight, nMaxIter);
}

namespace priv
{
//  (C) Copyright Gennadiy Rozental 2001-2002.
//  Permission to copy, use, modify, sell and distribute this software
//  is granted provided this copyright notice appears in all copies.
//  This software is provided "as is" without express or implied warranty,
//  and with no claim as to its suitability for any purpose.

//  See http://www.boost.org for most recent version including documentation.
//
//  File        : $RCSfile: LineApproximator.h,v $
//
//  Version     : $Id: LineApproximator.h,v 1.1.1.1 2006/06/26 15:37:52 oconrad Exp $
//
//  Description : defines algoirthms for comparing 2 floating point values
// ***************************************************************************
	template<typename FPT>
	inline FPT
	fpt_abs( FPT arg ) 
	{
	    return arg < 0 ? -arg : arg;
	}

	// both f1 and f2 are unsigned here
	template<typename FPT>
	inline FPT 
	safe_fpt_division( FPT uf1, FPT uf2 )
	{
	    return  ( uf1 < 1 && uf1 > uf2 * std::numeric_limits<FPT>::max())   
			? std::numeric_limits<FPT>::max() :
	           ((uf2 > 1 && uf1 < uf2 * std::numeric_limits<FPT>::min() || 
	             uf1 == 0)                                               ? 0                               :
	                                                                      uf1/uf2 );
	}

	template<typename FPT>
	class close_at_tolerance 
	{
	public:
	    explicit close_at_tolerance( FPT tolerance, bool strong_or_weak = true ) 
			: p_tolerance( tolerance ),m_strong_or_weak( strong_or_weak ) { };
	
	 explicit    close_at_tolerance( int number_of_rounding_errors, bool strong_or_weak = true ) 
	    : p_tolerance( std::numeric_limits<FPT>::epsilon() * number_of_rounding_errors/2 ), 
	   m_strong_or_weak( strong_or_weak ) {}
	
	    bool        operator()( FPT left, FPT right ) const
	    {
	        FPT diff = fpt_abs( left - right );
	     FPT d1   = safe_fpt_division( diff, fpt_abs( right ) );
	     FPT d2   = safe_fpt_division( diff, fpt_abs( left ) );
	        
	        return m_strong_or_weak ? (d1 <= p_tolerance.get() && d2 <= p_tolerance.get()) 
	                             : (d1 <= p_tolerance.get() || d2 <= p_tolerance.get());
	    }
	
	    // Data members
		class p_tolerance_class
		{
		private:
			FPT f;
		public:
			p_tolerance_class(FPT _f=0):f(_f){};
			FPT  get() const{	return f;};
		};
		p_tolerance_class p_tolerance;	
	private:
	bool        m_strong_or_weak;
	};

	template <typename T>
	inline bool IsEqual(T x, T y)		
	{ 
	  static close_at_tolerance<T> comp( std::numeric_limits<T>::epsilon()/2*10);
	  return comp(fpt_abs(x),fpt_abs(y));
	};
  
	template <typename T>
	inline bool IsEmptyInterval(T x, T y)
	{
		return ( x>=y || IsEqual(x,y) );
	}

};

template<typename T, typename TPointContainer, typename TKeyContainer>
size_t TLineApproximator<T,TPointContainer,TKeyContainer>::Shrink( size_t nDesiredPoints, size_t nTol, T eTolRight, size_t nMaxIter)
{
	if (m_cPoints.size()<2)
		return 0;
	
	// number of points wanted...
	T dWantedPoints= __min(m_cPoints.size(), __max(2, nDesiredPoints));
	T uMinWantedPoints = __min(m_cPoints.size(), __max(2, nDesiredPoints-nTol ));
	T uMaxWantedPoints = __min(m_cPoints.size(), __max(2, nDesiredPoints+nTol ));

	T eLeft, eRight, eMiddle;
	T dResultLeft, dResultRight;
	size_t iter=0;

	// compute limits
	ComputeBoundingBox();

	// normalize if needed
	if (m_bNormalization)
		NormalizePoints();

	// first estimation
	eLeft = 0;
	SetTol(eLeft);

	ComputeKeys();

	dResultLeft =  m_cKeys.size();
	iter++;
	// test if success
	if ( (m_cKeys.size()<=uMaxWantedPoints) && (m_cKeys.size() >= uMinWantedPoints)  )
		goto PostProcess;

	// second estimation
	if (eTolRight<=0)
		eRight=__max( m_limits.GetWidth(), m_limits.GetHeight()); 
	else
		eRight=eTolRight;
	SetTol(eRight);

	ComputeKeys();

	dResultRight =  m_cKeys.size();

	// test if optimization possible
//	if (dResultLeft<uMinWantedPoints ||  dResultRight>uMaxWantedPoints)
//		throw _T("TLineApproximator<T>::Shrink failed: Desired compression ratio not possible in the tolerance domain.");

	iter++;
	// test if success
	if ( ((m_cKeys.size()<=uMaxWantedPoints) && (m_cKeys.size() >= uMinWantedPoints)) || (dResultLeft == dResultRight) )
		goto PostProcess;

	// main loop, dichotomy
	do
	{ 
		// test middle
		eMiddle=(eLeft +eRight)/2;
		SetTol(eMiddle);

		// computing new DP...
		ComputeKeys();
		
		// updating...
		if ( (m_cKeys.size()-dWantedPoints)*( dResultLeft-dResultRight) < 0 )
		{
			eRight=eMiddle;
			dResultRight=m_cKeys.size();
		}
		else 
		{
			eLeft=eMiddle;
			dResultLeft=m_cKeys.size();
		}

		iter++;
	} while ( ((m_cKeys.size()>uMaxWantedPoints) || (m_cKeys.size() < uMinWantedPoints)) /* checking that we are in the acceptable compression */
		&& !priv::IsEmptyInterval(eLeft,eRight) /* interval is non empty */
		&& (dResultRight != dResultLeft)
		&& iter<nMaxIter /* checking for maximum number of iterations */);

PostProcess:
	if (m_bNormalization)
		DeNormalizePoints();

	return iter;
}


template <typename T, typename TPointContainer, typename TKeyContainer>
void TLineApproximator<T,TPointContainer, TKeyContainer>::Simplify()
{
	if (m_cPoints.size()<2)
		return;

	// compute limits
	ComputeBoundingBox();
	
	// preprocess...
	if (m_bNormalization)
		NormalizePoints();

	ComputeKeys();

	if (m_bNormalization)
		DeNormalizePoints();
}

}; // namespace hull

#endif // !defined(AFX_LINEAPPROXIMATOR_H__F5E6E8DC_1185_4AC0_A061_7B3309700E9D__INCLUDED_)