Algorithm to check whether pizza toppings are divided half-and-half

Question

Using Unity, I am creating a 2D pizza game and I am stuck at finding an algorithm to solve this problem which is Detecting if the pizza is half and half taking into consideration that the user can put the toppings in all rotations shown in the picture and lot more possible distributions.

I used Physics2D.OverlapAreaAll to get position of ingredients on the pizza and I tried getting the sumX and sumY of coordinates of all topping A and sumX and sumY of all topping B and adding A.sumX + B.sumX and A.sumY + B.sumY and if the 2 totals are between 0 and 1 then A and B are on opposite sides but the bad distribution of toppings in the second pic is also accepted by my algorithm. The toppings must be spread like in the 1st pic

I need some easier way to detect the correct distribution of ingredients maybe using collisions or something.

if (sumX > -ErrLvl && sumX < ErrLvl && sumY > -ErrLvl && sumY < ErrLvl)  
    Debug.Log("APPROVED HALF-HALF PIZZA");
else
    Debug.Log("BAD HALF-HALF PIZZA");

Answer 1

After getting help from @DMGregory I was able to solve this by :

1. Getting the center of the toppingsA and toppingsB
2. Finding 6 most far toppings from the centers
3. generate 2 polygons based on these 6 vertices for each topping
4. check if polygons have the minumum area needed to cover most of the half and that they don't collide

This gives accurate half-half pizza detection

Answer 2

This is probably not the best solution in terms of performance but the easiest thing you could do (and this may be okay if you limit the number of toppings) would be to iterate though all topping positions and check the angles between them (you can find someone looking for a similar solution here) This would require iteration through an array while in array giving you performance of O(n^2) which is usually not okay but in some cases could be acceptable.

While I haven't been able to test this, you could possibly reduce performance to O(n) by iterating through the array of toppings once and comparing the angle between topping 0 and topping n to find the topping with the largest angle. Then iterate through again and compare all toppings to the previous max. If any angle is greater than 180 then you know your player is not yet good enough to work at Papa's Pizzeria.

Here is some rough pseudo code. Note that the GetAngleBetween function might not be able to handle obtuse angles, you may need to use cross products to check what side of the line transform B is when compared to the line formed by transform A and the pizza origin. Note that this also doesn't check things like the bounds of your topping only the center point (which honestly is probably fine as long as none of your virtual clients have allergies).

float GetAngleBetween(Tranform a, Transform b)
{
    return angle = Mathf.Atan2(b.position.y - a.position.y, b.position.x - a.position.x) * 180.0f / Mathf.PI; // You may need to use cross product for angles over 180
}

bool CheckToppings(List<Transform> toppings, float angleLimit)
{
    // Find farthest topping to one side
    int maxToppingIndex = 0;
    float maxAngle = 0.0f;

    for (int toppingIndex = 0; toppingIndex < toppings.Count; toppingIndex++)
    {
        float angle = GetAngleBetween(toppings[maxToppingIndex], toppingx[toppingIndex]);

        if (angle > maxAngle)
        {
            maxToppingIndex = toppingIndex;
            maxAngle = angle;
        }
    }

    // Find farthest topping to the other side
    int maxToppingIndex2 = maxToppingIndex; // cache this for later
    maxAngle = 0.0f;

    for (int toppingIndex = 0; toppingIndex < toppings.Count; toppingIndex++)
    {
        float angle = GetAngleBetween(toppings[maxToppingIndex], toppingx[toppingIndex]);

        if (angle > maxAngle)
        {
            maxToppingIndex = toppingIndex;
            maxAngle = angle;
        }
    }
    
    return GetAngleBetween(toppings[maxToppingIndex], toppings[maxToppingIndex2]) <= angleLimit;
}

Answer 3

One simple but likely good enough solution would be to brute-force it. Try many different possible pizza layouts and rate the player based on the one which is most favorable to them.

For the half-and-half layout, you could calculate the layouts with lines of separation in increments of 10° to get 18 different ratings (the other 180° would be redundant as they would just be mirrors of the 18 cases tested before) and pick the best one.