Schnittpunkt zweier Dreiecke

19

A, B, C, DBerechnen Sie bei 4 Punkten auf den 2D-Ebenen die Fläche des Schnittbereichs der Dreiecke OABund OCD, wo Osich der Mittelpunkt der Ebene befindet, die Koordinate (0, 0).

Algorithmen, die in konstanter zeitlicher Komplexität (in Bezug auf arithmetische Operationen) ablaufen, werden empfohlen, aber nicht erzwungen.

Regeln

  • Jeder Punkt wird als zwei reelle Zahlen dargestellt und bezeichnet deren X- und Y-Koordinate.
    • Wenn Ihre Programmiersprache (oder eine Bibliothek Ihrer Programmiersprache) über einen integrierten PointTyp oder einen entsprechenden Typ verfügt, kann optional ein PointObjekt als Eingabe verwendet werden.
  • Die Eingabe erfolgt in Formaten mit 4 Punkten, einschließlich, aber nicht beschränkt auf:
    • Eine Liste von 8 Koordinaten.
    • Eine Liste von 4 Punkten, jeder Punkt kann in einem beliebigen Format dargestellt werden.
    • Zwei Listen mit 2 Punkten.
    • etc.
  • Sie können keine bestimmte Reihenfolge der Punkte annehmen (gegen den Uhrzeigersinn oder im Uhrzeigersinn)
  • Sie können nicht davon ausgehen, dass der Punkt Oals Eingabe übergeben wird. Mit anderen Worten, das Programm darf keine fremden Eingaben verwenden.
  • Sie können nicht davon ausgehen, dass alle Punkte unterschiedlich sind. Mit anderen Worten können die Dreiecke entartet sein. Sie müssen auch diesen Fall behandeln (siehe Testfälle unten)
  • Die absolute oder relative Differenz muss geringer sein als in den folgenden Beispieltestfällen.10-3

Gewinnkriterien

Dies ist , die kürzeste Antwort in Bytes zu gewinnen!

Beispiel-Testfälle

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

Hier sind die Ausgaben für die erste Testfallgruppe in exakter Form:

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

Abbildung für den Testfall 5 1 1 3 3 4 4 -3(die Fläche des grünen Vierecks ist die erwartete Ausgabe):

[ Bild]

user202729
quelle
Einer Ihrer Testfälle hat 9 Eingänge anstatt 8. 1.2 3.4 -0.3 4.2 5 3 7.6 -1.1 2.4 0
Kelly Lowder
1
@ KellyLowder behoben.
user202729

Antworten:

16

Wolfram Language (Mathematica) , 55 Byte

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

Probieren Sie es online!

Ein paar Bytes weniger als die einfache Antwort.

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

Durch Ersetzen Areamit DiscretizeRegionwird die Kreuzung angezeigt.

Bildbeschreibung hier eingeben

Dies funktioniert übrigens mit allen Simplexen, nicht nur mit Dreiecken.

-1 Byte dank JungHwan Min

@ user202729s Vorschlag fügte 4 Bytes hinzu, lässt es jedoch 0 für entartete Dreiecke ergeben

Kelly Lowder
quelle
1
Auch Simplex kann durch Polygon ersetzt werden
Kelly Lowder
1
Noch ein Byte: {{0,0}}bis {0{,}}(dies funktioniert, weil der Ausdruck ausgewertet wird {Times[0, {Null, Null}]})
JungHwan Min
Fehler für diesen Testfall , der in Beispieltestfällen aufgeführt ist.
user202729
Bereits bemerkt, dass dies nicht auf TIO funktioniert. Nicht sicher, was sie unter der Haube haben.
Kelly Lowder
1
Ich sehe, dass es für den Schnittpunkt zweier Linien nicht funktioniert. Mein schlechtes für das Überspringen dieses Testfalls. Technisch sind dies keine Dreiecke. Ich nehme an, wenn wir so technisch werden, sollten Sie vielleicht den Titel des Beitrags sowie den ersten Satz ändern. Wir könnten auch eine wirklich esoterische Diskussion darüber führen, ob der Bereich überhaupt für ein eindimensionales Objekt definiert ist, aber ich würde es lieber nicht tun.
Kelly Lowder
5

Python 2 + PIL, 341 318 313 284 270 Bytes

Besonderer Dank geht an Dennis, der dank Mr. Xcoder sofort PIL auf TIO
-23 Bytes hinzugefügt hat

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

Probieren Sie es online! oder Probieren Sie alle Testfälle aus

Um die Differenz zu berechnen, werden die Dreiecke buchstäblich gezeichnet und die Anzahl der Pixel überprüft, die in beiden Bildern gezeichnet werden.
Diese Methode hat einen Rundungsfehler eingefügt, der durch Erhöhen der Bildgröße verringert wird.

Erläuterung

#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
Stange
quelle