algorithmspolygons
I have a convex polygon and I want to divide into 4 equal parts using the two perpedicular splits. Like in a picture. I need s1 = s2 = s3 = s4; I need to get coordinates of point where the lines cross and angle of rotation of polygon.
I think that firstly I need to divide polygon in 2 parts by 1st line, then by 2nd line. Then I get point of line cross and then I check s1=s2=s3=s4. If it is not then I need to rotate polygon at some angle.
Is there anything better for this purpose?
To be read in order, and ideally not all at once.
Hint 1
Given a vertex $p_i$, let $\mathbf n_i$ the unit vector such that the closed half-plane "to the left" of oriented line $qp_i$ is: $$\{ x\in\mathbb R^2\mid \langle x-p_i,\,\mathbf n_i\rangle \ge 0\}$$ where $\langle \mathbf a,\,\mathbf b\rangle$ denotes the scalar product of vectors $\mathbf a$ and $\mathbf b$. Looking at those unit vectors should be useful.
Hint 2
Vertex $p_i$ supports a right tangent line if and only if $\langle p_{i-1}-p_i,\, \mathbf n_i\rangle \ge 0$ and $\langle p_{i+1}-p_i,\,\mathbf n_i\rangle\ge 0$, with $p_{-1}=p_n$ and $p_{n+1}=p_0$.
Hint 3
If a vertex $p_i$ doesn't satisfy the two conditions from hint 2, you can (very often) figure out "which way" the proper vertex is wrt $p_i$. The only situation where you cannot figure that out, is if $p_i$ supports a "left tangent line".
Hint 4
Dichotomic search?
Hint 5
No.
Take a look at the following picture where the initial convex polygon boundary is in red :
It represents the variations of function $z=d(x,y)$ defined as the (internal) distance function to the boundary of the polygon. The peak $(x_0,y_0,z0)$ is such that $(x_0,y_0)$ is the most internal point and $z_0$ is its closes distance to the polygon boundary.
The different planes $P_k$ that need to be considered are those that cross the horizontal plane along edges $E_k$ of the polygon with, say, a 45° inclination. Seeing the resulting surface as a roof constituted by different planar panes, the skeleton is, in a natural way, the projection of the panes' limits (locus of points whose distance to the border can be computed in two ways = pieces of angle bissectors : here we are...).
Mathematicaly, the above distance function is defined in this way :
$$d(x,y)=\min_k(f_k(x,y)) \ \text{where} \ z=f_k(x,y)$$
is the equation of the $k$th plane.
For a fully automatic obtention of the skeleton in a general case, one has to keep track of the "right planes at the right place" by using a hierarchical organisation, proceeding inward, from the border, keeping track of which plane is still "active" at such and such distance, until there is ... no longer any active plane.
Here is the Matlab program that I have conceived for such a picture, providing in particular the exact plane equations.
x=[0,3,5,7,8,6,3,0,0];y=[0,0,1,3,7,8,7,3,0]; L=length(x)-1; plot(x,y,'r','linewidth',2); [X,Y]=meshgrid(0:0.01:8,0:0.01:8); Zc=10*ones(size(X));hold on; Z1=zeros(size(X)); for k=1:L vx=x(k+1)-x(k);vy=y(k+1)-y(k); Vx=vx/norm([vx,vy]);Vy=vy/norm([vx,vy]); xm=(x(k+1)+x(k))/2;ym=(y(k+1)+y(k))/2; P=[xm-Vy,ym+Vx,sqrt(1/2)]';% normal vect. to plane P_k M=[x(k),x(k+1);y(k),y(k+1)]; dd=det([[M,[P(1);P(2)]];ones(1,3)]) den=1/dd; Z=den*P(3)*(Y*vx-X*vy+det(M));%plane equ. Zc=min(Zc,Z);Zc=max(Zc,Z1); end; view([-29,36]); g=surf(X,Y,Zc); set(g,'edgecolor','none')
Appendix : A very straightforward way to obtain the analytical equation of the two angle bissectors of two lines with resp. equations $a_1x+b_1y+c_1=0$ and $a_2x+b_2y+c_2=0$ is to express that a point $M(x,y)$ belongs to one of them iff its signed distance is the same to both of them, i.e.,
$$\dfrac{a_1x+b_1y+c_1}{\sqrt{a_1^2+b_1^2}}=\pm \dfrac{a_2x+b_2y+c_2}{\sqrt{a_2^2+b_2^2}}$$
($\pm$ sign for distinguishing interior and exterior angle bissectors)
Best Answer
This only applies for convex polygons.
We can use a continuity argument. Fix a direction $v\in S^1$: there exists a (only one) line $t_v$ parallel to $v$ that splits the area of the polygon in two equal parts, $L_v$ on the left of $t_v$ and $R_v$ on the right of $t_v$. For a similar reason, there exists a (only one) line $l_v$ orthogonal to $t_v$ that splits in two equal parts $L_v$, and a (only one) line $r_v$, orthogonal to $t_v$, that splits in two equal parts $R_v$. Call $P_L=t_v\cap l_v$ and $P_R=t_v\cap r_v$. Say that $v$ is "right-handed" if $P_R-P_L$ has the same direction of $v$, "left-handed" if $P_R-P_L$ has the opposite direction. If $v$ is right-handed then $-v$ is left-handed, so somewhere between $v$ and $-v$ we must have a direction that is neither left- or right- handed, i.e. a solution for our splitting problem.
And yes, this is just a consequence of the Borsuk-Ulam theorem.