h2d::priv::chull Namespace Reference

Holds convex hull code. More...

Classes
struct	Mystack
	Inherits std::stack<> and adds a member function to fetch the underlying std::vector. Used in h2d::convexHull() More...

Functions
template<typename FPT >
size_t	getPivotPoint (const std::vector< Point2d_< FPT >> &in)
	Used int the convex hull algorithm. More...
template<typename T >
int	orientation (Point2d_< T > p, Point2d_< T > q, Point2d_< T > r)
	To find orientation of ordered triplet of points (p, q, r). More...
template<typename FPT >
std::vector< size_t >	sortPoints (const std::vector< Point2d_< FPT >> &in, size_t piv_idx)
	Sorts points by angle between the lines with horizontal axis. More...

Detailed Description

Holds convex hull code.

Function Documentation

getPivotPoint()

template<typename FPT >

size_t h2d::priv::chull::getPivotPoint

(

const std::vector< Point2d_< FPT >> &

in

)

Used int the convex hull algorithm.

{
    auto pmin = h2d::priv::getBmPoint_helper( in );
    return static_cast<size_t>( pmin - in.begin() );
}

Here is the call graph for this function:

Here is the caller graph for this function:

orientation()

template<typename T >

int h2d::priv::chull::orientation	(	Point2d_< T >	p,
		Point2d_< T >	q,
		Point2d_< T >	r
	)

To find orientation of ordered triplet of points (p, q, r).

The function returns following values

• 0 –> p, q and r are colinear
• 1 –> Clockwise
• 2 –> Counterclockwise

Todo:

20240326: this is subject to numerical instability, as it is based on differences.

Todo:

20230212: replace const value HOMOG2D_THR_ZERO_DETER with related static function

{
    HOMOG2D_INUMTYPE px = p.getX();
    HOMOG2D_INUMTYPE py = p.getY();
    HOMOG2D_INUMTYPE qx = q.getX();
    HOMOG2D_INUMTYPE qy = q.getY();
    HOMOG2D_INUMTYPE rx = r.getX();
    HOMOG2D_INUMTYPE ry = r.getY();

    auto val = (qy - py) * (rx - qx) - (qx - px) * (ry - qy);

    if( homog2d_abs(val) < HOMOG2D_THR_ZERO_DETER )
        return 0;  // collinear
    return (val > 0 ? 1 : -1 ); // clock or counterclock wise
}

Here is the call graph for this function:

Here is the caller graph for this function:

sortPoints()

template<typename FPT >

std::vector<size_t> h2d::priv::chull::sortPoints	(	const std::vector< Point2d_< FPT >> &	in,
		size_t	piv_idx
	)

Sorts points by angle between the lines with horizontal axis.

{
    assert( in.size()>3 );

// step 1: create new vector holding the indexes of the points, including the pivot point (will be in first position)
    std::vector<size_t> out( in.size() );
    std::iota( out.begin(), out.end(), 0 ); // fill vector: [0,1,2,...]
    std::swap( out[piv_idx], out[0] );
    auto pt0 = in[piv_idx];

// step 2: sort points by angle of lines between the current point and pivot point
    std::sort(
        out.begin()+1,
        out.end(),
        [&]                  // lambda
        ( size_t i1, size_t i2 )
        {
            auto pt1 = in[i1];
            auto pt2 = in[i2];
            auto dx1 = pt1.getX() - pt0.getX();
            auto dy1 = pt1.getY() - pt0.getY();
            auto dx2 = pt2.getX() - pt0.getX();
            auto dy2 = pt2.getY() - pt0.getY();
            return ((dx1 * dy2 - dx2 * dy1) > 0);
        }
    );
    return out;
}

Here is the call graph for this function:

Here is the caller graph for this function: