Gift Wrapping Algorithm with Collinear Points

Question

So I've written the following code based on examples of the Gift Wrapping Algorithm for finding the Convex Hull of a group of points:

std::vector<sf::Vector2f> convexHull(const std::vector<sf::Vector2f>& _shape)
{
    std::vector<sf::Vector2f> returnValue;    
    returnValue.push_back(leftmostPoint(_shape));
    for (std::vector<sf::Vector2f>::const_iterator it = _shape.begin(), end = _shape.end(); it != end; ++it)
    {
        if (elementIncludedInVector(*it, returnValue)) continue;
        bool allPointWereToTheLeft = true;
        for (std::vector<sf::Vector2f>::const_iterator it1 = _shape.begin(); it1 != end; ++it1)
        {
            if (*it1 == *it || elementIncludedInVector(*it1, returnValue)) continue;
            if (pointPositionRelativeToLine(returnValue.back(), *it, *it1) > 0.0f)
            {
                allPointWereToTheLeft = false;
                break;
            }
        }
        if (allPointWereToTheLeft)
        {
            returnValue.push_back(*it);
            it = _shape.begin();
        }
    }
    return returnValue;
}

Here is my function for determining on which side of a line a third point is:

float pointPositionRelativeToLine(const sf::Vector2f& A, const sf::Vector2f& B, const sf::Vector2f& C)
{
    return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}

Returning a negative number means the point is on one side, positive on the other, 0 means the three points are collinear. And now, the question: How can the above code be modified so that it works correctly even when there are collinear points in _shape?

Answer 1

If some points are collinear, you have to choose the farthest point from them (with max distance to current point)

Answer 2

You can base your reasoning on an "exclude" relation between two points (around a common center), with the meaning that A excludes B if the relative placement of A and B proves that B cannot be on the convex hull.

On the figure, the green points exclude the blue one, while the red don't. Among two aligned points, the farthest from the center excludes the other. The exclusion locus is an open half-plane and a half-line.

Note that "excludes" is transitive and defines a total ordering.