Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

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:
    691
    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:
    1,992
    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:
    691
    Hmm that makes sense, I'll tune it up- thank you for the feedback! :)
     
  4. Fattie

    Fattie

    Joined:
    Jul 5, 2012
    Posts:
    476
    @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!
     
  5. Fattie

    Fattie

    Joined:
    Jul 5, 2012
    Posts:
    476
  6. Owen-Reynolds

    Owen-Reynolds

    Joined:
    Feb 15, 2012
    Posts:
    1,992
    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?)