Calculate the area of rectangles union











up vote
13
down vote

favorite
2












I've been given the following task:




Given N rectangles with edges parallel to axis, calculate the area of the union of all rectangles. The input and output are files specified in program arguments. Input is represented by N lines with 4 numbers separated by spaces, defining 2 opposite vertices of the rectangle. Output file should contain 1 number - the resulting area of the rectangles' union.




Additional constraints:




  • $1 le N le 100$

  • $-10000 le x1$, $y1$, $x2$, $y2 le 10000$

  • Memory consumption < 16 MB

  • Program parameters should be validated

  • Input file format should be validated.


Examples:



Input:



1 1 7 7


Output:



36


Input:



1 1 3 3  
2 2 4 4


Output:



7


My solution:



public class Main {

private List<Rectangle> rectangles = new ArrayList<>();

public static void main(String args) {
if (args.length != 2) {
throw new IllegalArgumentException("Invalid arguments numbernProgram usage: java Main input output");
}

Main computer = new Main();
long area = computer.computeAreaFromFile(args[0]);
computer.writeAreaToFile(area, args[1]);
}

public long computeAreaFromFile(String inputFileName) {
rectangles.clear();

String line;
try (BufferedReader inputFileReader = new BufferedReader(new FileReader(inputFileName))) {
long area = 0;

while ((line = inputFileReader.readLine()) != null) {
Rectangle rectangle = Rectangle.fromString(line);
area += addRectangleArea(rectangle, false);
}

return area;
} catch (FileNotFoundException e) {
throw new IllegalArgumentException("Input file not found");
} catch (IOException e) {
throw new RuntimeException(e);
} catch (NumberFormatException | IndexOutOfBoundsException e) {
throw new IllegalArgumentException("Input file contains incorrect line");
}
}

private int addRectangleArea(Rectangle newRectangle, boolean isIntersection) {
int result = 0;

boolean hasIntersections = false;

for (Rectangle existingRectangle : rectangles) {
if (!existingRectangle.contains(newRectangle)) {
List<Rectangle> complements = existingRectangle.complementOf(newRectangle);
if (complements.size() > 0) {
hasIntersections = true;

for (Rectangle complement : complements) {
result += addRectangleArea(complement, true);
}

break;
}
}
}

if (!hasIntersections) {
result += newRectangle.area();
}

if (!isIntersection) {
rectangles.add(newRectangle);
}

return result;
}

private void writeAreaToFile(long area, String outputFileName) {
try (BufferedWriter writer = new BufferedWriter(new FileWriter(outputFileName))) {
writer.write(String.valueOf(area));
} catch (IOException e) {
throw new RuntimeException("Could not open file " + outputFileName);
}
}
}

class Rectangle {
public final int x1;
public final int y1;
public final int x2;
public final int y2;

public static Rectangle fromString(String input) throws NumberFormatException, IndexOutOfBoundsException {
String splitInput = input.split(" ");

if (splitInput.length != 4) {
throw new IndexOutOfBoundsException();
}

return new Rectangle(Integer.valueOf(splitInput[0]),
Integer.valueOf(splitInput[1]),
Integer.valueOf(splitInput[2]),
Integer.valueOf(splitInput[3]));
}

public Rectangle(int x1, int y1, int x2, int y2) {
this.x1 = Math.min(x1, x2);
this.y1 = Math.min(y1, y2);
this.x2 = Math.max(x1, x2);
this.y2 = Math.max(y1, y2);
}

/**
* Finds a relative complement of the specified rectangle.
*
* @param rectangle rectangle to find a complement of.
* @return {@link List} of the rectangles forming the resulting complement.
*/
public List<Rectangle> complementOf(Rectangle rectangle) {
List<Rectangle> intersections = new ArrayList<>();

if (rectangle.x2 > x1 && x2 > rectangle.x1 && rectangle.y2 > y1 && y2 > rectangle.y1) {
if (rectangle.y1 <= y1) {
intersections.add(new Rectangle(rectangle.x1, rectangle.y1, rectangle.x2, y1));
}

if (y2 <= rectangle.y2) {
intersections.add(new Rectangle(rectangle.x1, y2, rectangle.x2, rectangle.y2));
}

if (rectangle.x1 <= x1) {
intersections.add(new Rectangle(rectangle.x1, Math.max(y1, rectangle.y1), x1, Math.min(y2, rectangle.y2)));
}

if (x2 <= rectangle.x2) {
intersections.add(new Rectangle(x2, Math.max(y1, rectangle.y1), rectangle.x2, Math.min(y2, rectangle.y2)));
}
}

return intersections;
}

/**
* Calculates area of this rectangle.
*
* @return area of this rectangle.
*/
public int area() {
return Math.abs((x1 - x2) * (y1 - y2));
}

/**
* Checks if this rectangle contains the specified rectangle.
*
* @param rectangle rectangle to check for.
* @return true if rectangle inside this, false otherwise.
*/
public boolean contains(Rectangle rectangle) {
return x1 <= rectangle.x1 && rectangle.x2 <= x2 && y1 <= rectangle.y1 && rectangle.y2 <= y2;
}

@Override
public boolean equals(Object o) {
if (!(o instanceof Rectangle)) {
return false;
}

Rectangle other = (Rectangle) o;
return x1 == other.x1 && y1 == other.y1 && x2 == other.x2 && y2 == other.y2;
}

@Override
public int hashCode() {
int result = 17;

result = 37 * result + x1;
result = 37 * result + y1;
result = 37 * result + x2;
result = 37 * result + y2;

return result;
}

@Override
public String toString() {
return String.format("Rectangle with x1: %s y1: %s x2: %s y2: %s", x1, y1, x2, y2);
}
}


I have several questions/considerations:




  1. Is the provided solution correct?

  2. I assume the complexity of this algorithm is $O(n^2)$. Can it be improved?

  3. I've overridden toString(), equals() and hashCode() methods, although I've never called them (except toString() while debugging). Is it bad practise to do so?

  4. I feel that comments in javadoc are lame. How can they be improved and are they necessary at all?


  5. computeAreaFromFile() does 2 things: it reads file content and performs actual calculations. I think this method should be split, however I'm not sure how I could do this.










share|improve this question




























    up vote
    13
    down vote

    favorite
    2












    I've been given the following task:




    Given N rectangles with edges parallel to axis, calculate the area of the union of all rectangles. The input and output are files specified in program arguments. Input is represented by N lines with 4 numbers separated by spaces, defining 2 opposite vertices of the rectangle. Output file should contain 1 number - the resulting area of the rectangles' union.




    Additional constraints:




    • $1 le N le 100$

    • $-10000 le x1$, $y1$, $x2$, $y2 le 10000$

    • Memory consumption < 16 MB

    • Program parameters should be validated

    • Input file format should be validated.


    Examples:



    Input:



    1 1 7 7


    Output:



    36


    Input:



    1 1 3 3  
    2 2 4 4


    Output:



    7


    My solution:



    public class Main {

    private List<Rectangle> rectangles = new ArrayList<>();

    public static void main(String args) {
    if (args.length != 2) {
    throw new IllegalArgumentException("Invalid arguments numbernProgram usage: java Main input output");
    }

    Main computer = new Main();
    long area = computer.computeAreaFromFile(args[0]);
    computer.writeAreaToFile(area, args[1]);
    }

    public long computeAreaFromFile(String inputFileName) {
    rectangles.clear();

    String line;
    try (BufferedReader inputFileReader = new BufferedReader(new FileReader(inputFileName))) {
    long area = 0;

    while ((line = inputFileReader.readLine()) != null) {
    Rectangle rectangle = Rectangle.fromString(line);
    area += addRectangleArea(rectangle, false);
    }

    return area;
    } catch (FileNotFoundException e) {
    throw new IllegalArgumentException("Input file not found");
    } catch (IOException e) {
    throw new RuntimeException(e);
    } catch (NumberFormatException | IndexOutOfBoundsException e) {
    throw new IllegalArgumentException("Input file contains incorrect line");
    }
    }

    private int addRectangleArea(Rectangle newRectangle, boolean isIntersection) {
    int result = 0;

    boolean hasIntersections = false;

    for (Rectangle existingRectangle : rectangles) {
    if (!existingRectangle.contains(newRectangle)) {
    List<Rectangle> complements = existingRectangle.complementOf(newRectangle);
    if (complements.size() > 0) {
    hasIntersections = true;

    for (Rectangle complement : complements) {
    result += addRectangleArea(complement, true);
    }

    break;
    }
    }
    }

    if (!hasIntersections) {
    result += newRectangle.area();
    }

    if (!isIntersection) {
    rectangles.add(newRectangle);
    }

    return result;
    }

    private void writeAreaToFile(long area, String outputFileName) {
    try (BufferedWriter writer = new BufferedWriter(new FileWriter(outputFileName))) {
    writer.write(String.valueOf(area));
    } catch (IOException e) {
    throw new RuntimeException("Could not open file " + outputFileName);
    }
    }
    }

    class Rectangle {
    public final int x1;
    public final int y1;
    public final int x2;
    public final int y2;

    public static Rectangle fromString(String input) throws NumberFormatException, IndexOutOfBoundsException {
    String splitInput = input.split(" ");

    if (splitInput.length != 4) {
    throw new IndexOutOfBoundsException();
    }

    return new Rectangle(Integer.valueOf(splitInput[0]),
    Integer.valueOf(splitInput[1]),
    Integer.valueOf(splitInput[2]),
    Integer.valueOf(splitInput[3]));
    }

    public Rectangle(int x1, int y1, int x2, int y2) {
    this.x1 = Math.min(x1, x2);
    this.y1 = Math.min(y1, y2);
    this.x2 = Math.max(x1, x2);
    this.y2 = Math.max(y1, y2);
    }

    /**
    * Finds a relative complement of the specified rectangle.
    *
    * @param rectangle rectangle to find a complement of.
    * @return {@link List} of the rectangles forming the resulting complement.
    */
    public List<Rectangle> complementOf(Rectangle rectangle) {
    List<Rectangle> intersections = new ArrayList<>();

    if (rectangle.x2 > x1 && x2 > rectangle.x1 && rectangle.y2 > y1 && y2 > rectangle.y1) {
    if (rectangle.y1 <= y1) {
    intersections.add(new Rectangle(rectangle.x1, rectangle.y1, rectangle.x2, y1));
    }

    if (y2 <= rectangle.y2) {
    intersections.add(new Rectangle(rectangle.x1, y2, rectangle.x2, rectangle.y2));
    }

    if (rectangle.x1 <= x1) {
    intersections.add(new Rectangle(rectangle.x1, Math.max(y1, rectangle.y1), x1, Math.min(y2, rectangle.y2)));
    }

    if (x2 <= rectangle.x2) {
    intersections.add(new Rectangle(x2, Math.max(y1, rectangle.y1), rectangle.x2, Math.min(y2, rectangle.y2)));
    }
    }

    return intersections;
    }

    /**
    * Calculates area of this rectangle.
    *
    * @return area of this rectangle.
    */
    public int area() {
    return Math.abs((x1 - x2) * (y1 - y2));
    }

    /**
    * Checks if this rectangle contains the specified rectangle.
    *
    * @param rectangle rectangle to check for.
    * @return true if rectangle inside this, false otherwise.
    */
    public boolean contains(Rectangle rectangle) {
    return x1 <= rectangle.x1 && rectangle.x2 <= x2 && y1 <= rectangle.y1 && rectangle.y2 <= y2;
    }

    @Override
    public boolean equals(Object o) {
    if (!(o instanceof Rectangle)) {
    return false;
    }

    Rectangle other = (Rectangle) o;
    return x1 == other.x1 && y1 == other.y1 && x2 == other.x2 && y2 == other.y2;
    }

    @Override
    public int hashCode() {
    int result = 17;

    result = 37 * result + x1;
    result = 37 * result + y1;
    result = 37 * result + x2;
    result = 37 * result + y2;

    return result;
    }

    @Override
    public String toString() {
    return String.format("Rectangle with x1: %s y1: %s x2: %s y2: %s", x1, y1, x2, y2);
    }
    }


    I have several questions/considerations:




    1. Is the provided solution correct?

    2. I assume the complexity of this algorithm is $O(n^2)$. Can it be improved?

    3. I've overridden toString(), equals() and hashCode() methods, although I've never called them (except toString() while debugging). Is it bad practise to do so?

    4. I feel that comments in javadoc are lame. How can they be improved and are they necessary at all?


    5. computeAreaFromFile() does 2 things: it reads file content and performs actual calculations. I think this method should be split, however I'm not sure how I could do this.










    share|improve this question


























      up vote
      13
      down vote

      favorite
      2









      up vote
      13
      down vote

      favorite
      2






      2





      I've been given the following task:




      Given N rectangles with edges parallel to axis, calculate the area of the union of all rectangles. The input and output are files specified in program arguments. Input is represented by N lines with 4 numbers separated by spaces, defining 2 opposite vertices of the rectangle. Output file should contain 1 number - the resulting area of the rectangles' union.




      Additional constraints:




      • $1 le N le 100$

      • $-10000 le x1$, $y1$, $x2$, $y2 le 10000$

      • Memory consumption < 16 MB

      • Program parameters should be validated

      • Input file format should be validated.


      Examples:



      Input:



      1 1 7 7


      Output:



      36


      Input:



      1 1 3 3  
      2 2 4 4


      Output:



      7


      My solution:



      public class Main {

      private List<Rectangle> rectangles = new ArrayList<>();

      public static void main(String args) {
      if (args.length != 2) {
      throw new IllegalArgumentException("Invalid arguments numbernProgram usage: java Main input output");
      }

      Main computer = new Main();
      long area = computer.computeAreaFromFile(args[0]);
      computer.writeAreaToFile(area, args[1]);
      }

      public long computeAreaFromFile(String inputFileName) {
      rectangles.clear();

      String line;
      try (BufferedReader inputFileReader = new BufferedReader(new FileReader(inputFileName))) {
      long area = 0;

      while ((line = inputFileReader.readLine()) != null) {
      Rectangle rectangle = Rectangle.fromString(line);
      area += addRectangleArea(rectangle, false);
      }

      return area;
      } catch (FileNotFoundException e) {
      throw new IllegalArgumentException("Input file not found");
      } catch (IOException e) {
      throw new RuntimeException(e);
      } catch (NumberFormatException | IndexOutOfBoundsException e) {
      throw new IllegalArgumentException("Input file contains incorrect line");
      }
      }

      private int addRectangleArea(Rectangle newRectangle, boolean isIntersection) {
      int result = 0;

      boolean hasIntersections = false;

      for (Rectangle existingRectangle : rectangles) {
      if (!existingRectangle.contains(newRectangle)) {
      List<Rectangle> complements = existingRectangle.complementOf(newRectangle);
      if (complements.size() > 0) {
      hasIntersections = true;

      for (Rectangle complement : complements) {
      result += addRectangleArea(complement, true);
      }

      break;
      }
      }
      }

      if (!hasIntersections) {
      result += newRectangle.area();
      }

      if (!isIntersection) {
      rectangles.add(newRectangle);
      }

      return result;
      }

      private void writeAreaToFile(long area, String outputFileName) {
      try (BufferedWriter writer = new BufferedWriter(new FileWriter(outputFileName))) {
      writer.write(String.valueOf(area));
      } catch (IOException e) {
      throw new RuntimeException("Could not open file " + outputFileName);
      }
      }
      }

      class Rectangle {
      public final int x1;
      public final int y1;
      public final int x2;
      public final int y2;

      public static Rectangle fromString(String input) throws NumberFormatException, IndexOutOfBoundsException {
      String splitInput = input.split(" ");

      if (splitInput.length != 4) {
      throw new IndexOutOfBoundsException();
      }

      return new Rectangle(Integer.valueOf(splitInput[0]),
      Integer.valueOf(splitInput[1]),
      Integer.valueOf(splitInput[2]),
      Integer.valueOf(splitInput[3]));
      }

      public Rectangle(int x1, int y1, int x2, int y2) {
      this.x1 = Math.min(x1, x2);
      this.y1 = Math.min(y1, y2);
      this.x2 = Math.max(x1, x2);
      this.y2 = Math.max(y1, y2);
      }

      /**
      * Finds a relative complement of the specified rectangle.
      *
      * @param rectangle rectangle to find a complement of.
      * @return {@link List} of the rectangles forming the resulting complement.
      */
      public List<Rectangle> complementOf(Rectangle rectangle) {
      List<Rectangle> intersections = new ArrayList<>();

      if (rectangle.x2 > x1 && x2 > rectangle.x1 && rectangle.y2 > y1 && y2 > rectangle.y1) {
      if (rectangle.y1 <= y1) {
      intersections.add(new Rectangle(rectangle.x1, rectangle.y1, rectangle.x2, y1));
      }

      if (y2 <= rectangle.y2) {
      intersections.add(new Rectangle(rectangle.x1, y2, rectangle.x2, rectangle.y2));
      }

      if (rectangle.x1 <= x1) {
      intersections.add(new Rectangle(rectangle.x1, Math.max(y1, rectangle.y1), x1, Math.min(y2, rectangle.y2)));
      }

      if (x2 <= rectangle.x2) {
      intersections.add(new Rectangle(x2, Math.max(y1, rectangle.y1), rectangle.x2, Math.min(y2, rectangle.y2)));
      }
      }

      return intersections;
      }

      /**
      * Calculates area of this rectangle.
      *
      * @return area of this rectangle.
      */
      public int area() {
      return Math.abs((x1 - x2) * (y1 - y2));
      }

      /**
      * Checks if this rectangle contains the specified rectangle.
      *
      * @param rectangle rectangle to check for.
      * @return true if rectangle inside this, false otherwise.
      */
      public boolean contains(Rectangle rectangle) {
      return x1 <= rectangle.x1 && rectangle.x2 <= x2 && y1 <= rectangle.y1 && rectangle.y2 <= y2;
      }

      @Override
      public boolean equals(Object o) {
      if (!(o instanceof Rectangle)) {
      return false;
      }

      Rectangle other = (Rectangle) o;
      return x1 == other.x1 && y1 == other.y1 && x2 == other.x2 && y2 == other.y2;
      }

      @Override
      public int hashCode() {
      int result = 17;

      result = 37 * result + x1;
      result = 37 * result + y1;
      result = 37 * result + x2;
      result = 37 * result + y2;

      return result;
      }

      @Override
      public String toString() {
      return String.format("Rectangle with x1: %s y1: %s x2: %s y2: %s", x1, y1, x2, y2);
      }
      }


      I have several questions/considerations:




      1. Is the provided solution correct?

      2. I assume the complexity of this algorithm is $O(n^2)$. Can it be improved?

      3. I've overridden toString(), equals() and hashCode() methods, although I've never called them (except toString() while debugging). Is it bad practise to do so?

      4. I feel that comments in javadoc are lame. How can they be improved and are they necessary at all?


      5. computeAreaFromFile() does 2 things: it reads file content and performs actual calculations. I think this method should be split, however I'm not sure how I could do this.










      share|improve this question















      I've been given the following task:




      Given N rectangles with edges parallel to axis, calculate the area of the union of all rectangles. The input and output are files specified in program arguments. Input is represented by N lines with 4 numbers separated by spaces, defining 2 opposite vertices of the rectangle. Output file should contain 1 number - the resulting area of the rectangles' union.




      Additional constraints:




      • $1 le N le 100$

      • $-10000 le x1$, $y1$, $x2$, $y2 le 10000$

      • Memory consumption < 16 MB

      • Program parameters should be validated

      • Input file format should be validated.


      Examples:



      Input:



      1 1 7 7


      Output:



      36


      Input:



      1 1 3 3  
      2 2 4 4


      Output:



      7


      My solution:



      public class Main {

      private List<Rectangle> rectangles = new ArrayList<>();

      public static void main(String args) {
      if (args.length != 2) {
      throw new IllegalArgumentException("Invalid arguments numbernProgram usage: java Main input output");
      }

      Main computer = new Main();
      long area = computer.computeAreaFromFile(args[0]);
      computer.writeAreaToFile(area, args[1]);
      }

      public long computeAreaFromFile(String inputFileName) {
      rectangles.clear();

      String line;
      try (BufferedReader inputFileReader = new BufferedReader(new FileReader(inputFileName))) {
      long area = 0;

      while ((line = inputFileReader.readLine()) != null) {
      Rectangle rectangle = Rectangle.fromString(line);
      area += addRectangleArea(rectangle, false);
      }

      return area;
      } catch (FileNotFoundException e) {
      throw new IllegalArgumentException("Input file not found");
      } catch (IOException e) {
      throw new RuntimeException(e);
      } catch (NumberFormatException | IndexOutOfBoundsException e) {
      throw new IllegalArgumentException("Input file contains incorrect line");
      }
      }

      private int addRectangleArea(Rectangle newRectangle, boolean isIntersection) {
      int result = 0;

      boolean hasIntersections = false;

      for (Rectangle existingRectangle : rectangles) {
      if (!existingRectangle.contains(newRectangle)) {
      List<Rectangle> complements = existingRectangle.complementOf(newRectangle);
      if (complements.size() > 0) {
      hasIntersections = true;

      for (Rectangle complement : complements) {
      result += addRectangleArea(complement, true);
      }

      break;
      }
      }
      }

      if (!hasIntersections) {
      result += newRectangle.area();
      }

      if (!isIntersection) {
      rectangles.add(newRectangle);
      }

      return result;
      }

      private void writeAreaToFile(long area, String outputFileName) {
      try (BufferedWriter writer = new BufferedWriter(new FileWriter(outputFileName))) {
      writer.write(String.valueOf(area));
      } catch (IOException e) {
      throw new RuntimeException("Could not open file " + outputFileName);
      }
      }
      }

      class Rectangle {
      public final int x1;
      public final int y1;
      public final int x2;
      public final int y2;

      public static Rectangle fromString(String input) throws NumberFormatException, IndexOutOfBoundsException {
      String splitInput = input.split(" ");

      if (splitInput.length != 4) {
      throw new IndexOutOfBoundsException();
      }

      return new Rectangle(Integer.valueOf(splitInput[0]),
      Integer.valueOf(splitInput[1]),
      Integer.valueOf(splitInput[2]),
      Integer.valueOf(splitInput[3]));
      }

      public Rectangle(int x1, int y1, int x2, int y2) {
      this.x1 = Math.min(x1, x2);
      this.y1 = Math.min(y1, y2);
      this.x2 = Math.max(x1, x2);
      this.y2 = Math.max(y1, y2);
      }

      /**
      * Finds a relative complement of the specified rectangle.
      *
      * @param rectangle rectangle to find a complement of.
      * @return {@link List} of the rectangles forming the resulting complement.
      */
      public List<Rectangle> complementOf(Rectangle rectangle) {
      List<Rectangle> intersections = new ArrayList<>();

      if (rectangle.x2 > x1 && x2 > rectangle.x1 && rectangle.y2 > y1 && y2 > rectangle.y1) {
      if (rectangle.y1 <= y1) {
      intersections.add(new Rectangle(rectangle.x1, rectangle.y1, rectangle.x2, y1));
      }

      if (y2 <= rectangle.y2) {
      intersections.add(new Rectangle(rectangle.x1, y2, rectangle.x2, rectangle.y2));
      }

      if (rectangle.x1 <= x1) {
      intersections.add(new Rectangle(rectangle.x1, Math.max(y1, rectangle.y1), x1, Math.min(y2, rectangle.y2)));
      }

      if (x2 <= rectangle.x2) {
      intersections.add(new Rectangle(x2, Math.max(y1, rectangle.y1), rectangle.x2, Math.min(y2, rectangle.y2)));
      }
      }

      return intersections;
      }

      /**
      * Calculates area of this rectangle.
      *
      * @return area of this rectangle.
      */
      public int area() {
      return Math.abs((x1 - x2) * (y1 - y2));
      }

      /**
      * Checks if this rectangle contains the specified rectangle.
      *
      * @param rectangle rectangle to check for.
      * @return true if rectangle inside this, false otherwise.
      */
      public boolean contains(Rectangle rectangle) {
      return x1 <= rectangle.x1 && rectangle.x2 <= x2 && y1 <= rectangle.y1 && rectangle.y2 <= y2;
      }

      @Override
      public boolean equals(Object o) {
      if (!(o instanceof Rectangle)) {
      return false;
      }

      Rectangle other = (Rectangle) o;
      return x1 == other.x1 && y1 == other.y1 && x2 == other.x2 && y2 == other.y2;
      }

      @Override
      public int hashCode() {
      int result = 17;

      result = 37 * result + x1;
      result = 37 * result + y1;
      result = 37 * result + x2;
      result = 37 * result + y2;

      return result;
      }

      @Override
      public String toString() {
      return String.format("Rectangle with x1: %s y1: %s x2: %s y2: %s", x1, y1, x2, y2);
      }
      }


      I have several questions/considerations:




      1. Is the provided solution correct?

      2. I assume the complexity of this algorithm is $O(n^2)$. Can it be improved?

      3. I've overridden toString(), equals() and hashCode() methods, although I've never called them (except toString() while debugging). Is it bad practise to do so?

      4. I feel that comments in javadoc are lame. How can they be improved and are they necessary at all?


      5. computeAreaFromFile() does 2 things: it reads file content and performs actual calculations. I think this method should be split, however I'm not sure how I could do this.







      java performance algorithm computational-geometry






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Nov 4 '16 at 23:18









      200_success

      128k15149412




      128k15149412










      asked Sep 9 '15 at 20:02









      Mikhail

      16417




      16417






















          2 Answers
          2






          active

          oldest

          votes

















          up vote
          4
          down vote













          The time for the approach you gave is in $O(n ^ 2)$.





          Dec. 10, 2018



          Details about a possible solution



          This is Klee's measure problem for $d = 2$.



          Apparently, an optimal algorithm for this case exists and is called Bentley's algorithm. Its running time is $O(n cdot log(n))$. However, it seems that the 1977 paper that describes it is unavailable. It uses sweep-line approach and a dynamic 1-d segment tree.



          We have $n$ axis-aligned rectangles. Our sweep-line moves across $x$. We have events along $x$ that correspond to start of rectangle and end of rectangle. The intersection of the sweep-line with a collection of rectangles is essentially a 1-d measure problem. We have $2 cdot n$ events with at most $2 cdot n$ distinct x values. We use a 1-d segment tree that we maintain via inserts and deletes to give 1-d measure that we "pull" with delta-$x$'s to give incremental contributions to 2-d measure. The costly operations are sort and insert/delete.



          Higher dimensions are more difficult to handle. We might then be better served by using higher-dimensional segment tree with intersection queries or an R-tree variant with intersection queries. This would depend on which is larger -- $d cdot log(n)$ or $log^{textrm{max}(d - 1, 1)}(n)$ for $d geq 1$ -- the former being smaller may imply that R-tree is better; the latter (i.e. we note that this time is with fractional cascading) being smaller implies segment tree is better.



          For more details, see the links.



          References




          • Bentley - Algorithms for Klee's rectangle problems (1977) -- possibly unavailable


          • Elizarov - Finding missing range in multidimensional domain - Answer (2017)
            https://cs.stackexchange.com/q/73819


          • Erickson - Klee's measure problem (1998)
            http://jeffe.cs.illinois.edu/open/klee.html


          • Chlebus - On the Klee's measure problem in small dimensions (1998)







          share|improve this answer























          • Wow, I accidentally came across this answer. Super helpful insight!
            – Mikhail
            Nov 26 '17 at 21:53


















          up vote
          3
          down vote













          Correctness



          (See the update at the end.)



          I don't believe your algorithm is correct. Here is the way I would expect to see it solved:




          1. Define a function rectDiff(r,s) which computes the difference of two rectangles r and s. It may return an empty list (if r is completely contained in s), a list of just r (if r is disjoint from s) or a list of two smaller rectangles r1, r2 representing the parts of r which do not intersect s. This is probably what your .complementsOf() method does.



          2. Given this rectDiff function, I would compute the area like this:



            Pseudo-code:



            theRects = ...read rects from a file...

            rectangles =
            totalArea = 0

            for r in theRects:
            pieces = [r]
            for s in rectangles:
            pieces = takeAway(pieces, s)
            for t in pieces:
            totalArea += area(t)
            append r to rectangles

            def takeAway(pieces, s):
            # pieces is a list of (disjoint) rects
            # s is a single rect
            # returns a new list of (disjoint) rects
            newPieces =
            for t in pieces:
            append rectDiff(t,s) to newPieces
            return newPieces


            The point is that when considering a new rectangle r you need to remove from r the overlap with all previous rectangles, and then you can add the area of the surviving complements to the total area.




          Your code, however, adds the area of a complement right away to the total area.



          Range trees



          If you employ the ideas in this article, you can use range trees to write the code this way:



          for r in theRectangles:
          let rlist = the list of rects in rectangles which overlap with r
          pieces = [r]
          for s in rlist:
          pieces = takeAway(pieces, s)
          ...
          add r to rectangles


          The idea is that using a range tree rlist might be a lot smaller than the full list rectangles.



          Update



          Your algorithm is probably correct since you recursively call addRectangleArea() on each complement piece.



          However, there is an inefficiency in the algorithm. Suppose:



          rectangles = [ r1, r2, r3, ... ]


          and we are processing a new rectangle r. Let



          cs1 = rectDiff(r, r1) = complements of r compared to r1
          = [ c1, c2, ... ]


          Your code calls addRectangleArea(c1) which then will compute rectDiff(c1, r1). However, this difference will always be empty. When considering c1 (or c2 or any rectangle in cs1) you can start with r2 in the rectangles list on the recursive call.






          share|improve this answer























          • Thanks for the review! You're right about what my complementsOf() method does. However, my algorithm does not add area of complements right away, instead I call addRectangleArea() recursively with the overlapping part of r, which is basically what you suggest. Apparently I failed to write this in concise way. Thanks for the range trees links, I'll take a look at it.
            – Mikhail
            Sep 10 '15 at 6:52










          • I see that now. Also see my update.
            – ErikR
            Sep 10 '15 at 7:45











          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ifUsing("editor", function () {
          StackExchange.using("externalEditor", function () {
          StackExchange.using("snippets", function () {
          StackExchange.snippets.init();
          });
          });
          }, "code-snippets");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "196"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f104258%2fcalculate-the-area-of-rectangles-union%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          2 Answers
          2






          active

          oldest

          votes








          2 Answers
          2






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          up vote
          4
          down vote













          The time for the approach you gave is in $O(n ^ 2)$.





          Dec. 10, 2018



          Details about a possible solution



          This is Klee's measure problem for $d = 2$.



          Apparently, an optimal algorithm for this case exists and is called Bentley's algorithm. Its running time is $O(n cdot log(n))$. However, it seems that the 1977 paper that describes it is unavailable. It uses sweep-line approach and a dynamic 1-d segment tree.



          We have $n$ axis-aligned rectangles. Our sweep-line moves across $x$. We have events along $x$ that correspond to start of rectangle and end of rectangle. The intersection of the sweep-line with a collection of rectangles is essentially a 1-d measure problem. We have $2 cdot n$ events with at most $2 cdot n$ distinct x values. We use a 1-d segment tree that we maintain via inserts and deletes to give 1-d measure that we "pull" with delta-$x$'s to give incremental contributions to 2-d measure. The costly operations are sort and insert/delete.



          Higher dimensions are more difficult to handle. We might then be better served by using higher-dimensional segment tree with intersection queries or an R-tree variant with intersection queries. This would depend on which is larger -- $d cdot log(n)$ or $log^{textrm{max}(d - 1, 1)}(n)$ for $d geq 1$ -- the former being smaller may imply that R-tree is better; the latter (i.e. we note that this time is with fractional cascading) being smaller implies segment tree is better.



          For more details, see the links.



          References




          • Bentley - Algorithms for Klee's rectangle problems (1977) -- possibly unavailable


          • Elizarov - Finding missing range in multidimensional domain - Answer (2017)
            https://cs.stackexchange.com/q/73819


          • Erickson - Klee's measure problem (1998)
            http://jeffe.cs.illinois.edu/open/klee.html


          • Chlebus - On the Klee's measure problem in small dimensions (1998)







          share|improve this answer























          • Wow, I accidentally came across this answer. Super helpful insight!
            – Mikhail
            Nov 26 '17 at 21:53















          up vote
          4
          down vote













          The time for the approach you gave is in $O(n ^ 2)$.





          Dec. 10, 2018



          Details about a possible solution



          This is Klee's measure problem for $d = 2$.



          Apparently, an optimal algorithm for this case exists and is called Bentley's algorithm. Its running time is $O(n cdot log(n))$. However, it seems that the 1977 paper that describes it is unavailable. It uses sweep-line approach and a dynamic 1-d segment tree.



          We have $n$ axis-aligned rectangles. Our sweep-line moves across $x$. We have events along $x$ that correspond to start of rectangle and end of rectangle. The intersection of the sweep-line with a collection of rectangles is essentially a 1-d measure problem. We have $2 cdot n$ events with at most $2 cdot n$ distinct x values. We use a 1-d segment tree that we maintain via inserts and deletes to give 1-d measure that we "pull" with delta-$x$'s to give incremental contributions to 2-d measure. The costly operations are sort and insert/delete.



          Higher dimensions are more difficult to handle. We might then be better served by using higher-dimensional segment tree with intersection queries or an R-tree variant with intersection queries. This would depend on which is larger -- $d cdot log(n)$ or $log^{textrm{max}(d - 1, 1)}(n)$ for $d geq 1$ -- the former being smaller may imply that R-tree is better; the latter (i.e. we note that this time is with fractional cascading) being smaller implies segment tree is better.



          For more details, see the links.



          References




          • Bentley - Algorithms for Klee's rectangle problems (1977) -- possibly unavailable


          • Elizarov - Finding missing range in multidimensional domain - Answer (2017)
            https://cs.stackexchange.com/q/73819


          • Erickson - Klee's measure problem (1998)
            http://jeffe.cs.illinois.edu/open/klee.html


          • Chlebus - On the Klee's measure problem in small dimensions (1998)







          share|improve this answer























          • Wow, I accidentally came across this answer. Super helpful insight!
            – Mikhail
            Nov 26 '17 at 21:53













          up vote
          4
          down vote










          up vote
          4
          down vote









          The time for the approach you gave is in $O(n ^ 2)$.





          Dec. 10, 2018



          Details about a possible solution



          This is Klee's measure problem for $d = 2$.



          Apparently, an optimal algorithm for this case exists and is called Bentley's algorithm. Its running time is $O(n cdot log(n))$. However, it seems that the 1977 paper that describes it is unavailable. It uses sweep-line approach and a dynamic 1-d segment tree.



          We have $n$ axis-aligned rectangles. Our sweep-line moves across $x$. We have events along $x$ that correspond to start of rectangle and end of rectangle. The intersection of the sweep-line with a collection of rectangles is essentially a 1-d measure problem. We have $2 cdot n$ events with at most $2 cdot n$ distinct x values. We use a 1-d segment tree that we maintain via inserts and deletes to give 1-d measure that we "pull" with delta-$x$'s to give incremental contributions to 2-d measure. The costly operations are sort and insert/delete.



          Higher dimensions are more difficult to handle. We might then be better served by using higher-dimensional segment tree with intersection queries or an R-tree variant with intersection queries. This would depend on which is larger -- $d cdot log(n)$ or $log^{textrm{max}(d - 1, 1)}(n)$ for $d geq 1$ -- the former being smaller may imply that R-tree is better; the latter (i.e. we note that this time is with fractional cascading) being smaller implies segment tree is better.



          For more details, see the links.



          References




          • Bentley - Algorithms for Klee's rectangle problems (1977) -- possibly unavailable


          • Elizarov - Finding missing range in multidimensional domain - Answer (2017)
            https://cs.stackexchange.com/q/73819


          • Erickson - Klee's measure problem (1998)
            http://jeffe.cs.illinois.edu/open/klee.html


          • Chlebus - On the Klee's measure problem in small dimensions (1998)







          share|improve this answer














          The time for the approach you gave is in $O(n ^ 2)$.





          Dec. 10, 2018



          Details about a possible solution



          This is Klee's measure problem for $d = 2$.



          Apparently, an optimal algorithm for this case exists and is called Bentley's algorithm. Its running time is $O(n cdot log(n))$. However, it seems that the 1977 paper that describes it is unavailable. It uses sweep-line approach and a dynamic 1-d segment tree.



          We have $n$ axis-aligned rectangles. Our sweep-line moves across $x$. We have events along $x$ that correspond to start of rectangle and end of rectangle. The intersection of the sweep-line with a collection of rectangles is essentially a 1-d measure problem. We have $2 cdot n$ events with at most $2 cdot n$ distinct x values. We use a 1-d segment tree that we maintain via inserts and deletes to give 1-d measure that we "pull" with delta-$x$'s to give incremental contributions to 2-d measure. The costly operations are sort and insert/delete.



          Higher dimensions are more difficult to handle. We might then be better served by using higher-dimensional segment tree with intersection queries or an R-tree variant with intersection queries. This would depend on which is larger -- $d cdot log(n)$ or $log^{textrm{max}(d - 1, 1)}(n)$ for $d geq 1$ -- the former being smaller may imply that R-tree is better; the latter (i.e. we note that this time is with fractional cascading) being smaller implies segment tree is better.



          For more details, see the links.



          References




          • Bentley - Algorithms for Klee's rectangle problems (1977) -- possibly unavailable


          • Elizarov - Finding missing range in multidimensional domain - Answer (2017)
            https://cs.stackexchange.com/q/73819


          • Erickson - Klee's measure problem (1998)
            http://jeffe.cs.illinois.edu/open/klee.html


          • Chlebus - On the Klee's measure problem in small dimensions (1998)








          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited 16 hours ago

























          answered Nov 4 '16 at 21:57









          bzliu94

          21213




          21213












          • Wow, I accidentally came across this answer. Super helpful insight!
            – Mikhail
            Nov 26 '17 at 21:53


















          • Wow, I accidentally came across this answer. Super helpful insight!
            – Mikhail
            Nov 26 '17 at 21:53
















          Wow, I accidentally came across this answer. Super helpful insight!
          – Mikhail
          Nov 26 '17 at 21:53




          Wow, I accidentally came across this answer. Super helpful insight!
          – Mikhail
          Nov 26 '17 at 21:53












          up vote
          3
          down vote













          Correctness



          (See the update at the end.)



          I don't believe your algorithm is correct. Here is the way I would expect to see it solved:




          1. Define a function rectDiff(r,s) which computes the difference of two rectangles r and s. It may return an empty list (if r is completely contained in s), a list of just r (if r is disjoint from s) or a list of two smaller rectangles r1, r2 representing the parts of r which do not intersect s. This is probably what your .complementsOf() method does.



          2. Given this rectDiff function, I would compute the area like this:



            Pseudo-code:



            theRects = ...read rects from a file...

            rectangles =
            totalArea = 0

            for r in theRects:
            pieces = [r]
            for s in rectangles:
            pieces = takeAway(pieces, s)
            for t in pieces:
            totalArea += area(t)
            append r to rectangles

            def takeAway(pieces, s):
            # pieces is a list of (disjoint) rects
            # s is a single rect
            # returns a new list of (disjoint) rects
            newPieces =
            for t in pieces:
            append rectDiff(t,s) to newPieces
            return newPieces


            The point is that when considering a new rectangle r you need to remove from r the overlap with all previous rectangles, and then you can add the area of the surviving complements to the total area.




          Your code, however, adds the area of a complement right away to the total area.



          Range trees



          If you employ the ideas in this article, you can use range trees to write the code this way:



          for r in theRectangles:
          let rlist = the list of rects in rectangles which overlap with r
          pieces = [r]
          for s in rlist:
          pieces = takeAway(pieces, s)
          ...
          add r to rectangles


          The idea is that using a range tree rlist might be a lot smaller than the full list rectangles.



          Update



          Your algorithm is probably correct since you recursively call addRectangleArea() on each complement piece.



          However, there is an inefficiency in the algorithm. Suppose:



          rectangles = [ r1, r2, r3, ... ]


          and we are processing a new rectangle r. Let



          cs1 = rectDiff(r, r1) = complements of r compared to r1
          = [ c1, c2, ... ]


          Your code calls addRectangleArea(c1) which then will compute rectDiff(c1, r1). However, this difference will always be empty. When considering c1 (or c2 or any rectangle in cs1) you can start with r2 in the rectangles list on the recursive call.






          share|improve this answer























          • Thanks for the review! You're right about what my complementsOf() method does. However, my algorithm does not add area of complements right away, instead I call addRectangleArea() recursively with the overlapping part of r, which is basically what you suggest. Apparently I failed to write this in concise way. Thanks for the range trees links, I'll take a look at it.
            – Mikhail
            Sep 10 '15 at 6:52










          • I see that now. Also see my update.
            – ErikR
            Sep 10 '15 at 7:45















          up vote
          3
          down vote













          Correctness



          (See the update at the end.)



          I don't believe your algorithm is correct. Here is the way I would expect to see it solved:




          1. Define a function rectDiff(r,s) which computes the difference of two rectangles r and s. It may return an empty list (if r is completely contained in s), a list of just r (if r is disjoint from s) or a list of two smaller rectangles r1, r2 representing the parts of r which do not intersect s. This is probably what your .complementsOf() method does.



          2. Given this rectDiff function, I would compute the area like this:



            Pseudo-code:



            theRects = ...read rects from a file...

            rectangles =
            totalArea = 0

            for r in theRects:
            pieces = [r]
            for s in rectangles:
            pieces = takeAway(pieces, s)
            for t in pieces:
            totalArea += area(t)
            append r to rectangles

            def takeAway(pieces, s):
            # pieces is a list of (disjoint) rects
            # s is a single rect
            # returns a new list of (disjoint) rects
            newPieces =
            for t in pieces:
            append rectDiff(t,s) to newPieces
            return newPieces


            The point is that when considering a new rectangle r you need to remove from r the overlap with all previous rectangles, and then you can add the area of the surviving complements to the total area.




          Your code, however, adds the area of a complement right away to the total area.



          Range trees



          If you employ the ideas in this article, you can use range trees to write the code this way:



          for r in theRectangles:
          let rlist = the list of rects in rectangles which overlap with r
          pieces = [r]
          for s in rlist:
          pieces = takeAway(pieces, s)
          ...
          add r to rectangles


          The idea is that using a range tree rlist might be a lot smaller than the full list rectangles.



          Update



          Your algorithm is probably correct since you recursively call addRectangleArea() on each complement piece.



          However, there is an inefficiency in the algorithm. Suppose:



          rectangles = [ r1, r2, r3, ... ]


          and we are processing a new rectangle r. Let



          cs1 = rectDiff(r, r1) = complements of r compared to r1
          = [ c1, c2, ... ]


          Your code calls addRectangleArea(c1) which then will compute rectDiff(c1, r1). However, this difference will always be empty. When considering c1 (or c2 or any rectangle in cs1) you can start with r2 in the rectangles list on the recursive call.






          share|improve this answer























          • Thanks for the review! You're right about what my complementsOf() method does. However, my algorithm does not add area of complements right away, instead I call addRectangleArea() recursively with the overlapping part of r, which is basically what you suggest. Apparently I failed to write this in concise way. Thanks for the range trees links, I'll take a look at it.
            – Mikhail
            Sep 10 '15 at 6:52










          • I see that now. Also see my update.
            – ErikR
            Sep 10 '15 at 7:45













          up vote
          3
          down vote










          up vote
          3
          down vote









          Correctness



          (See the update at the end.)



          I don't believe your algorithm is correct. Here is the way I would expect to see it solved:




          1. Define a function rectDiff(r,s) which computes the difference of two rectangles r and s. It may return an empty list (if r is completely contained in s), a list of just r (if r is disjoint from s) or a list of two smaller rectangles r1, r2 representing the parts of r which do not intersect s. This is probably what your .complementsOf() method does.



          2. Given this rectDiff function, I would compute the area like this:



            Pseudo-code:



            theRects = ...read rects from a file...

            rectangles =
            totalArea = 0

            for r in theRects:
            pieces = [r]
            for s in rectangles:
            pieces = takeAway(pieces, s)
            for t in pieces:
            totalArea += area(t)
            append r to rectangles

            def takeAway(pieces, s):
            # pieces is a list of (disjoint) rects
            # s is a single rect
            # returns a new list of (disjoint) rects
            newPieces =
            for t in pieces:
            append rectDiff(t,s) to newPieces
            return newPieces


            The point is that when considering a new rectangle r you need to remove from r the overlap with all previous rectangles, and then you can add the area of the surviving complements to the total area.




          Your code, however, adds the area of a complement right away to the total area.



          Range trees



          If you employ the ideas in this article, you can use range trees to write the code this way:



          for r in theRectangles:
          let rlist = the list of rects in rectangles which overlap with r
          pieces = [r]
          for s in rlist:
          pieces = takeAway(pieces, s)
          ...
          add r to rectangles


          The idea is that using a range tree rlist might be a lot smaller than the full list rectangles.



          Update



          Your algorithm is probably correct since you recursively call addRectangleArea() on each complement piece.



          However, there is an inefficiency in the algorithm. Suppose:



          rectangles = [ r1, r2, r3, ... ]


          and we are processing a new rectangle r. Let



          cs1 = rectDiff(r, r1) = complements of r compared to r1
          = [ c1, c2, ... ]


          Your code calls addRectangleArea(c1) which then will compute rectDiff(c1, r1). However, this difference will always be empty. When considering c1 (or c2 or any rectangle in cs1) you can start with r2 in the rectangles list on the recursive call.






          share|improve this answer














          Correctness



          (See the update at the end.)



          I don't believe your algorithm is correct. Here is the way I would expect to see it solved:




          1. Define a function rectDiff(r,s) which computes the difference of two rectangles r and s. It may return an empty list (if r is completely contained in s), a list of just r (if r is disjoint from s) or a list of two smaller rectangles r1, r2 representing the parts of r which do not intersect s. This is probably what your .complementsOf() method does.



          2. Given this rectDiff function, I would compute the area like this:



            Pseudo-code:



            theRects = ...read rects from a file...

            rectangles =
            totalArea = 0

            for r in theRects:
            pieces = [r]
            for s in rectangles:
            pieces = takeAway(pieces, s)
            for t in pieces:
            totalArea += area(t)
            append r to rectangles

            def takeAway(pieces, s):
            # pieces is a list of (disjoint) rects
            # s is a single rect
            # returns a new list of (disjoint) rects
            newPieces =
            for t in pieces:
            append rectDiff(t,s) to newPieces
            return newPieces


            The point is that when considering a new rectangle r you need to remove from r the overlap with all previous rectangles, and then you can add the area of the surviving complements to the total area.




          Your code, however, adds the area of a complement right away to the total area.



          Range trees



          If you employ the ideas in this article, you can use range trees to write the code this way:



          for r in theRectangles:
          let rlist = the list of rects in rectangles which overlap with r
          pieces = [r]
          for s in rlist:
          pieces = takeAway(pieces, s)
          ...
          add r to rectangles


          The idea is that using a range tree rlist might be a lot smaller than the full list rectangles.



          Update



          Your algorithm is probably correct since you recursively call addRectangleArea() on each complement piece.



          However, there is an inefficiency in the algorithm. Suppose:



          rectangles = [ r1, r2, r3, ... ]


          and we are processing a new rectangle r. Let



          cs1 = rectDiff(r, r1) = complements of r compared to r1
          = [ c1, c2, ... ]


          Your code calls addRectangleArea(c1) which then will compute rectDiff(c1, r1). However, this difference will always be empty. When considering c1 (or c2 or any rectangle in cs1) you can start with r2 in the rectangles list on the recursive call.







          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited Nov 15 '16 at 4:59









          Jamal

          30.2k11115226




          30.2k11115226










          answered Sep 9 '15 at 23:40









          ErikR

          1,75546




          1,75546












          • Thanks for the review! You're right about what my complementsOf() method does. However, my algorithm does not add area of complements right away, instead I call addRectangleArea() recursively with the overlapping part of r, which is basically what you suggest. Apparently I failed to write this in concise way. Thanks for the range trees links, I'll take a look at it.
            – Mikhail
            Sep 10 '15 at 6:52










          • I see that now. Also see my update.
            – ErikR
            Sep 10 '15 at 7:45


















          • Thanks for the review! You're right about what my complementsOf() method does. However, my algorithm does not add area of complements right away, instead I call addRectangleArea() recursively with the overlapping part of r, which is basically what you suggest. Apparently I failed to write this in concise way. Thanks for the range trees links, I'll take a look at it.
            – Mikhail
            Sep 10 '15 at 6:52










          • I see that now. Also see my update.
            – ErikR
            Sep 10 '15 at 7:45
















          Thanks for the review! You're right about what my complementsOf() method does. However, my algorithm does not add area of complements right away, instead I call addRectangleArea() recursively with the overlapping part of r, which is basically what you suggest. Apparently I failed to write this in concise way. Thanks for the range trees links, I'll take a look at it.
          – Mikhail
          Sep 10 '15 at 6:52




          Thanks for the review! You're right about what my complementsOf() method does. However, my algorithm does not add area of complements right away, instead I call addRectangleArea() recursively with the overlapping part of r, which is basically what you suggest. Apparently I failed to write this in concise way. Thanks for the range trees links, I'll take a look at it.
          – Mikhail
          Sep 10 '15 at 6:52












          I see that now. Also see my update.
          – ErikR
          Sep 10 '15 at 7:45




          I see that now. Also see my update.
          – ErikR
          Sep 10 '15 at 7:45


















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Code Review Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.





          Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


          Please pay close attention to the following guidance:


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f104258%2fcalculate-the-area-of-rectangles-union%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          Ellipse (mathématiques)

          Quarter-circle Tiles

          Mont Emei