# Testing if position is located inside convex hull

Discussion in 'Scripting' started by Sendatsu_Yoshimitsu, Jul 21, 2019.

1. ### Sendatsu_Yoshimitsu

Joined:
May 19, 2014
Posts:
673
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<Vector2> 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?

Code (CSharp):
1.
2.         public bool ContainsPoint(Vector2 p, List<Vector2> vertices)
3.         {
4.             int j = vertices.Count - 1;
5.             bool inside = false;
6.             for (int i = 0; i < vertices.Count; j = i++)
7.             {
8.                 Vector2 pi = vertices[i];
9.                 Vector2 pj = vertices[j];
10.                 if (((pi.y <= p.y && p.y < pj.y) || (pj.y <= p.y && p.y < pi.y)) &&
11.                     (p.x < (pj.x - pi.x) * (p.y - pi.y) / (pj.y - pi.y) + pi.x))
12.                     inside = !inside;
13.             }
14.             return inside;
15.         }
16.

2. ### Owen-Reynolds

Joined:
Feb 15, 2012
Posts:
908
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.

3. ### Sendatsu_Yoshimitsu

Joined:
May 19, 2014
Posts:
673
Hmm that makes sense, I'll tune it up- thank you for the feedback!

unityunity