Algoritmo de corte de un polígono en partes iguales

Question

Tengo un polígono convexo. Necesito dividirlo en 4 partes iguales utilizando las dos rendijas. Por ejemplo, si tengo un cuadrado, tengo que cortarlo a lo largo de las diagonales. ¿Existe algún algoritmo común para esta acción?

Answer 1

Si $P$ es un polígono es posible encontrar una línea paralela a cualquier dirección fija que divida $P$ en dos regiones de un área determinada (por supuesto, no mayor que el área de $P$ ).

Supongamos que la línea es vertical (en caso contrario se puede girar el polígono o adaptar el algoritmo). Sea $p_1=q_1=(x_1,y_1)$ sea el vértice de $P$ que tiene la menor primera coordenada posible $x_1$ . A continuación, enumere los vértices superiores e inferiores a partir de $p_1$ aumentando la primera coordenada: $p_1,p_2,\dots$ son los superior parte de la frontera, $q_1,q_2,\dots$ son la parte inferior de la frontera. Ahora considere todas las líneas verticales que pasan a través de estos puntos y calcular la intersección con los bordes en el otro lateral del polígono. Por ejemplo, supongamos que entre $p_2$ y $q_2$ el punto que es más a la izquierda es $p_1$ . Entonces puedes encontrar un punto en el segmento $q_1 q_2$ tal que tenga la misma primera coordenada de $p_2$ . Sumando estos puntos, se puede suponer que los puntos $p_k$ y $q_k$ tienen el mismo $x$ -coordenada.

Ahora has subdividido tu polígono en una unión finita de trapecios con bases verticales. Encontrar el área de estos trapezoides es muy fácil. Por tanto, si quieres encontrar un corte con un área determinada, pasa a lo largo de estos trapezoides hasta que pases por el área objetivo. Entonces hay que dividir el último trapezoide con una línea vertical para obtener el área total correcta. De nuevo, esto es muy sencillo, ya que el área del trapecio es una función lineal de la línea vertical. $x$ coordenada de la línea de corte vertical.

adenda: Observe que el algoritmo, tal y como se describe, puede fallar si el polígono no es convexo.

Answer 2

Se puede cortar el polígono por la mitad triangulándolo con diagonales desde un vértice fijo, y luego encontrando el triángulo en el que el área a su izquierda es menor que la mitad del área total y el área a su derecha es mayor que la mitad del área total y finalmente computando el corte por la mitad desde el vértice fijo.

Así se obtienen dos polígonos convexos con la misma área. Ahora puedes aplicar uno de los algoritmos descritos en los artículos siguientes:

• I. Stojmenovic, Bisecciones y cortes en sándwich de polígonos y poliedros convexos , Cartas de tratamiento de la información , 38, 1 (1991) 15-21.

• B. Armbruster, Encontrar 2d cortes de bocadillo de jamón en tiempo lineal .

Para el primer paso, véase también

• Thomas C. Shermer, Algoritmo lineal para bisecar un polígono , Cartas de tratamiento de la información , 41, 3 (1992) 135-140.