This course will teach participants about installing and configuring Python, syntax, importing, statements, types, strings, booleans, files, lists, tuples, comprehensions, functions, and classes.

given a vector<POINT> of points and another POINT i need to generate the convex hull of points and then determine point is inside or on the line of the convex hull. i have tried to implement grahams scan and then use the pnpoly algorithm from the comp.graphics faq but something is wrong. after finding the convex hull i use pnpoly. if pnpoly returns 1 the points is in the hull else if it is 0 it is possibly on the border so i go through every line possible line segment and check to see if the point is on the line. if it is i return true. i would prefer an algorithm that gives a definite answer to if the point is outside, inside, or on the border. for the ConvexHull algorithm i have attempted to implement Graham's Scan from CLR but I dont think I have done it correctly. I think my sorting may be off. i use sort() with

bool AngleCompare( POINT p1, POINT p2 )

{

p1.x -= p0ref.x;

p1.y -= p0ref.y;

p2.x -= p0ref.x;

p2.y -= p0ref.y;

//return CrossProd( p1, p2 ) > 0;

return atan2( (double) p1.y, p1.x ) < atan2( (double) p2.y, p2.x );

}

the algorithm says to sort the points in counterclockwise order around p0ref. i didnt know how to do this exactly so i searched online and round that it could be done based on the crossproduct but that didnt seem to work so i switched to using atan2 after translating p0ref ot the origin.

here is the rest of the code

bool Equal(double x, double y, double epsilon)

{

//PRECONDITION(epsilon >= 0.0);

// Get the exponent of the smaller of the two numbers (using the

// smaller of the two gives us a tighter epsilon value).

int exponent;

(void) frexp(fabs(x) < fabs(y) ? x : y, &exponent);

// Scale epsilon by the exponent.

double delta = ldexp(epsilon, exponent);

// If the difference between the numbers is smaller than the

// scaled epsilon we'll consider the numbers to be equal.

double difference = fabs(x - y);

bool equal = difference <= delta;

return equal;

}

int pnpoly(vector<POINT> vPoints, POINT pt)

{ int i, j, c = 0;

for (i = 0, j = vPoints.size()-1; i < vPoints.size(); j = i++) {

if ((((vPoints[i].y<=pt.y) && (pt.y<vPoints[j].y)) || ((vPoints[j].y<=pt.y)

&& (pt.y<vPoints[i].y))) &&

(pt.x < (vPoints[j].x - vPoints[i].x) * (pt.y - vPoints[i].y) /

(vPoints[j].y - vPoints[i].y) + vPoints[i].x))

c = !c; }

return c;

}

bool PointInConvexPoly( vector<POINT> vPoints, POINT ptThePoint )

{

int i;

double m, b, y;

bool online;

if( pnpoly( vPoints, ptThePoint ) )

return true;

else

{

vPoints.push_back( vPoints[0] );

online = false;

for( i = 0; i < vPoints.size() - 1; ++i )

{

m = (vPoints[i + 1].y - vPoints[i].y) / (double) (vPoints[i + 1].x - vPoints[i].x);

b = vPoints[i].y - m * vPoints[i].x;

y = m * ptThePoint.x + b;

if( abs( y - ptThePoint.y ) < 1E-6 )

online = true;

}

if( online )

return true;

else

return false;

}

}

bool ConvexHull ( vector<POINT> vPoints, POINT ptThePoint )

{

int size, i, minYIndex;

POINT ptMinY;

stack<POINT> theStack;

POINT p0, p1, p2;

size = (int) vPoints.size ();

for ( i = 0, minYIndex = 0; i < size; ++i )

{

if ( vPoints[i].y < vPoints[minYIndex].y || (vPoints[i].y == vPoints[minYIndex].y && vPoints[i].x < vPoints[minYIndex].x) )

minYIndex = i;

}

ptMinY = vPoints[minYIndex];

vPoints.erase ( vPoints.begin () + minYIndex );

p0ref = ptMinY;

sort ( vPoints.begin (), vPoints.end (), AngleCompare );

for( i = vPoints.size() - 1; i >= 1; --i )

{

if( Equal( atan2( (double) vPoints[i].y - p0ref.y, vPoints[i].x - p0ref.x ), atan2( (double) vPoints[i - 1].y - p0ref.y, vPoints[i - 1].x - p0ref.x ), 1E-6 ) )

{

if( sqrt( pow( vPoints[i].y - p0ref.y, 2) + pow( vPoints[i].x - p0ref.x, 2 ) ) > sqrt( pow( vPoints[i - 1].y - p0ref.y, 2) + pow( vPoints[i - 1].x - p0ref.x, 2 ) ) )

{

vPoints.erase( vPoints.begin() + (i - 1) );

++i;

}

else

vPoints.erase( vPoints.begin() + i );

}

}

for( i = 0; i < vPoints.size(); ++i )

cout << vPoints[i].x << ", " << vPoints[i].y << " " << atan2( (double) vPoints[i].y - p0ref.y, vPoints[i].x - p0ref.x ) << endl;

theStack.push (ptMinY);

theStack.push (vPoints[0]);

theStack.push (vPoints[1]);

for ( i = 2; i < vPoints.size(); ++i )

{

while( true )

{

p1 = theStack.top();

theStack.pop();

p0 = theStack.top();

theStack.push ( p1 );

p2 = vPoints[i];

p2.x -= p0.x;

p2.y -= p0.y;

p1.x -= p0.x;

p1.y -= p0.y;

if( CrossProd( p2, p1 ) < 0 )

break;

else

theStack.pop();

}

theStack.push( vPoints[i] );

}

vPoints.clear();

cout << "points in convex hull - ";

while( !theStack.empty() )

{

vPoints.push_back( p0 = theStack.top() );

cout << "( " << p0.x << ", " << p0.y << " ) ";

theStack.pop();

}

cout << endl;

return PointInConvexPoly( vPoints, ptThePoint );

}

int CrossProd( POINT p1, POINT p2 )

{

return p1.x * p2.y - p2.x - p1.y;

}

bool AngleCompare( POINT p1, POINT p2 )

{

p1.x -= p0ref.x;

p1.y -= p0ref.y;

p2.x -= p0ref.x;

p2.y -= p0ref.y;

//return CrossProd( p1, p2 ) > 0;

return atan2( (double) p1.y, p1.x ) < atan2( (double) p2.y, p2.x );

}

bool AngleCompare( POINT p1, POINT p2 )

{

p1.x -= p0ref.x;

p1.y -= p0ref.y;

p2.x -= p0ref.x;

p2.y -= p0ref.y;

//return CrossProd( p1, p2 ) > 0;

return atan2( (double) p1.y, p1.x ) < atan2( (double) p2.y, p2.x );

}

the algorithm says to sort the points in counterclockwise order around p0ref. i didnt know how to do this exactly so i searched online and round that it could be done based on the crossproduct but that didnt seem to work so i switched to using atan2 after translating p0ref ot the origin.

here is the rest of the code

bool Equal(double x, double y, double epsilon)

{

//PRECONDITION(epsilon >= 0.0);

// Get the exponent of the smaller of the two numbers (using the

// smaller of the two gives us a tighter epsilon value).

int exponent;

(void) frexp(fabs(x) < fabs(y) ? x : y, &exponent);

// Scale epsilon by the exponent.

double delta = ldexp(epsilon, exponent);

// If the difference between the numbers is smaller than the

// scaled epsilon we'll consider the numbers to be equal.

double difference = fabs(x - y);

bool equal = difference <= delta;

return equal;

}

int pnpoly(vector<POINT> vPoints, POINT pt)

{ int i, j, c = 0;

for (i = 0, j = vPoints.size()-1; i < vPoints.size(); j = i++) {

if ((((vPoints[i].y<=pt.y) && (pt.y<vPoints[j].y)) || ((vPoints[j].y<=pt.y)

&& (pt.y<vPoints[i].y))) &&

(pt.x < (vPoints[j].x - vPoints[i].x) * (pt.y - vPoints[i].y) /

(vPoints[j].y - vPoints[i].y) + vPoints[i].x))

c = !c; }

return c;

}

bool PointInConvexPoly( vector<POINT> vPoints, POINT ptThePoint )

{

int i;

double m, b, y;

bool online;

if( pnpoly( vPoints, ptThePoint ) )

return true;

else

{

vPoints.push_back( vPoints[0] );

online = false;

for( i = 0; i < vPoints.size() - 1; ++i )

{

m = (vPoints[i + 1].y - vPoints[i].y) / (double) (vPoints[i + 1].x - vPoints[i].x);

b = vPoints[i].y - m * vPoints[i].x;

y = m * ptThePoint.x + b;

if( abs( y - ptThePoint.y ) < 1E-6 )

online = true;

}

if( online )

return true;

else

return false;

}

}

bool ConvexHull ( vector<POINT> vPoints, POINT ptThePoint )

{

int size, i, minYIndex;

POINT ptMinY;

stack<POINT> theStack;

POINT p0, p1, p2;

size = (int) vPoints.size ();

for ( i = 0, minYIndex = 0; i < size; ++i )

{

if ( vPoints[i].y < vPoints[minYIndex].y || (vPoints[i].y == vPoints[minYIndex].y && vPoints[i].x < vPoints[minYIndex].x) )

minYIndex = i;

}

ptMinY = vPoints[minYIndex];

vPoints.erase ( vPoints.begin () + minYIndex );

p0ref = ptMinY;

sort ( vPoints.begin (), vPoints.end (), AngleCompare );

for( i = vPoints.size() - 1; i >= 1; --i )

{

if( Equal( atan2( (double) vPoints[i].y - p0ref.y, vPoints[i].x - p0ref.x ), atan2( (double) vPoints[i - 1].y - p0ref.y, vPoints[i - 1].x - p0ref.x ), 1E-6 ) )

{

if( sqrt( pow( vPoints[i].y - p0ref.y, 2) + pow( vPoints[i].x - p0ref.x, 2 ) ) > sqrt( pow( vPoints[i - 1].y - p0ref.y, 2) + pow( vPoints[i - 1].x - p0ref.x, 2 ) ) )

{

vPoints.erase( vPoints.begin() + (i - 1) );

++i;

}

else

vPoints.erase( vPoints.begin() + i );

}

}

for( i = 0; i < vPoints.size(); ++i )

cout << vPoints[i].x << ", " << vPoints[i].y << " " << atan2( (double) vPoints[i].y - p0ref.y, vPoints[i].x - p0ref.x ) << endl;

theStack.push (ptMinY);

theStack.push (vPoints[0]);

theStack.push (vPoints[1]);

for ( i = 2; i < vPoints.size(); ++i )

{

while( true )

{

p1 = theStack.top();

theStack.pop();

p0 = theStack.top();

theStack.push ( p1 );

p2 = vPoints[i];

p2.x -= p0.x;

p2.y -= p0.y;

p1.x -= p0.x;

p1.y -= p0.y;

if( CrossProd( p2, p1 ) < 0 )

break;

else

theStack.pop();

}

theStack.push( vPoints[i] );

}

vPoints.clear();

cout << "points in convex hull - ";

while( !theStack.empty() )

{

vPoints.push_back( p0 = theStack.top() );

cout << "( " << p0.x << ", " << p0.y << " ) ";

theStack.pop();

}

cout << endl;

return PointInConvexPoly( vPoints, ptThePoint );

}

int CrossProd( POINT p1, POINT p2 )

{

return p1.x * p2.y - p2.x - p1.y;

}

bool AngleCompare( POINT p1, POINT p2 )

{

p1.x -= p0ref.x;

p1.y -= p0ref.y;

p2.x -= p0ref.x;

p2.y -= p0ref.y;

//return CrossProd( p1, p2 ) > 0;

return atan2( (double) p1.y, p1.x ) < atan2( (double) p2.y, p2.x );

}

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

- You've got a small error in your CrossProd there, should be p1.x * p2.y - p2.x * p1.y.

I haven't checked, but if you do it with arctangens, you may have problems around the X or Y axes.

Also, the problem with sorting is that you're sorting something that's in a circle, so you need to define an arbitrary direction where you 'open up' the circle, so to speak. For example, your angle comparison could first check the X coordinates' signs against each other, and return +1 or -1 depending on that, and if they have the same sign (the angles are in the same hemisphere), then you check the angles against each other. (Or maybe first check the signs of the Y coordinates also, and check the actual angles only when they're in the same quadrant.)

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vcstdlib/html/vclrfalgorithmsort.asp

how would i change AngleCompare to properly sort with CrossProd instead of using atan?

Lessee, what I would do (off the top of my head, untested):

bool AngleCompare( POINT p1, POINT p2 )

{

p1.x -= p0ref.x;

p1.y -= p0ref.y;

p2.x -= p0ref.x;

p2.y -= p0ref.y;

if ((p1.x < 0) && (p2.x > 0)) {

return true;

}

if ((p1.x >= 0) && (p2.x =< 0)) {

return false;

}

return CrossProd( p1, p2 ) > 0;

}

This way you make sure that the angles you're comparing are always less than 180 degrees.

If you order the points in a circle, you have to mark a point on the circle as the start and endpoint, otherwise you don't get a stable ordering.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
C++

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

if( CrossProd( p2, p1 ) < 0 )

break;

else

theStack.pop();