Search Unity

Testing if position is located inside convex hull

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

  1. Sendatsu_Yoshimitsu

    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

    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

    Sendatsu_Yoshimitsu

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