4
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ what do you mean with "equal parts"? Same area, or congruent? $\endgroup$ – Emanuele Paolini Dec 10 '13 at 12:11
  • $\begingroup$ @Emanuele Paolini, it means, that equal parts have same area. $\endgroup$ – Denis Dec 10 '13 at 12:12
3
$\begingroup$

You can cut the polygon in half by triangulating it with diagonals from a fixed vertex, and then finding the triangle where the area to the left of it is less than half the total area and the area to the right of it is greater than half the total area and finally computing the halving cut from the fixed vertex.

This gives you two convex polygons with the same area. Now you can apply one of the algorithms described in the papers below:

For the first step, see also

$\endgroup$
4
  • $\begingroup$ what if my second bisection line must be orthogonal to the first one? When I am using your first step, once I have fixed the vertex, I lost all the other cases, did I? $\endgroup$ – Neil Galiaskarov Dec 30 '13 at 17:12
  • $\begingroup$ @NeilGaliaskarov, Is there a theorem that guarantees that two orthogonal bisections exist? $\endgroup$ – lhf Dec 31 '13 at 14:22
  • $\begingroup$ @lhf, There is none, as far as I know. (correct me if I am wrong) That's why once I cut the initial polygon into 4 polygons, I am checking the angle between bisection lines. If it is not 90, I am saying that such bisection can not exist. But can I guarantee that this is the truth? $\endgroup$ – Neil Galiaskarov Dec 31 '13 at 14:32
  • $\begingroup$ @lhf In this question I deal with the orthogonal case. The answer is an orthogonal bisection exists. $\endgroup$ – Calvin Lin Jun 20 '14 at 0:12
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you for the great response. $\endgroup$ – Denis Dec 10 '13 at 12:46
  • $\begingroup$ @Denis: if you like it you can vote it! :-) $\endgroup$ – Emanuele Paolini Dec 10 '13 at 15:01
  • 2
    $\begingroup$ unfortunately, I have no right to vote. This is due to the fact that I have 11 reputation. $\endgroup$ – Denis Dec 10 '13 at 18:04
  • $\begingroup$ I paid my debt to you :) $\endgroup$ – Denis May 30 '15 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.