How to determine this?

106 Views Asked by At

For any $6$ coplanar points

$$\left(x_{1}+y_{1},x_{2}+y_{2},x_{3}+y_{3}\right)$$

$$\left(x_{1}+y_{2},x_{2}+y_{1},x_{3}+y_{3}\right)$$

$$\left(x_{1}+y_{3},x_{2}+y_{2},x_{3}+y_{1}\right)$$ $$\left(x_{1}+y_{1},x_{2}+y_{3},x_{3}+y_{2}\right)$$ $$\left(x_{1}+y_{2},x_{2}+y_{3},x_{3}+y_{1}\right)$$ $$\left(x_{1}+y_{3},x_{2}+y_{1},x_{3}+y_{2}\right)$$

how to determine whether the convex hull of these $6$ points contains a point with one coordinate equal to $0$. What are the coordinates of that point?

2

There are 2 best solutions below

0
On

Label the points in the given order as $p_1,...,p_6$. Then the convex hull consists of the expressions $ap_1+bp_2+cp_3+dp_4+ep_5+fp_6$ where $a+b+c+d+e+f=1$ and each of $a,...,f$ is nonnegative. Suppose we set the first of the three coordinates to $0$. Since the sum of $a,...,f$ is $1$ this gives the equation $$x_1 + (a+d)y_1+(b+e)y_2+(c+f)y_3=0.\tag{1}$$ I'll just look at the case $x_1>0$ since otherwise it should be similar. EDIT: It turns out I never use $x_1>0$ so this restriction may be dropped.

Now note that except for the $x_1$ on the left of (1), the rest is just the convex hull (on the real line) of the three points $y_1,y_2,y_3$. Assuming without loss that $y_1\le y_2 \le y_3$, this hull is the closed interval $[y_1,y_3].$ Hence equation (1) has a solution iff $x_1+y_1 \le 0 \le x_1+y_3.$ Assuming this holds, we only need "use" the points $y_1,y_3$ to solve it, that is, we may set $b=e=0$ and continue to solve.

Then if $s=a+d,t=c+f$ we want to solve $y_1s+y_3t=-x$ where $s+t=1$ and $s,t\ge 0.$ Doing this gives $$s=\frac{x_1+y_3}{y_3-y_1}$$ and $t=1-s.$ Note that the numerator here is nonnegative because of our (necessary) assumption $x_1+y_1 \le 0 \le x_1+y_3,$ while the denominator is positive unless some of the $y_k$ coincide, a separate case that may have to be done. [EDIT: The only way $y_3-y_1=0$ is when all the $y_k$ are equal, say to $k$, in which case equation (1) becomes simply $x_1+k=0$, where the common values of the $y_k$ make that part of the sum equal to $k$. In this case no matter what choices are made for the coefficients $a,...,f$ there will be $x=0$ in the hull iff $x_1+k=0$, and if so all points of the hull have $x=0$] Also note that the numerator of $t=1-s$ is $-(x_1+y_1)$, again nonnegative because of the above necessary assumption. For specific values for $a,d,c,f$ we may choose any so that their sums are $s$ and $t$, e.g. $a=s,c=t,d=f=0.$

0
On

The six listed points are at $(x_1,x_2,x_3)+(y_{\sigma(1)},y_{\sigma(2)},y_{\sigma(3)})$, where $\sigma$ ranges over the group $S_3$ of all permutations of the set $\{1,2,3\}$. Thus all the points as well as their convex hull lies on the plane $x+y+z=\sum_{i=1}^3(x_i+y_i)$. This plane has a normal vector $\vec{n}=(1,1,1)$.

Write $t=(y_1+y_2+y_3)/3$, and $d_i=y_i-t$, $i=1,2,3.$ Without loss of generality (we are permuting the $y$:s anyway) we can assume that $y_1\le y_2\le y_3$, or equivalently that $d_1\le d_2\le d_3$. Furthermore, we note that by design $d_1+d_2+d_3=0$, so barring the case that they are all equal to zero, their signs differ. The centroid of the hexagon is at the point $$ P=(p_1,p_2,p_3)=(x_1+t,x_2+t,x_3+t). $$

Existence: Determining whether there are points on the hexagon such that their first coordinate vanishes is easy. The smalles value of the first coordinate on any of the points (shared by two points actually) is $x_1+y_1$ and the largest (again shared by two points) is $x_1+y_3$. By convexity, these are also the minimum (resp. maximum) value of the first coordinate on the hexagon. So if the numbers $x_1+y_1$ and $x_1+y_3$ share the same sign, then the first coordinate never vanishes on the hexagon. In all the other cases (obviouly including those where the minimum or maximum is equal to zero) there will be such points.

The existence of points, where the second (resp. the third) coordinate vanishes can similarly be decided by studying the signs of $x_2+y_1$ and $x_2+y_3$ (resp. $x_3+y_1$ and $x_3+y_3$).

Finding the points: It is easy to find one point with a vanishing coordinate (if the existence check reveals that it exists). For example, if $x_1+y_1<0<x_1+y_3$ we find one such point on the line segment connecting e.g. the vertices $(x_1+y_1,x_2+y_2,x_3+y_3)$ and $(x_1+y_3,x_2+y_2,x_3+y_1)$. Similarly for the other coordinates.

BUT, the set of points with a single coordinate vanishing forms a plane. It is possible that such a plane just grazes the hexagon at one of the vertices. More typically the plane and hexagon intersect along a line segment. In that case the end points of that line segment are on those edges of the hexagon whose end points have a change of sign in the coordinate of interest. Identifying those edges would be easy, if we were given the vertices of the hexagon in, say, counterclockwise order. An algorithm for doing that is probably well known in computer graphics. If you can't find anything I can try and cook up something. Essentially the remaining task is equivalent to 3D-clipping the hexagon (hopefully a useful buzzword).