Detecting if objects are at opposite coordinates

133 Views Asked by At

distribution of ingredients on pizza

I am a game developer and I'm stuck at this trying to get a mathematical equation to detect if red and blue ingredients are always on opposite sides relative to each other on the pizza. I have $(x,y)$ of every single ingredient (blue and red). What equation should I use in order to detect if red ingredients are opposite to blue in every way we rotate the pizza. (This is not a game question, I just want the math to solve this problem)

Pizza axis size : $x$ from $-3$ to $3$ , $y$ from $-3$ to $3$

2

There are 2 best solutions below

0
On

So I'm assuming that the question your're asking is if we can find a line that cuts the pizza in two and such that all the red points are on one side of the line and all the blue points are on the other. The best way to do this is to... well, try a whole bunch of lines and see if one works. But, the real question is, how do we know if a particular line "works"? First convert all of the $(x,y)$ coordinates of your points into polar coordinates $(r,\theta)$ using the transformations $$r=\sqrt{x^2+y^2}$$ $$\theta=\operatorname{atan2}(y,x)$$ (actually the radius transformation isn't needed, but whatever) Suppose we've chosen a line that distends an angle of $\varphi$ from the $x$ axis. Then this line cuts the pizza into two segments - $\theta\in[\varphi,\varphi+\pi]$("region 1") and $\theta\in[\varphi-\pi,\varphi]$("region 2"). First pick one blue point and find which region it is in. Then see if the rest of the blue points are in this region. Repeat the process for the red points and see if they are all in the other region. If this all works, hooray! If not, move on to the next guess for $\varphi$. I'll give a short example, illustrated in the picture below: points

The blue points have the following Cartesian coordinates: $$\text{Blue points(Cartesian)}=\{\left(-0.5,0.5\right),\left(-0.9,0.1\right),\left(-0.3,0.8\right),\left(0,0.7\right),\left(-0.7,-0.2\right),\left(0.2,0.59\right),\left(-0.38,0.21\right)\}$$ And the red points: $$\text{Red points(Cartesian)}=\{\left(0.5,-0.5\right),\left(0.9,-0.1\right),\left(0,-0.3\right),\left(0.2,-0.89\right),\left(0.5,0.3\right),\left(-0.3,-0.77\right),\left(0.3,-0.4\right)\}$$ The purple line has a slope of $1.8$ which corresponds to an angle $\varphi\approx 1.0636978224$ radians or $60.95^{\circ}$. It splits the pizza into two segments: $\theta \in [1.0636978224,1.0636978224+\pi]$, and $\theta\in[1.0636978224-\pi,1.0636978224]$. The corresponding angles are $$\text{Red angles}=\{-0.78539816, -0.11065722, -1.57079633, -1.34974926, 0.5404195 , -1.94231418, -0.92729522\}$$ $$\text{Blue angles}=\{2.35619449, 3.0321417 , 1.929567 , 1.57079633, -2.86329299, 1.24396967, 2.63673128\}$$

Basically check a bunch of $\varphi$ and see if one works.

0
On

I assume you want to solve the following problem:

Given a set of $k$ red points $\{R_1, R_2, \ldots R_k\}$ and a set of $k$ blue points $\{B_1, B_2, \ldots B_k\}$ in the plane, decide if there is a line $\sigma$ such that if you reflect the blue points across the line $\sigma$ you get the red points (and vice versa) and calculate the line if it exists.

If we know the line $\sigma$, the corresponding blue-red-pairs can be found easily:

Fix an arbitrary point $M(m_1/m_2)$ on $\sigma$ and create a new coordinate system with origin $M$ and the first axis is $\sigma$ and the second axis is the normal of $\sigma$ through $M$. Assume $\frak{e}$ is the unity vector of $\sigma$ and $\frak{n}$ is the normal vector of $\frak{e}$. The coordinates of a point $X(x_1,x_2)$ in the new coordinate systems are $((X-M)\cdot {\frak e}, (X-M)\cdot {\frak n})$, where $\cdot$ is the scalar product of two vectors. If $(u,v)$ are the coordinates of a point in the new coordinate system, its reflection across the line $\sigma$ has the coordinates $(u,-v)$ in the new coordinate system, and $u{\frak e}-v{\frak n}$ in the original coordinate system. So we can easily identify which blue point is mirrored to which red point.

But how can we find out the symmetry axis $\sigma$?

If $B_i$ is a bluepoint and $R_j$ is the corresponding red point, then $\sigma$ is the symmetry line of $B_i$ and $R_j$. The line $\sigma$ contains the point $\frac 1 2 (B_i+R_j)$ and is normal to the line through $B_i$ and $R_j$, so its normal vector is $(B_i-R_j)$.

So we can choose $i=1$ and then check for every $j\in \{1,\ldots,k\}$ if the symmetry axis defined by $B_1$ and $R_j$ is a symmetry axis for all points. So we have to check $k$ possible symmetry axis.

But there is a simpler way. If $C_b$ is the center of mass of the blue points and $C_r$ is the center of mass of the red points and the blue and the red points are symmetric about a symmetry line $\sigma$ then the centers of mass are symmetric, too.

So $\sigma$ can be calculated as the symmetry line of the points $C_b$ and $C_r$.

The point $C_b$ can be calculated as $\frac 1 k \sum_{i=1}^k B_i$ and $C_r$ can be calculated as $\frac 1 k \sum_{i=1}^k R_i$.

The case $C_b=C_r$ will not happen if the blue points are all on the same side of the symmetry line.

Also when or $C_b \approx C_r$ some special treatment may be necessary because of the numerical problems that arise.