8
\$\begingroup\$

The Challenge

Given an arbitrary amount of rectangles, output the total count of intersections of those when drawn in a 2D plane.

An intersection here is defined as a point P which is crossed by two lines which are orthogonal to each other and are both not ending in P.

Example

Each rectangle here is denoted by a 2-tuple with the coordinates of the upper left corner first and the coordinates of the bottom right corner second.

[(-8,6),(-4,-2)]
[(-4,9),(4,3)]
[(2,10),(14,4)]
[(1,7),(10,-6)]
[(7,4),(10,2)]
[(5,2),(9,-4)]
[(-6,-4),(-2,-6)]

enter image description here

Those rectangles create 6 intersections, which has to be your output.

  • As you can see in the image above, touching rectangles will not create intersections here and are not counted.
  • You can encode the rectagles in any format you want. Make it clear which format you use.
  • If multiple rectangles intersect at the same point, it only counts as one intersection.
  • The coordinates will always be integers.
  • There won't be any duplicate rectangles in the input.
  • You will always get at least one rectangle as input.
  • You may not use any builtins which solve this problem directly. Additionally you may not use builtins that solve equations. All other builtins are allowed.
  • The output has to be a single integer indicating the intersection count.

Rules

Test cases

Same format as in the example above. The rectangles are wrapped in a list.

[[(-8,6),(-4,-2)],[(-4,9),(4,3)],[(2,10),(14,4)],[(1,7),(10,-6)],[(7,4),(10,2)],[(5,2),(9,-4)],[(-6,-4),(-2,-6)]] -> 6
[[(-2,2),(6,-4)]] -> 0
[[(-12,10),(-8,6)],[(-14,6),(-10,2)],[(-10,6),(-6,2)]] -> 0
[[(-4,10),(6,2)],[(-2,8),(4,3)],[(1,6),(8,4)],[(2,11),(5,5)]] -> 10
[[(8,2),(12,-2)],[(10,0),(14,-4)]] -> 2
[[(0,2),(2,0)],[(0,1),(3,0)]] -> 1
[[(-10,-2),(-6,-6)],[(-6,-2),(-2,-6)],[(-8,-4),(-4,-8)]] -> 3

Happy Coding!

\$\endgroup\$
  • \$\begingroup\$ You need to define what it is that you want answers to count, as many points in the intersection of two or more rectangles are apparently ignored, according to the diagram. \$\endgroup\$ – feersum Mar 27 '16 at 21:38
  • 1
    \$\begingroup\$ So, [[(0,0),(1,2)],[(0,0),(2,1)]] would have 1 intersection? \$\endgroup\$ – Neil Mar 27 '16 at 21:39
  • \$\begingroup\$ @Neil Exactly. Gonna add this test case, thanks! \$\endgroup\$ – Denker Mar 27 '16 at 21:42
  • \$\begingroup\$ @feersum I think the diagram makes it pretty clear what to count and what not. But a formal definition wouldn't hurt I suppose, gonna add one. \$\endgroup\$ – Denker Mar 27 '16 at 21:43
  • 1
    \$\begingroup\$ If there are N pairs of rectangles that intersect at (x, y), is the point (x, y) counted once or N times? \$\endgroup\$ – feersum Mar 27 '16 at 22:43
2
\$\begingroup\$

JavaScript (ES6), 186 bytes

a=>a.map(([a,b,c,d])=>h.push([b,a,c],[d,a,c])&v.push([a,b,d],[c,b,d]),h=[],v=[])|h.map(([d,a,e])=>v.map(([c,f,b])=>a<c&c<e&b<d&d<f&t.every(([a,b])=>a-c|b-d)&&t.push([c,d])),t=[])|t.length

Splits each rectangle into its component lines, then intersects the horizontal and vertical lines, building up a list of intersections to avoid duplicates.

\$\endgroup\$
  • \$\begingroup\$ Which input format do you use? When I call this with the tastcases, I always get zero. \$\endgroup\$ – Denker Mar 28 '16 at 0:07
  • \$\begingroup\$ @DenkerAffe Sorry, I should have said, I expect an array of arrays of 4 elements e.g. [[-4,10,6,2],[-2,8,4,3],[1,6,8,4],[2,11,5,5]]. Since JavaScript doesn't have tuples, if you'd tried to use your examples literally you'd have triggered the comma operator instead, invalidating the input. \$\endgroup\$ – Neil Mar 28 '16 at 0:11
  • \$\begingroup\$ Alright, thanks. However, this gives 4 instead of 3 for the last testcase, since intersections of multiple rectangles only count as one intersection. I clarified this after you posted your answer I think, so this one goes on me. Hope its not too hard to fix this, sorry for the inconvenience. \$\endgroup\$ – Denker Mar 28 '16 at 0:18
  • \$\begingroup\$ @DenkerAffe I've updated it to work with your new spec. \$\endgroup\$ – Neil Mar 28 '16 at 10:53
0
\$\begingroup\$

Mathematica 138 bytes

Not finished! This works for all cases except [[(0,0),(1,2)],[(0,0),(2,1)]]


Length@Union[Join@@(Cases[RegionIntersection@@# &/@Subsets[Line[{{#,#2},{#3,#2},{#3,#4},{#,#4},{#,#2}}]&@@@Flatten/@#,{2}],Point@a__:> a])]

Example

Length@Union[
Join @@ (Cases[RegionIntersection @@ # & /@ Subsets[
Line[{{#, #2}, {#3, #2}, {#3, #4}, {#, #4}, {#, #2}}] & @@@ Flatten /@ #, {2}], 
Point@a__ :> a])] &@{{{-8, 6}, {-4, -2}}, {{-4, 9}, {4, 3}}, {{2, 10}, {14, 4}}, 
{{1, 7}, {10, -6}}, {{7, 4}, {10, 2}}, {{5, 2}, {9, -4}}, {{-6, -4}, {-2, -6}}}

6

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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