Vertexes on the contour formed by n rectangles

This is Manila. I met my best friends :)

1. Introduction

In this article, I consider a simple program outputting vertexes on the contour formed by n rectangles.

The locations and height of n rectangles are given like Figure 1, 2, 3.
It is guaranteed that 2 ≤ n ≤ Max of Integers.

I assumed the following as for vertex information.

[Assumption]
1. I suppose that the vertex information of each rectangles is represented by array of integers [lx, rx, ly, ry], [lx', rx', ly', ry'], ... .

2. It is guaranteed that 0 ≤ lx < rx ≤ Max of Integer and 0 ≤ ly < hy ≤ Max of Integer.

2. Program

2.1. Input

And as for a program input, I supposed the following list.

[Input]
{(lx, rx, ly, hy), (lx', rx', Lly', hy'), ...}

2.2. Output

As for a program output, I suppose to output the list of vertexes on the contour formed by these rectangles like Figure 1', 2', 3'.

[Output]
Figure1: {(lx,ly), (rx,ly), (rx,ly'), (rx',ly'), (lx,hy), (lx',hy), (lx',hy'), (rx',hy')}
Figure2: {(lx,ly), (lx',ly), (lx',ly'), (rx',ly'), (lx,hy), (rx,hy), (rx,hy'), (rx',hy')}

Figure3: {(lx,ly), (rx',ly'), (lx,ly), (rx',ly')}

2.3. Implementation

For example, I can simply implement as follows.

Main.java

package org.inut;

import java.util.*;

class Main {
  int lx = 0;
  int rx = 0;
  int ly = 0;
  int hy = 0;

  public List<List<Integer>> seekVertexes(List<List<Integer>> input, List<List<Integer>> outputLowerSide, List<List<Integer>> outputUpperSide) {
    for (List<Integer> list : input) {
      int newLx = list.get(0);
      int newRx = list.get(1);
      int newLy = list.get(2);
      int newHy = list.get(3);

      // seek vertexes on the lower side
      if (ly != newLy) {
        if (outputLowerSide.isEmpty()) {
          outputLowerSide.add(new ArrayList<Integer>() {{add(newLx); add(newLy); }});
          lx = newLx;
          ly = newLy;
        } else {
          if (ly < newLy) {
            outputLowerSide.add(new ArrayList<Integer>() {{ add(rx); add(ly); }});
            outputLowerSide.add(new ArrayList<Integer>() {{ add(rx); add(newLy); }});
          } else if (ly > newLy) {
            outputLowerSide.add(new ArrayList<Integer>() {{ add(newLx); add(ly); }});
            outputLowerSide.add(new ArrayList<Integer>() {{ add(newLx); add(newLy); }});
          }

          lx = newLx;
          ly = newLy;
        }
      }

      // seek vertexes on the upper side
      if (hy != newHy) {
        if (outputUpperSide.isEmpty()) {
          outputUpperSide.add(new ArrayList<Integer>() {{add(newLx); add(newHy); }});
          lx = newLx;
          hy = newHy;
        } else {
           if (hy > newHy) {
             outputUpperSide.add(new ArrayList<Integer>() {{ add(rx); add(hy); }});
             outputUpperSide.add(new ArrayList<Integer>() {{ add(rx); add(newHy); }});
           } else if (hy < newHy) {
             outputUpperSide.add(new ArrayList<Integer>() {{ add(newLx); add(hy); }});
             outputUpperSide.add(new ArrayList<Integer>() {{ add(newLx); add(newHy); }});
           }

            lx = newLx;
            hy = newHy;
        }
      }

      rx = newRx;
    }

    outputLowerSide.add(new ArrayList<Integer>() {{add(rx); add(ly); }});
    outputUpperSide.add(new ArrayList<Integer>() {{add(rx); add(hy); }});

    List<List<Integer>> result = new ArrayList<>();
    result.addAll(outputLowerSide);
    result.addAll(outputUpperSide);

    return result;

  }

  public static void main(String args[]) {
    List<List<Integer>> input = new ArrayList<>();
    input.add(Arrays.asList(1,3,1,3));
    input.add(Arrays.asList(2,5,2,5));
    input.add(Arrays.asList(4,7,1,4));

    List<List<Integer>> outputLowerSide = new ArrayList<>();
    List<List<Integer>> outputUpperSide = new ArrayList<>();
    List<List<Integer>> result = new Main().seekVertexes(input, outputLowerSide, outputUpperSide);

    for (List<Integer> elm : result) {
      System.out.println(elm);
    }
  }
}

3. Sort and Performance

This program will work well.

However, if sort is needed and n is large number, I want to come to use some sort algorithm to get the good performance. For example, it's a merge sort algorithm :)