# 2D Finding an algorithm to check pizza toppings positions

Using unity 3D 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");


• It sounds like you want to find a Linear Classifier for your two topping positions. That is: the best line that separates the collection of topping 1 items from the topping 2 items. You can rate the quality of the half-and-half split by how closely that line cuts through the center of the pizza, and how few toppings touch the "wrong side" of the line. – DMGregory Aug 12 '20 at 20:21
• Comments are not for extended discussion; this conversation has been moved to chat. – DMGregory Aug 12 '20 at 21:57

## 3 Answers

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

• Sounds like a good solution especially since the polygon covers the distribution over area issue but I could see some corner cases that might pop up. For example if you have to place 7 or more toppings, you basically can throw one on the wrong side as a freebie as long as it is closer to the center than 6 other toppings. Another issue might pop up if you get into quater pizzas where the toppings are too close to edges (basically the polygon would be basically a line). Still a very cool and easy to visualize solution. – Benjamin Danger Johnson Aug 13 '20 at 4:22
• No need to credit me here, this is all your original ideas. :) – DMGregory Aug 13 '20 at 10:59
• @Benjamin There is Room for error for 2 toppings – A.J Aug 13 '20 at 12:04

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;
}


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.