Search Unity

How to calculate a point guaranteed to be outside of a convex polygon

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

  1. Sendatsu_Yoshimitsu

    Sendatsu_Yoshimitsu

    Joined:
    May 19, 2014
    Posts:
    673
    I'm trying to write a basic script to determine if one polygon is completely inside another. The easiest way to do this is by drawing a line from the center of the potentially-encapsulated polygon in any direction and testing how many of the encapsulating polygon's edges that line intersects; if the number is odd, one polygon completely contains the other.

    The examples I found suggest doing this with a physics ray that goes to infinity, but since I'm making this calculation before any collision volumes are generated a ray won't do anything. So given a Vector2[] representing a CCW-wound convex hull, is there a simple way to find a point that will exist outside of the polygon 100% of the time?
     
  2. tonemcbride

    tonemcbride

    Joined:
    Sep 7, 2010
    Posts:
    914
    From what I remember you can just do a cross product to check whether the given point is on the left or right hand side of the convex hull vector. If it's on the left then it's inside otherwise it's outside (for CCW winding).

    e.g. If P0 and P1 are the first two points of the convex hull and Q is the test point you can do a cross product of (P1-P0) and (Q-P0) and then check the Z axis of the result to see which side it's on. It would be positive or negative depending on the angle. This is assuming your convex hull is on the XY plane.

    You would then repeat this action on all the convex hull vectors.
     
    DonLoquacious likes this.
  3. Sendatsu_Yoshimitsu

    Sendatsu_Yoshimitsu

    Joined:
    May 19, 2014
    Posts:
    673
    That's super-helpful, thank you! Does this look about right to you?

    Code (CSharp):
    1.         public bool Contains(Polygon p)
    2.         {
    3.             List<Vector3> hullPoints = GetEdgesAsVectors();
    4.             Vector3 Q = p.GetCentroid();
    5.             List<Vector3> crossProducts = new List<Vector3>();
    6.             for (int i = 1; i < hullPoints.Count; i++)
    7.             {
    8.                 Vector3 newCross = Vector3.Cross(hullPoints[1] - hullPoints[0], Q - hullPoints[0]);
    9.                 crossProducts.Add(newCross);
    10.                 if (newCross.y > 0)
    11.                 {
    12.                     return true;
    13.                 }
    14.             }
    15.             return false;
    16.         }
    I think I must've done something wrong, because it's generating weirdly inconsistent results. Here's a visualization: each square is being tested with the above code to check if it's fully inside a yellow rectangle. The red squares returned true with the above, the green guys returned false.

     
  4. tonemcbride

    tonemcbride

    Joined:
    Sep 7, 2010
    Posts:
    914
    Sorry, I forgot to mention that you need to normalise at least one of the vectors in the cross product (best just to normalise both in case, I can't remember off hand).

    Also, in your loop you test hullPoints[1]-hullPoints[0] but that should be

    Code (CSharp):
    1. hullPoints[i]-hullPoints[i-1] and Q - hullPoints[i-1]
    You also need to test the negative condition, for example - return 'false' if any cross product is outside. Your function should return 'true' at the end if everything is within.

    Here's what I mean:

    Code (CSharp):
    1.  public bool Contains(Polygon p)
    2. {
    3.         List<Vector3> hullPoints = GetEdgesAsVectors();
    4.         Vector3 Q = p.GetCentroid();
    5.         for (int i = 1; i < hullPoints.Count; i++)
    6.         {
    7.                 Vector3 newCross = Vector3.Cross((hullPoints[i] - hullPoints[i-1]).normalized, (Q - hullPoints[i-1]).normalized);
    8.  
    9.               // This may need to be change to '< 0' rather than '> 0'
    10.                 if (newCross.y > 0)
    11.                 {
    12.                         return false;
    13.                 }
    14.         }
    15.         return true;
    16. }
     
    Last edited: Jul 23, 2019
  5. halley

    halley

    Joined:
    Aug 26, 2013
    Posts:
    737
    I really can't tell much of anything from that screenshot. I suggest you start with a much simpler test: one yellow box you can move, and one test square you can move. I have a feeling you're working in local space where you intend to work in world space, but a simple test will help you get the feeling for the problem much faster.
     
  6. Sendatsu_Yoshimitsu

    Sendatsu_Yoshimitsu

    Joined:
    May 19, 2014
    Posts:
    673
    Ooh, thanks for the clarification! I think I must be doing something wrong outside the scope of the math we're discussing, but I'm stumped to figure out what it could be. Here's what the revised code generates, the blue square is testing which rectangles it thinks it's inside of, each red rectangle has returned true:



    The debug lines drawing each shape use the same coordinate data that the calculation does, I had it draw me some lines connecting Q to each hull point to verify that the points it was testing matched the vertices (which they did!), and I verified that everything was being wrapped CCW (which it was!). Y is definitely the axis we want to check, since the polygons are drawn on the X,Z axes, and I'm pretty sure that y>0 is the right sign because checking for y<0 tends to produce 50-100 false positives instead of 5-10. It must be something weird on my end, but if the coordinates that are being used to feed the drawn shapes are the same ones being tested I'm struggling to think of what else could silently throw off the results, especially in such a scattered way.
     
  7. tonemcbride

    tonemcbride

    Joined:
    Sep 7, 2010
    Posts:
    914
    That's odd, it sounds like you've tested everything I would have tested too. If you want to zip up the project I can have a look at it for you and see if I can spot anything.
     
  8. Sendatsu_Yoshimitsu

    Sendatsu_Yoshimitsu

    Joined:
    May 19, 2014
    Posts:
    673
    Hey, thank you for the offer! To save time, I stripped out 100% of my own code and made a single test monobehaviour with a really schlocky manual setup. This is the same Contains code we used above (renamed PolyContains to avoid a collision with Monobehaviour's method), I changed it to work with vectors instead of my own container class and hardcoded a big square and a small square. Whenever you run TestOverlap this draws both squares in the editor, but just like the main version its results are weird- in this case, it kinda works but partially-enclosed squares are sometimes true, and sometimes false. If we can get this to work consistently, I can plug that back in and know that 100% of the remaining weirdness is a me problem, not math oddities.

    Code (CSharp):
    1. public class OverlapTester : MonoBehaviour
    2. {
    3.     public GameObject target1;   //Assign a gameobject in the inspector, so we can drag it around and set bluePoly's top-left corner at will
    4.  
    5.  
    6.     public void OnGUI()
    7.     {
    8.  
    9.         if (GUILayout.Button("Overlap Test"))
    10.         {
    11.             TestOverlap();      
    12.         }
    13.     }
    14.  
    15.     public void TestOverlap()
    16.     {
    17.  
    18.         //Hardcode the blue polygon to be contained
    19.         Vector3 b1 = target1.transform.position;
    20.         Vector3 b2 = b1 + Vector3.right * 10;
    21.         Vector3 b3 = b2 + Vector3.back * 10;
    22.         Vector3 b4 = b3 + Vector3.left * 10;
    23.  
    24.         List<Vector3> bluePoly = new List<Vector3> { b1, b2, b3, b4, b1}; //Declare CW for readability
    25.         bluePoly.Reverse(); //Reverse so it's now wound CCW
    26.  
    27.         //Hardcode the green polygon to do the containing
    28.         Vector3 g1 = new Vector3(1, 1, 1);
    29.         Vector3 g2 = g1 + Vector3.right * 20;
    30.         Vector3 g3 = g2 + Vector3.back * 20;
    31.         Vector3 g4 = g3 + Vector3.left * 20;
    32.  
    33.         List<Vector3> greenPoly = new List<Vector3> { g1, g2, g3, g4, g1 };
    34.         greenPoly.Reverse();
    35.  
    36.         //Debug visualization
    37.         for (int i = 1; i < bluePoly.Count; i++)
    38.         {
    39.             Debug.DrawLine(bluePoly[i - 1], bluePoly[I], Color.blue, 5);
    40.         }
    41.  
    42.         for (int i = 1; i < greenPoly.Count; i++)
    43.         {
    44.             Debug.DrawLine(greenPoly[i - 1], greenPoly[I], Color.green, 5);
    45.         }
    46.  
    47.         Debug.Log(PolyContains(greenPoly, GetCentroid(bluePoly)));
    48.     }
    49.  
    50.     public Vector3 GetCentroid(List<Vector3> vertices)
    51.     {
    52.         Vector3 vertex = Vector3.zero;
    53.         for (int i = 0; i < vertices.Count; i++)
    54.         {
    55.             vertex += vertices[I];
    56.         }
    57.  
    58.         return vertex / (float)vertices.Count;
    59.     }
    60.  
    61.     public bool PolyContains(List<Vector3> hullPoints, Vector3 Q)
    62.     {
    63.         for (int i = 1; i < hullPoints.Count; i++)
    64.         {
    65.             Vector3 newCross = Vector3.Cross((hullPoints[I] - hullPoints[i - 1]).normalized, (Q - hullPoints[i - 1]).normalized);
    66.  
    67.             // This may need to be change to '< 0' rather than '> 0'
    68.             if (newCross.y > 0)
    69.             {
    70.                 return false;
    71.             }
    72.         }
    73.  
    74.         return true;
    75.     }
    76. }
    77.  
     
    Last edited: Jul 23, 2019
  9. halley

    halley

    Joined:
    Aug 26, 2013
    Posts:
    737
    I think your cut-and-paste may have autocorrected the capital I in a couple places.

    I don't understand why your lists are { b1 b2 b2 b3 b3 b4 b4 b1 }. Your loops would definitely be trying to see if a point is "to the right of" an unintended zero-length line { b2 b2 } or { b4 b4 }. Your loops would need to step by 2, or just stop duplicating those points.
     
  10. tonemcbride

    tonemcbride

    Joined:
    Sep 7, 2010
    Posts:
    914
    Yeah, it looks like a list of vectors rather than points (e.g. b1->b2 b2->b3 b3->b4). I was basing my code on the assumption it was b1,b2,b3,b4
     
  11. Sendatsu_Yoshimitsu

    Sendatsu_Yoshimitsu

    Joined:
    May 19, 2014
    Posts:
    673
    Ack, that was just a typo from me when I was hardcoding it- I edited it to revise out the doubles (so a 4-sided poly is now g1,g2,g3,g4,g1), I do definitely represent polys as points, not vectors. p.GetEdgesFromVectors() always returns a List<Vector3> with one vector per vertice, and assumes you'll do subtraction if you actually want a direction.
     
  12. tonemcbride

    tonemcbride

    Joined:
    Sep 7, 2010
    Posts:
    914
    I tested it and it seems to work ok for me - as soon as the centroid of the blue polygon goes outside of the green convex hull it returns 'false' correctly.

    I think the problem was in how I read the question. I thought you wanted to check if a single point was within the convex hull (your code just checks the centre of the polygon) and that works ok. If you want to actually check if one convex hull is within another then it's more complicated as there are various cases (for example, you could have a large convex hull where none of the points are intersecting but the inside area is).

    There are various ways of doing this, I've used sutherland-hodgman in the past to clip against the screen polygon so you can do a similar thing:

    http://rosettacode.org/wiki/Sutherland-Hodgman_polygon_clipping#C.23
     
  13. Sendatsu_Yoshimitsu

    Sendatsu_Yoshimitsu

    Joined:
    May 19, 2014
    Posts:
    673
    Hmkay, thanks for confirming- I think this is enough to tune up the rest of what was tripping me up- I really appreciate your guys' time, it helped tremendously. :)
     
  14. tonemcbride

    tonemcbride

    Joined:
    Sep 7, 2010
    Posts:
    914
    If you just wanted something rough you could check each point in your polygon against the convex hull (instead of just checking the centroid). That would work in most cases but it would fall over in cases where the polygon was larger than the hull or if part of the polygon was intersecting without any points actually being inside.
     
  15. Sendatsu_Yoshimitsu

    Sendatsu_Yoshimitsu

    Joined:
    May 19, 2014
    Posts:
    673
    That's probably what I'll end up with if I ever need to do anything fancier- at the moment just checking the centroid is pretty much good enough, but it's nice to have both options. ^^
     
unityunity