20
\$\begingroup\$

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 , 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]

\$\endgroup\$
2
  • \$\begingroup\$ 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 \$\endgroup\$ Dec 20, 2017 at 15:24
  • 1
    \$\begingroup\$ @KellyLowder Fixed. \$\endgroup\$
    – DELETE_ME
    Dec 21, 2017 at 0:52

2 Answers 2

17
\$\begingroup\$

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

\$\endgroup\$
10
  • 1
    \$\begingroup\$ Polygon can be substituted in for Simplex as well \$\endgroup\$ Dec 14, 2017 at 17:00
  • 1
    \$\begingroup\$ One more byte: {{0,0}} to {0{,}} (this works because the expression evaluates to {Times[0, {Null, Null}]} ) \$\endgroup\$ Dec 14, 2017 at 22:55
  • \$\begingroup\$ Fail for this test case, which is listed in sample test cases. \$\endgroup\$
    – DELETE_ME
    Dec 15, 2017 at 15:47
  • \$\begingroup\$ Already noted that this does NOT work on TIO. Not sure what they have under the hood. \$\endgroup\$ Dec 15, 2017 at 15:52
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Dec 15, 2017 at 16:16
5
\$\begingroup\$

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
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.