I have a convex polygon. I need to divide it into 4 equal parts using the two slit. For example, if I have a square, I have to cut it along the diagonals. Are there some common algorithm for this action?
[Math] Algorithm of cutting a polygon into equal parts
algorithmspolygons
Related Solutions
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.
This is called polygon offsetting rather than scaling.
In the general case, this is much harder than it seems, as different parts of the inflated polygon can overlap each other, letting holes appear, and some edges may completely disappear. The way to handle corners isn't so well defined either.
For an exact solution, have a look at Clipper.
For a simple solution not guaranteed to work on all shapes, you have to consider all vertices in turn, draw lines parallel to the abutting edges, at the desired distance on the right side, and find their intersection.
Best Answer
If $P$ is a polygon it is possible to find a line parallel to any fixed direction which divides $P$ in two region of any given area (of course not larger than the area of $P$).
Suppose that the line is vertical (otherwise you can rotate the polygon or adapt the algorithm). Let $p_1=q_1=(x_1,y_1)$ be the vertex of $P$ which has least possible first coordinate $x_1$. Then enumerate the upper and lower vertices starting from $p_1$ by increasing first coordinate: $p_1,p_2,\dots$ are the upper part of the boundary, $q_1,q_2,\dots$ are the lower part of the boundary. Now consider all vertical lines passing through these points and compute the intersection with the edges on the other side of the polygon. For example suppose that between $p_2$ and $q_2$ the point which is left-most is $p_1$. Then you can find a point on the segment $q_1 q_2$ such that it has the same first coordinate of $p_2$. Adding such points, you may assume that the points $p_k$ and $q_k$ have the same $x$-coordinate.
Now you have subdivided your polygon into a finite union of trapezoids with vertical bases. Finding the area of such trapezoids is very easy. So if you want to find a cut with given area, you pass along these trapezoids until you pass the target area. Then you must divide the last trapezoid with a vertical line, so to get the correct total area. Again this is very simple since the area of the trapezoid is a linear function of the $x$ coordinate of the vertical cutting line.
addendum: Notice that the algorithm, as described, can fail if the polygon is not convex.