Intersection of two triangles

Question

Given 4 points on the 2D planes A, B, C, D, calculate the area of the intersection region of the triangles OAB and OCD, where O is the center of the plane, having coordinate (0, 0).

Algorithms that runs in constant time complexity (in terms of arithmetic operations) are encouraged, but not forced.

Rules

• Each point is represented as two real numbers, denotes their X and Y coordinate.
  • Optionally, if your programming language (or some library of your programming language) has built-in Point type or equivalent, it is allowed to take Point object as input.
• The input is given as 4 points, in the formats, including but not limited to:
  • A list of 8 coordinates.
  • A list of 4 points, each point can be represented in any convenient format.
  • Two lists of 2 points.
  • etc.
• You cannot assume particular ordering of the points (counter-clockwise order or clockwise order)
• You cannot assume that the point O is passed as input. In other word, program must not take and use extraneous input.
• You cannot assume all the points are different. In other words, the triangles may be degenerate. You need to also handle that case (see test cases below)
• The absolute or relative difference must be less than 10-3 for the sample test cases below.

Winning criteria

This is code-golf, the shortest answer in bytes win!

Sample test cases

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

If anyone want, here are the outputs for the first test case group in exact form:

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

Illustration image for test case 5 1 1 3 3 4 4 -3 (the area of the green quadrilateral is the expected output):

[Image]

• Kelly Lowder: One of your test cases has 9 inputs rather than 8. 1.2 3.4 -0.3 4.2 5 3 7.6 -1.1 2.4 0
• user202729: @KellyLowder Fixed.

Answer 1

Wolfram Language (Mathematica), 55 bytes

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

Try it online!

Shaved a few bytes off the trivial answer.

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

Replacing Area with DiscretizeRegion will show the intersection.

enter image description here

By the way, this will work with any simplexes, not just triangles.

-1 Byte thanks to JungHwan Min

@user202729's suggestion added 4 bytes but makes it yield 0 for degenerate triangles

• Kelly Lowder: Polygon can be substituted in for Simplex as well
• JungHwan Min: One more byte: {{0,0}} to {0{,}} (this works because the expression evaluates to {Times[0, {Null, Null}]} )
• user202729: Fail for this test case, which is listed in sample test cases.
• Kelly Lowder: Already noted that this does NOT work on TIO. Not sure what they have under the hood.
• Kelly Lowder: I see that it doesn't work for the intersection of two lines. My bad for skipping that test case. Technically these are not triangles. I suppose if we're going to get that technical, maybe you should change the title of the post as well as the first sentence. We could also have a really esoteric discussion about whether area is even defined for a one dimensional object, but I'd rather not.

Answer 2

Python 2 + PIL, (削除) 341 (削除ここまで) (削除) 318 (削除ここまで) (削除) 313 (削除ここまで) (削除) 284 (削除ここまで) 270 bytes

^{Special thanks to Dennis that promptly added PIL on TIO
-23 bytes thanks to Mr. 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

Try it online! or Try all test cases

To calculate the diference this literally draw the triangles and check the amount of pixels that are painted in both images.
This method inserted a rounding error, that is softened by increasing the image size.

Explanation

#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