# Testing if position is located inside convex hull

I have a test which, theoretically, is supposed to tell me if a given Vector2 is located within a convex, CCW-wrapped polygon formed by a List representing its vertices. On paper it looks good, and it seems to work consistently on axis-aligned polygons, but I’ve found that when I have odd shapes or rectangles that are rotated off the x-y axis, it becomes really inconsistent and generally claims that points located within the perimeter are not. Is there an obvious way I should be simplifying this to prevent weird results?

``````        public bool ContainsPoint(Vector2 p, List<Vector2> vertices)
{
int j = vertices.Count - 1;
bool inside = false;
for (int i = 0; i < vertices.Count; j = i++)
{
Vector2 pi = vertices[i];
Vector2 pj = vertices[j];
if (((pi.y <= p.y && p.y < pj.y) || (pj.y <= p.y && p.y < pi.y)) &&
(p.x < (pj.x - pi.x) * (p.y - pi.y) / (pj.y - pi.y) + pi.x))
inside = !inside;
}
return inside;
}
``````

Looks like the wrong algorithm. A convex hull check wants the point to be to the right of each line segment. If even a single edge isn’t, the answer is false.

I"m not sure, but I think that funny inside=false; and inside=!inside; is the second part of a concave check. First check if inside the convex hull, then check again - using the loop above – for the an even/odd count of edges you’re on the wrong side of.

Hmm that makes sense, I’ll tune it up- thank you for the feedback!

@Owen-Reynolds , hmm, the algorithm is correct I think?

The way you check if a point is inside is simply to count the line crossings right?

If the count is odd, it is inside. If it is even, it is outside.

Note that the toggling boolean is just the same as checking parity ie counting the crossings.

Note that line 10 is just a convenience check for performance, you can leave it out, line 11 will do all the work. You’re simply checking if a line from the point crosses the segment.

The thing is, the writer is checking the lines “to 0,0” … ie, assuming all the points, the overall “piece of paper” lies in the positive quadrant.

I think!

Ah. That seems to be a different algorithm than what I was thinking. The OP mentioned convex and CCW wrapped (the lines are going in a consistent direction) That made me think of the convex polygon “to the right of every line” test. It also works in 3D as “to the right of every plane” (more or less).

This one doesn’t require convex or any ordering of segments. The wiki and the the OP didn’t have any comments, but maybe the imaginary line is parallel to the x-axis, at the height of the imaginary point? All of those IF’s are checking to see if our line is within the segment, I guess, and to the left(?) or our point? Maybe their code is slightly wrong, or maybe their rotation math has a problem (they say it bugs out when rotated – how are they rotating those points?)