Intersección de dos triángulos.

19

Dados 4 puntos en los planos 2D A, B, C, D, calcule el área de la región de intersección de los triángulos OABy OCD, donde Oestá el centro del plano, teniendo coordenadas (0, 0).

Los algoritmos que se ejecutan en una complejidad de tiempo constante (en términos de operaciones aritméticas) son alentados, pero no forzados.

Reglas

  • Cada punto se representa como dos números reales, denota sus coordenadas X e Y.
    • Opcionalmente, si su lenguaje de programación (o alguna biblioteca de su lenguaje de programación) tiene un Pointtipo incorporado o equivalente, se le permite tomar el Pointobjeto como entrada.
  • La entrada se da como 4 puntos, en los formatos, que incluyen pero no se limitan a:
    • Una lista de 8 coordenadas.
    • Una lista de 4 puntos, cada punto se puede representar en cualquier formato conveniente.
    • Dos listas de 2 puntos.
    • etc.
  • No puede asumir un orden particular de los puntos (orden en sentido antihorario o en sentido horario)
  • No puede suponer que el punto Ose pasa como entrada. En otras palabras, el programa no debe tomar y usar entradas extrañas.
  • No puedes asumir que todos los puntos son diferentes. En otras palabras, los triángulos pueden estar degenerados. También debe manejar ese caso (ver casos de prueba a continuación)
  • La diferencia absoluta o relativa debe ser menor que para los casos de prueba de muestra a continuación.10-3

Criterios ganadores

Este es el , ¡la respuesta más corta en bytes gana!

Muestra de casos de prueba

Ax Ay Bx By Cx Cy Dx Dy area

5 1 1 3 -1 0 0 -1 0
5 1 1 3 -1 0 0 0 0
5 1 1 3 0 0 0 0 0
5 1 1 3 3 4 4 -3 4.50418
5 1 1 3 1 2 2 1 1.5
5 1 1 3 -2 5 4 -2 1.74829
5 1 1 3 -2 5 5 4 2.96154
5 1 1 3 3 5 5 4 1.88462
5 1 1 3 3 5 3 1 3.92308
5 1 1 3 3 5 4 -1 5.26619
5 1 1 3 5 1 4 -1 0
5 1 1 3 5 1 1 3 7
1 3 1 3 5 1 1 3 0
1 3 1 3 1 3 1 3 0
4 8 4 -1 -2 6 -2 -3 0

1.2 3.4 -0.3 4.2 5 7.6 -1.1 2.4 2.6210759326188535
3.1 0.6 0.1 7.2 5.2 0.7 0.9 8 9.018496993987977

Si alguien quiere, aquí están las salidas para el primer grupo de casos de prueba en forma exacta:

0
0
0
46375/10296
3/2
1792/1025
77/26
49/26
51/13
23345/4433
0
7
0
0
0

Imagen de ilustración para el caso de prueba 5 1 1 3 3 4 4 -3(el área del cuadrilátero verde es el resultado esperado):

[ Imagen]

usuario202729
fuente
Uno de sus casos de prueba tiene 9 entradas en lugar de 8. 1.2 3.4 -0.3 4.2 5 3 7.6 -1.1 2.4 0
Kelly Lowder
1
@KellyLowder fijo.
user202729

Respuestas:

16

Wolfram Language (Mathematica) , 55 bytes

0&@@Area@BooleanRegion[And,Simplex[{0{,}}~Join~#]&/@#]&

Pruébalo en línea!

Afeitó unos pocos bytes de la respuesta trivial.

%@{{{5, 1}, {1, 3}}, {{3, 4}, {4, -3}}} yields 46375/10296 or 4.504176379

Reemplazar Areacon DiscretizeRegionmostrará la intersección.

ingrese la descripción de la imagen aquí

Por cierto, esto funcionará con cualquier simplex, no solo con triángulos.

-1 Byte gracias a JungHwan Min

La sugerencia de @ user202729 agregó 4 bytes pero hace que produzca 0 para triángulos degenerados

Kelly Lowder
fuente
1
El polígono también se puede sustituir por Simplex
Kelly Lowder
1
Un byte más: {{0,0}}to {0{,}}(esto funciona porque la expresión se evalúa como {Times[0, {Null, Null}]})
JungHwan Min
Fallo para este caso de prueba , que se enumera en casos de prueba de muestra.
user202729
Ya noté que esto NO funciona en TIO. No estoy seguro de lo que tienen debajo del capó.
Kelly Lowder
1
Veo que no funciona para la intersección de dos líneas. Mi mal por saltarse ese caso de prueba. Técnicamente estos no son triángulos. Supongo que si vamos a obtener esa información técnica, tal vez deberías cambiar el título de la publicación y la primera oración. También podríamos tener una discusión realmente esotérica sobre si el área está incluso definida para un objeto unidimensional, pero prefiero no hacerlo.
Kelly Lowder
5

Python 2 + PIL, 341 318 313 284 270 bytes

Un agradecimiento especial a Dennis que rápidamente agregó PIL en TIO
-23 bytes gracias al Sr. Xcoder

import PIL.Image as I,PIL.ImageDraw as D
l=[i*1000for i in[0,0]+input()+[0,0]]
z=zip(*[[i-min(t)for i in t]for t in l[::2],l[1::2]])
print sum(map(int.__mul__,*map(lambda i,c:D.Draw(i).polygon(c,1)or i.getdata(),map(I.new,'11',[[max(l)-min(l)]*2]*2),[z[:3],z[3:]])))/1e6

Pruébalo en línea!o Pruebe todos los casos de prueba

Para calcular la diferencia, esto literalmente dibuja los triángulos y verifica la cantidad de píxeles pintados en ambas imágenes.
Este método insertó un error de redondeo, que se suaviza al aumentar el tamaño de la imagen.

Explicación

#the image/triangles are enlarged to increase the precision
#a pair of zeros are inserted in the start and at the end, this way "l" will have all 6 points to draw the triangles 
l=[i*1000for i in[0,0]+input()+[0,0]]
#split the input in x and y, where x=l[::2] and y=l[1::2]
#get the smallest number on each list, that will be "0" if there is no negative number, to be used as offset.
#this will be used to overcome the fact that PIL won't draw on negative coords
#zip "x" and "y" lists, to create a list containing the points
z=zip(*[[i-min(t)for i in t]for t in x,y])
#create 2 (B&W) blank images
#where the size is the difference between the smallest and the largest coord.
map(I.new,'11',[[max(l)-min(l)]*2]*2)
#draw both triangles and return the pixel list of each image
map(lambda i,c:D.Draw(i).polygon(c,1)or i.getdata(),<result of previous line>,[z[:3],z[3:]])
#count the amount of overlapping pixels by summing the color of each pixel, if the pixel is "1" in both images, then the triangles are overlapping, then the amount of pixels is divided by the initial enlarging factor squared (1e6)
print sum(map(int.__mul__,*<result of previous line>))/1e6
varilla
fuente