Find our neighbors

Question

You live in a rectangular neighborhood which is completely partitioned into N rectangular plots, i.e. there are no gaps or overlaps. Plots do not necessarily have the same width/height as other plots. All widths/heights are positive integers. Your goal is to output all shared edges between plots.

Inputs

The input may come from any source desired (stdio, file, function parameters, etc.). The input is a list-like sequence of rectangles. Inputs for rectangles may be any form desired, for example (min_x, max_x, min_y, max_y), (min_x, min_y, width, height), (min_x, min_y, max_x, max_y), etc.

The neighborhood is bounded by min_x = 0 and min_y = 0. You may assume max_x and max_y of the neighborhood both fit in your language's native integer type.

You may flatten the input data into a 1D sequence if desired.

The id of a plot is a sequentially incremented integer based on the order of input, where the first plot may have any id desired.

Outputs

The output may be to any desired target (stdio, file, return value, output parameter, etc.).

The output is a list of lists of neighbors for each plot. A neighbor is defined as the id of the neighboring plot and the min/max bounds of the shared corner/edge. Shared corners/edges with the corner/edge of the neighborhood are not considered a neighbor relation and should not be outputted.

When printing out make some distinction between each list, for example using a newline to separate the neighbors of plot i from the neighbors of plot i+1.

The order of the neighbors of plot i is not important.

Example Test Cases

All listed test case inputs are of the format min_x, max_x, min_y, max_y and plot IDs start with 0. Outputs are formatted as (id, min_x, max_x, min_y, max_y).

Input:

0, 1, 0, 1

Output:

no output, empty list, list containing a single empty list, or anything similar such as null

Input:

0, 1, 0, 1
0, 1, 1, 2

Output:

(1, 0, 1, 1, 1)
(0, 0, 1, 1, 1)

Input:

0, 2, 1, 2
0, 2, 0, 1

Output:

(1, 0, 2, 1, 1)
(0, 0, 2, 1, 1)

Input:

0, 1, 0, 1
0, 1, 1, 2
0, 1, 2, 3

Output:

Regions with no neighbor relationships may be omitted.

(1, 0, 1, 1, 1)
(0, 0, 1, 1, 1), (2, 0, 1, 2, 2)
(1, 0, 1, 2, 2)

It is also ok to output the id of the other region with some indication of "no shared boundary".

(1, 0, 1, 1, 1), (2)
(0, 0, 1, 1, 1), (2, 0, 1, 2, 2)
(1, 0, 1, 2, 2), (0, falsy)

Input:

0, 1, 0, 1
0, 1, 1, 2
1, 2, 0, 2

Output:

(1, 0, 1, 1, 1), (2, 1, 1, 0, 1)
(0, 0, 1, 1, 1), (2, 1, 1, 1, 2)
(0, 1, 1, 0, 1), (1, 1, 1, 1, 2)

One possible alternative output (switched order of neighbors for plot 0):

(2, 1, 1, 0, 1), (1, 0, 1, 1, 1)
(0, 0, 1, 1, 1), (2, 1, 1, 1, 2)
(0, 1, 1, 0, 1), (1, 1, 1, 1, 2)

Input:

You may have corner neighbors.

0, 1, 0, 1
0, 1, 1, 2
1, 2, 0, 1
1, 2, 1, 2

Output:

(1, 0, 1, 1, 1), (2, 1, 1, 0, 1), (3, 1, 1, 1, 1)
(0, 0, 1, 1, 1), (2, 1, 1, 1, 1), (3, 1, 1, 1, 2)
(0, 1, 1, 0, 1), (1, 1, 1, 1, 1), (3, 1, 2, 1, 1)
(0, 1, 1, 1, 1), (1, 1, 1, 1, 2), (2, 1, 2, 1, 1)

Scoring

This is code golf; shortest code wins.

edit clarification that corner neighbors should be outputted as well. Also clarified that if two regions don't share any corners/edges the relation may be completely omitted, or a relation with a falsy edge bounds may be outputted. Both have test cases added.

Answer 1

Mathematica, 179 171 bytes

If[Depth@#2>2,Flatten/@(Thread@{##}/.Line->List)]&~MapThread~{Range@Length@#~Subsets~{2}-1,RegionIntersection/@Subsets[Line@{{##3},{#,#4},{#,#2},{#3,#2},{##3}}&@@@#,{2}]}&

---

Test cases

Inputs and outputs are list of elements in form {x1, y1, x2, y2}.

%[{{0, 0, 1, 1}, {0, 1, 1, 2}, {1, 0, 2, 2}}]
(*
   {{{0, 0, 1, 1, 1}, {1, 0, 1, 1, 1}},
    {{0, 1, 0, 1, 1}, {2, 1, 0, 1, 1}},
    {{1, 1, 1, 1, 2}, {2, 1, 1, 1, 2}}}
 *)

Answer 2

Mathematica 123 134 bytes

g@d_:=Subsets[MapIndexed[List,Apply[Rectangle,d,1]],{2}]/.{{a_,{i_Integer}},
{b_,{j_}}}:>{{i-1,r=RegionIntersection[a,b][[1]]},{j-1,r}}

---

I prefer this version, at 123 bytes, which returns graphics objects instead of mere coordinates. It also avoids redundancy, using by MartinBüttner's suggestion, by listing two rectangle numbers followed by a Line[{{x1,y1},{x2,y2}}] in the case of a shared edge, and Point[{x,y}] in the case of a shared corner.

f@d_:=Subsets[MapIndexed[List,Apply[Rectangle,d,1]],{2}]/.
{{a_,{i_Integer}},{b_,{j_}}}:>{{i,j}-1,r=RegionIntersection[a,b]}

---

f[{{{0, 0}, {1, 1}}}]

{}

---

f[{{{0, 0}, {1, 1}}, {{0, 1}, {1, 2}}}]

{{{0, 1}, Line[{{0, 1}, {1, 1}}]}}

---

f[{{{0, 1}, {1, 2}}, {{0, 0}, {2, 1}}}]

{{{0, 1}, Line[{{0, 1}, {1, 1}}]}}

---

Shared edges, corners, areas, formatted to a grid for clarity.

f[{{{0, 0}, {1, 1}}, {{0, 1}, {1, 2}}, {{.5, .5}, {1.3, 1.5}}, {{1, 
 0}, {2, 1}}, {{1, 1}, {2, 2}}}] // Grid

Answer 3

Python, 189 characters

for p in i:
    for q in i:
        for t in 0,2:
            v,a,b=p[3-t],min(p[1+t],q[1+t]),max(p[t],q[t])
            w,z=[v,v],[b,a]
            if v==q[2-t]and a>b:
                for d in p,q:
                    print[i.index(d)]+(w+z,z+w)[t/2]

The input is given as a list like

i = [[0, 1, 0, 1], [0, 1, 1, 2], [1, 2, 0, 2]]

Answer 4

JavaScript (ES6), 228

Input / output as an array of arrays. Format as in OP testcases:

• inputs min_x, max_x, min_y, max_y.
• outputs id (0 based), min_x, max_x, min_y, max_y.

l=>l.map(([x,r,y,s],i)=>l.map(([t,v,u,w],j)=>i-j&&(n=x-t&&x-v,m=r-t&&r-v,u>=s|w<=y||n&&m||q.push([j,z=m?x:r,z,y>u?y:u,s<w?s:w]),n=y-u&&y-w,m=s-u&&s-w,t>=r|v<=x||n&&m||q.push([j,x>t?x:t,r<v?r:v,z=m?y:s,z])),o.push(q=[])),o=[])&&o

This can probably be shortened merging the horizontal and vertical check

TEST

f=l=>
  l.map(([x,r,y,s],i)=>
    l.map(([t,v,u,w],j)=>
      i-j&&(
        n=x-t&&x-v,m=r-t&&r-v,u>=s|w<=y||n&&m||q.push([j,z=m?x:r,z,y>u?y:u,s<w?s:w]), // vertical
        n=y-u&&y-w,m=s-u&&s-w,t>=r|v<=x||n&&m||q.push([j,x>t?x:t,r<v?r:v,z=m?y:s,z])  // horizontal
      )
    ,o.push(q=[]))  
  ,o=[])&&o  

ArToStr=(a,s)=>a.map?(s?'[':'[\n ')+a.map(x=>ArToStr(x,1)).join(s?',':',\n ')+(s?']':'\n]\n'):a

console.log=x=>O.textContent+=x+'\n';

console.log(ArToStr(f([[0,1,0,1]])))
console.log(ArToStr(f([[0,1,0,1],[0,1,1,2]])))
console.log(ArToStr(f([[0, 2, 1, 2],[0, 2, 0, 1]])))
console.log(ArToStr(f([[0, 1, 0, 1],[0, 1, 1, 2],[1, 2, 0, 2]])))

<pre id=O></pre>