4

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?

enter image description here

user3102962
  • 183

2 Answers2

2

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.

Jack D'Aurizio
  • 353,855
  • The problem is obviously solvable. I think the OP is looking for an efficient algorithm, not a proof of solvability. – Chiffa Aug 12 '14 at 18:05
  • An "efficient" algorithm can be designed in the following way: consider the map from $v\in S^1$ to $P_R-P_L$ as an "oriented length". It is a piecewise $C^1$-map since the splitting line parallel to $v$ can be found by considering the inverse image of a point for a monotonic piecewise-quadratic function. Hence we just need a method for finding a zero of a piecewise-$C^1$ function. Bisection, for example. Or Newton's, if we are far from the discontinuities of the derivative. – Jack D'Aurizio Aug 12 '14 at 18:41
  • As a math student, I agree that it might be a great algorithm. As a coder, I have no idea how to implement what you've described. – Chiffa Aug 12 '14 at 18:45
  • It might be hard. For any $v\in S^1$, we need to find three splitting lines for a convex polygon. We can solve the splitting line problem this way: project the vertices of the convex polygon on some line orthogonal to $v$, defining a sequence of points $x_1\leq x_2\leq\ldots\leq x_k$. Over any interval $[x_i,x_{i+1}]$, find the coefficients of the second degree-polynomial that represents the swept area for a point in such interval. Find the index of the interval for which we attain half of the area (better to do this before), then find the exact point by inverting a second-degree polynomial. – Jack D'Aurizio Aug 12 '14 at 18:58
  • By finding three splitting lines, we have the value of the map $\varphi:v\to P_R-P_L$ for a given $v$. Now we just need to interpolate the values of $\varphi$ in order to find a zero. Halley's method should be good. – Jack D'Aurizio Aug 12 '14 at 19:00
0

Edit: Only applies for symmetrical polygons, see comments

Lets take a physical reasoning. Assume that you try to balance the polygon on one line, if the line doesn't include the center of mass (centroid) of the polygon then it's obvious that the polygon will tip to one side and fall off. If it doesn't tip then it is in equilibrium and the mass (area) on either side of the polygon must be equal.

From the above reasoning it is obvious that any line you use to cut the polygon must go through the polygon's centroid.

Under the constraint that both lines must be perpendicular you're left with determining the rotation of the polygon. You can do that by a linear search through $[0,\frac{\pi}{2}[$ due to symmetry of the cut.

Emily L.
  • 286
  • Do you mean that I need to find 1 point - centroid and put both lines there and just rotate polygon? – user3102962 Aug 08 '14 at 12:03
  • Yes. The centroid is easy to compute directly. – Emily L. Aug 08 '14 at 12:07
  • It may not be clear that one can always use the centroid as the center, and guarantee some rotation about that point gives the four areas equal. – coffeemath Aug 08 '14 at 12:13
  • @coffeemath True, but if a solution exsits, then it is centered on the centroid. The linear search will indicate if a solution exists or not. – Emily L. Aug 08 '14 at 12:16
  • Is it true that every line that goes through centroid divides convex polygon in 2 parts of same area? – user3102962 Aug 08 '14 at 12:16
  • Yes. Because any line that doesn't go through the centroid has more mass on either side. – Emily L. Aug 08 '14 at 12:17
  • The centroid has the property that any line through it is such that the figure would just balance if placed on that line in 3d and allowed to rotate about that line. That's not the same thing as both areas being equal, since the moment about the line depends on the distance to the line times the area element. – coffeemath Aug 08 '14 at 12:27
  • You are correct, I had a symmetric polygon in mind which they might not be... poop. I need more tea... – Emily L. Aug 08 '14 at 12:33