Find the set of largest contiguous rectangles to cover multiple areas [duplicate]

by

I found the paper Fast Algorithms To Partition Simple Rectilinear Polygons from San-Yuan Wu and Sartaj Sahni, which could be of interest to you. In your example the region with character ‘d’ forms a rectilinear polygon, also the regions with ‘c’ and ‘.’. This paper includes algorithms for hole-free simple rectilinear polygons.

If a polygon includes holes, there are algorithms running with O(n^3/2 log n) time, as JM Keil in the paper Polygon Decomposition on page 11 states.

If minimizing the total length of the line segments introduced in the partitioning process is the other optimization criterion, the problem becomes NP-complete if the polygon contains holes (page 12). For these problems approximation algorithms exist (the paper refers to papers with such algorithms). If the polygon doesn’t contain holes there is an O(n^4) time algorithm.

More Related Contents:

  1. How to determine if a point is in a 2D triangle? [closed]
  2. Equation for testing if a point is inside a circle
  3. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  4. An algorithm for inflating/deflating (offsetting, buffering) polygons
  5. How to calculate an angle from three points? [closed]
  6. How to find the intersection point between a line and a rectangle?
  7. Sort points in clockwise order?
  8. How do I efficiently determine if a polygon is convex, non-convex or complex?
  9. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  10. Is there an efficient algorithm to generate a 2D concave hull?
  11. Largest circle inside a non-convex polygon
  12. Puzzle: Find largest rectangle (maximal rectangle problem)
  13. Circle-circle intersection points
  14. How to find two most distant points?
  15. Polygon enclosing a set of points
  16. What is the most efficient algorithm to find a straight line that goes through most points?
  17. Collision detection of huge number of circles
  18. Create non-intersecting polygon passing through all given points
  19. Determining if two line segments intersect? [duplicate]
  20. Calculating the position of points in a circle
  21. Mesh generation from points with x, y and z coordinates
  22. How do you find a point at a given perpendicular distance from a line?
  23. Find if a point is inside a convex hull for a set of points without computing the hull itself
  24. Best way to find a point on a circle closest to a given point
  25. Algorithm for reflecting a point across a line
  26. Compute the area of intersection between a circle and a triangle?
  27. determine if a point sits inside an arbitrary shape?
  28. How can I perform Collision Detection on rotated rectangles? [closed]
  29. Location of highest density on a sphere
  30. Distance from a point to a polygon

Leave a Comment