Considere un polígono potencialmente auto-intersectado, definido por una lista de vértices en el espacio 2D. P.ej
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
Hay varias formas de definir el área de dicho polígono, pero la más interesante es la regla par-impar. Tomando cualquier punto en el plano, dibuja una línea desde el punto hasta el infinito (en cualquier dirección). Si esa línea cruza el polígono un número impar de veces, el punto es parte del área del polígono, si cruza el polígono un número par de veces, el punto no es parte del polígono. Para el polígono de ejemplo anterior, aquí están tanto su contorno como su área par-impar:
El polígono no será en general ortogonal. Solo he elegido un ejemplo tan simple para que sea más fácil contar el área.
El área de este ejemplo es 17
(no 24
o 33
como podrían dar otras definiciones o áreas).
Tenga en cuenta que, según esta definición, el área del polígono es independiente de su orden de bobinado.
El reto
Dada una lista de vértices con coordenadas enteras que definen un polígono, determine su área bajo la regla par-impar.
Puede escribir una función o programa, tomando la entrada a través de STDIN o la alternativa más cercana, el argumento de la línea de comandos o el argumento de la función y devolver el resultado o imprimirlo en STDOUT o la alternativa más cercana.
Puede tomar la entrada en cualquier lista conveniente o formato de cadena, siempre que no esté preprocesada.
El resultado debe ser un número de coma flotante, con una precisión de 6 dígitos significativos (decimales), o un resultado racional cuya representación en coma flotante tenga una precisión de 6 dígitos significativos. (Si produce resultados racionales, es probable que sean exactos, pero no puedo requerir esto, ya que no tengo resultados exactos para referencia).
Debe poder resolver cada uno de los casos de prueba a continuación en 10 segundos en una máquina de escritorio razonable. (Hay un margen de maniobra en esta regla, así que use su mejor criterio. Si tarda 20 segundos en mi computadora portátil, le daré el beneficio de la duda, si tarda un minuto, no lo haré). Creo que este límite debería ser muy generoso, pero se supone que debe descartar enfoques en los que simplemente se discretiza el polígono en una cuadrícula lo suficientemente fina y se cuenta, o se utilizan enfoques probabilísticos como Monte Carlo. Sea un buen deportista y no intente optimizar estos enfoques de modo que pueda cumplir con el límite de tiempo de todos modos. ;)
No debe utilizar ninguna función existente relacionada directamente con polígonos.
Este es el código de golf, por lo que gana el envío más corto (en bytes).
Supuestos
- Todas las coordenadas son enteros en el rango
0 ≤ x ≤ 100
,0 ≤ y ≤ 100
. - Habrá al menos
3
y a lo sumo50
vértices. - No habrá vértices repetidos. Tampoco los vértices se encuentran en otro borde. (Sin embargo, puede haber puntos colineales en la lista).
Casos de prueba
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
17.0000
{{22, 87}, {6, 3}, {98, 77}, {20, 56}, {96, 52}, {79, 34}, {46, 78}, {52, 73}, {81, 85}, {90, 43}}
2788.39
{{90, 43}, {81, 85}, {52, 73}, {46, 78}, {79, 34}, {96, 52}, {20, 56}, {98, 77}, {6, 3}, {22, 87}}
2788.39
{{70, 33}, {53, 89}, {76, 35}, {14, 56}, {14, 47}, {59, 49}, {12, 32}, {22, 66}, {85, 2}, {2, 81},
{61, 39}, {1, 49}, {91, 62}, {67, 7}, {19, 55}, {47, 44}, {8, 24}, {46, 18}, {63, 64}, {23, 30}}
2037.98
{{42, 65}, {14, 59}, {97, 10}, {13, 1}, {2, 8}, {88, 80}, {24, 36}, {95, 94}, {18, 9}, {66, 64},
{91, 5}, {99, 25}, {6, 66}, {48, 55}, {83, 54}, {15, 65}, {10, 60}, {35, 86}, {44, 19}, {48, 43},
{47, 86}, {29, 5}, {15, 45}, {75, 41}, {9, 9}, {23, 100}, {22, 82}, {34, 21}, {7, 34}, {54, 83}}
3382.46
{{68, 35}, {43, 63}, {66, 98}, {60, 56}, {57, 44}, {90, 52}, {36, 26}, {23, 55}, {66, 1}, {25, 6},
{84, 65}, {38, 16}, {47, 31}, {44, 90}, {2, 30}, {87, 40}, {19, 51}, {75, 5}, {31, 94}, {85, 56},
{95, 81}, {79, 80}, {82, 45}, {95, 10}, {27, 15}, {18, 70}, {24, 6}, {12, 73}, {10, 31}, {4, 29},
{79, 93}, {45, 85}, {12, 10}, {89, 70}, {46, 5}, {56, 67}, {58, 59}, {92, 19}, {83, 49}, {22,77}}
3337.62
{{15, 22}, {71, 65}, {12, 35}, {30, 92}, {12, 92}, {97, 31}, {4, 32}, {39, 43}, {11, 40},
{20, 15}, {71, 100}, {84, 76}, {51, 98}, {35, 94}, {46, 54}, {89, 49}, {28, 35}, {65, 42},
{31, 41}, {48, 34}, {57, 46}, {14, 20}, {45, 28}, {82, 65}, {88, 78}, {55, 30}, {30, 27},
{26, 47}, {51, 93}, {9, 95}, {56, 82}, {86, 56}, {46, 28}, {62, 70}, {98, 10}, {3, 39},
{11, 34}, {17, 64}, {36, 42}, {52, 100}, {38, 11}, {83, 14}, {5, 17}, {72, 70}, {3, 97},
{8, 94}, {64, 60}, {47, 25}, {99, 26}, {99, 69}}
3514.46
fuente
upath
operador. (En realidad, es una conversión extremadamente simple de 1: 1 entre los separadores.}, {
Simplemente se conviertelineto
, y la coma entre x e y se elimina, y las llaves de apertura y cierre se reemplazan con un encabezado y pie de página estáticos ...)upath
ylineto
suena como si realmente estuvieras preprocesando la entrada. Es decir, no estás tomando una lista de coordenadas sino un polígono real.CrossingPolygon
.Respuestas:
Mathematica,
247225222Primero agregue los puntos de intersección al polígono, luego invierta algunos de los bordes, luego su área puede calcularse como un polígono simple.
Ejemplo:
fuente
{1,2},{4,4},{4,2},{2,4},{2,1},{5,3}
? Deberías salir con 3.433333333333309. Lo miré usando una lógica similar.103/30
, y el valor numérico es3.43333
.Python 2,
323319 bytesToma una lista de vértices a través de STDIN como números complejos, en el siguiente formulario
y escribe el resultado en STDOUT.
Mismo código después del reemplazo de la cadena y algo de espacio:
Explicación
Para cada punto de intersección de dos lados del polígono de entrada (incluidos los vértices), pase una línea vertical a través de ese punto.
(De hecho, debido al golf, el programa pasa unas pocas líneas más; en realidad no importa, siempre y cuando pasemos al menos estas líneas). El cuerpo del polígono entre dos líneas consecutivas está compuesto de trapecios verticales ( y triángulos, y segmentos de línea, como casos especiales de esos). Tiene que ser el caso, ya que si alguna de estas formas tuviera un vértice adicional entre las dos bases, habría otra línea vertical a través de ese punto, entre las dos líneas en cuestión. La suma de las áreas de todos esos trapecios es el área del polígono.
Así es como encontramos estos trapecios: para cada par de líneas verticales consecutivas, encontramos los segmentos de cada lado del polígono que (correctamente) se encuentran entre estas dos líneas (que podrían no existir para algunos de los lados). En la ilustración anterior, estos son los seis segmentos rojos, cuando se consideran las dos líneas verticales rojas. Tenga en cuenta que estos segmentos no se cruzan correctamente entre sí (es decir, solo pueden encontrarse en sus puntos finales, coincidir completamente o no cruzarse en absoluto, ya que, una vez más, si se cruzaran correctamente, habría otra línea vertical en el medio;) y tiene sentido hablar de ordenarlos de arriba a abajo, lo cual hacemos. De acuerdo con la regla par-impar, una vez que cruzamos el primer segmento, estamos dentro del polígono; una vez que cruzamos el segundo, estamos fuera; el tercero, de nuevo; el cuarto, fuera; y así...
En general, este es un algoritmo O ( n 3 log n ).
fuente
Haskell, 549
No parece que pueda jugar golf lo suficiente, pero el concepto era diferente a las otras dos respuestas, así que pensé que lo compartiría de todos modos. Realiza operaciones racionales O (N ^ 2) para calcular el área.
Ejemplo:
La idea es volver a cablear el polígono en cada cruce, lo que resulta en una unión de polígonos sin bordes de intersección. Luego podemos calcular el área (firmada) de cada uno de los polígonos usando la fórmula de cordones de Gauss ( http://en.wikipedia.org/wiki/Shoelace_formula ). La regla par-impar exige que cuando se convierte un cruce, el área del nuevo polígono se cuenta negativamente en relación con el antiguo polígono.
Por ejemplo, considere el polígono en la pregunta original. El cruce en la esquina superior izquierda se convierte en dos caminos que solo se encuentran en un punto; las dos rutas están orientadas en sentido horario, por lo que las áreas de cada una serían positivas a menos que declaremos que la ruta interna está ponderada por -1 en relación con la ruta externa. Esto es equivalente a la inversión de ruta de alfaalfa.
Como otro ejemplo, considere el polígono del comentario de MickyT:
Aquí, algunos de los polígonos están orientados en sentido horario y otros en sentido antihorario. La regla de signo de volteo al cruzar asegura que las regiones orientadas en sentido horario recojan un factor adicional de -1, lo que hace que contribuyan con una cantidad positiva al área.
Así es como funciona el programa:
fuente