Contar la cantidad de triángulos en una imagen es una tarea comúnmente utilizada en las pruebas cerebrales. Se le da una imagen que contiene formas que consisten en triángulos. Luego debes encontrar todos los triángulos posibles en la imagen.
Tarea
Se le proporciona una lista de líneas en el formato que elija. Luego debe generar una lista de triángulos encontrados en ese
Entrada
Se le da una lista de líneas, cada una dada por cuatro coordenadas enteras (p. Ej. x1 y1 x2 y2). Puede elegir el formato de entrada, siempre que esté claramente documentado. Ejemplos:
0 4 8 1
0 4 9 5
8 1 9 5
2 8 0 4
9 5 2 8
[[0, 4, 8, 1], [0, 4, 9, 5], [8, 1, 9, 5], [2, 8, 0, 4], [9, 5, 2, 8]]
Aquí está la misma entrada que una imagen:
Otro, con intersecciones (solo en un formato para ahorrar espacio):
[[2, 1, 5, 0], [2, 1, 2, 7], [5, 0, 6, 6], [5, 0, 2, 7], [6, 6, 2, 1], [2, 7, 6, 6]]
Salida
Debe generar una lista de todos los triángulos, cada uno dado por seis coordenadas de punto flotante (p. Ej. x1 y1 x2 y2 x3 y3), En la imagen especificada por la entrada. Estos pueden no ser enteros, ya que las líneas pueden cruzarse en cualquier punto. Puede elegir el formato de salida, siempre que esté claramente documentado. Salidas de ejemplo para las entradas de ejemplo anteriores:
0 4 8 1 9 5
0 4 9 5 2 8
[[0, 4, 8, 3, 9, 5], [0, 4, 9, 5, 2, 8]]
[[2, 1, 5, 0, 2, 7], [2, 1, 5, 0, 6, 6], [5, 0, 6, 6, 2, 7], [2, 1, 6, 6, 2, 7], [2, 1, 5, 0, 3.674, 3.093], [5, 0, 6, 6, 3.674, 3.093], [6, 6, 2, 7, 3.674, 3.093], [2, 7, 2, 1, 3.674, 3.093]]
Puedes suponer que
no hay casos de borde donde una línea cruza una intersección pero no hay líneas, como
[[0, 9, 1, 8], [1, 8, 2, 9], [2, 9, 3, 8], [3, 8, 4, 9], [4, 9, 0, 9]]no hay ángulos superiores a 179 grados, como
[[0, 0, 0, 1], [0, 1, 0, 2], [0, 2, 0, 0]]
Reglas
- Puede usar cualquier idioma que desee.
- No se deben utilizar recursos externos.
- Se aplican lagunas estándar .
Puntuación
Este es el código de golf , por lo que gana la respuesta más corta en bytes .
[0,9],[1,8],[2,9],[3,8],[4,9]es en realidad una W con una línea dibujada en la parte superior. ¿No hay triángulos o 2 triángulos?[0,0],[1,0],[2,0],[1,2]Un "cuadrilátero" con un ángulo de 180 grados. ¿Sin triángulos o 1 triángulo?Respuestas:
PostGIS, 162
Creo que esto cumple con las reglas, es una consulta para PostGIS, que es una extensión de PostgreSQL. Se supone que la entrada es una tabla de coordenadas para cada línea llamada L La salida es un conjunto de filas con la definición de polígono para los triángulos formados.
En uso se parece a lo siguiente
La salida es la siguiente
fuente
Mathematica
915 395 401405Actualizar
Este desafío de programación es mucho más difícil de lo que parece ser.
El enfoque actual funciona con casos simples, donde hay una sola intersección a lo largo de cualquier segmento de línea. Con múltiples cruces a lo largo de un segmento, es necesario realizar un seguimiento de todos los puntos de intersección a lo largo de cada línea y crear nuevos subsegmentos (por lo tanto, bordes de gráficos adicionales) que conectan la nueva intersección a todos los puntos de intersección a lo largo de la línea de destino.
A pesar de esa limitación, puede valer la pena compartir la lógica subyacente al enfoque actual.
Los segmentos de línea de entrada se tratan como regiones. Si se cruzan, el centroide será las coordenadas de la intersección. Necesitamos eliminar esas intersecciones que ocurren en los vértices de los segmentos de línea. Las líneas que no se cruzan tendrán un centroide indeterminado.
Se crean cuatro aristas nuevas para cada punto de intersección. Conectan el punto de intersección con los cuatro vértices de las dos líneas de intersección.
Se genera un gráfico como el de abajo a la derecha utilizando los bordes antiguos y nuevos.
Los vértices son las coordenadas de los puntos respectivos. Los ciclos, es decir, los bucles cerrados de tres vértices serán triángulos siempre que los tres vértices no sean colineales.
Actualmente verificamos si algún "triángulo" tiene un área indeterminada. (Por alguna razón, no devuelve un área de 0 para tres puntos colineales).
Un simple ejemplo
A continuación se presentan (a) la figura trazada en el plano de coordenadas y (b) el gráfico que muestra los nodos dados, así como el nodo de intersección,
{114/23, 314/69}. En este último, los vértices no se encuentran en las coordenadas cartesianas respectivas.Puede parecer que hay más aristas en la figura derecha que en la izquierda. Pero recuerde que hay bordes de gráfico superpuestos a la izquierda. ¡Cada diagonal corresponde en realidad a 3 bordes del gráfico!
Cada fila de abajo es un triángulo.
Un ejemplo mas complejo
Aquí está el gráfico correspondiente a las coordenadas de entrada . Los vértices están en sus coordenadas cartesianas esperadas. (Si ejecuta el código de golf, mostrará los vértices en otro lugar mientras respeta las etiquetas y los bordes de los vértices. Para facilitar la lectura, asigné las coordenadas de los vértices usando un puñado de código adicional, que no es necesario para la solución).
Aquí está el gráfico derivado.
Incluye el punto de intersección derivado
(0,1/11), donde se cruzan algunas de las líneas de entrada.El código encontró 19 triángulos. Nueve de ellos tienen el punto,
(0,1/11)como uno de los vértices.fuente
Java,
10511004(Programa totalmente funcional)
Pensé que este es un buen desafío, no solo para jugar golf, sino principalmente para practicar escribir funciones matemáticas.
Y para dibujar una "línea de base" hice esta en Java * Espera a que todos comiencen a reír * .
Código
Entrada
Enteros separados por espacios. En pares de 4 (x1, y1, x2, y2)
Salida (la salida real no se redondea a 3 decimales)
Cada línea contiene un triángulo Cada línea consta de puntos flotantes separados por espacios en pares de 2 (x1, y1, x2, y2, x3, y3). (Nota: el orden de los 3 puntos que forman el triángulo no está definido).
Explicación
Comencé a escribir un método para encontrar la intersección entre dos líneas no infinitas. El método resultante es para un estilo Java bastante corto (246). En lugar de permitir que el método de entrada consista en 8 dobles o dos Puntos (P), elijo usar un parámetro arbitrario para proteger cantidades masivas de caracteres. Para minimizar el uso del operador de matriz, cada parámetro utilizado más de 2 veces se coloca en su propia variable.
Se agregará más explicación ... (esta respuesta probablemente se pueda jugar aún más)
fuente
BBC BASIC
Emulador en http://www.bbcbasic.co.uk/bbcwin/bbcwin.html
Espero que esto llegue a los 400's.
De entrada y salida
Cada vez que el usuario ingresa una nueva línea, el programa verifica si se han creado nuevos triángulos y los emite de inmediato, ver más abajo.
Se crea un nuevo triángulo donde la nueva línea se cruza con dos líneas preexistentes que también se cruzan entre sí (excepto cuando las tres líneas se cruzan en un punto, que es un caso especial que debe tratarse).
Código
El programa principal es tan simple como puede ser. Al final está la función, que realiza la compleja tarea de detectar intersecciones, de acuerdo con la fórmula en http://en.wikipedia.org/wiki/Line%E2%80%93line_intersection
La función devuelve cero si no hay intersección y un número de coma flotante distinto de cero si la hay. También tiene un efecto secundario: las coordenadas de la intersección se agregan a la cadena z $. Además, en BBC basic, las variables de una función son visibles para el programa principal siempre que el programa principal no tenga una variable del mismo nombre (incluso después de que la función haya finalizado).
Por lo tanto, el programa principal tiene acceso a las variables
xyy, ymyn, que almacenan las coordenadas de las intersecciones actuales y anteriores. Esto se usa para detectar si realmente hemos encontrado un triángulo y no solo tres líneas que se cruzan en un punto.fuente