Geek asks and answers

Given the many horizontal and vertical lines, how to find all the rectangles that have any sub-rectangle inside them?

I have many horizontal and vertical lines that make up a rectangle, for example, in this example.

Picture of horizontal and vertical lines

Is there an algorithm or code that can find every rectangle that does not contain another rectangle. I mean, the largest rectangle in this image is not the rectangle I'm looking for, because it contains other rectangles inside it.

The rectangles I'm looking for should be empty. I have a list of start and end points of each line, for example (a, b) - (c, d). As a result, I want to get a list of rectangles (x, y, w, h) or equivalent.

, , , , , , .

+5
4

, . ( ). x y, . :

enter image description here

(x_i, y_j) , ​​:

__|_1__2__3__4_
1 | x  x  0  x
2 | x  x  0  0
3 | 0  x  x  x
4 | x  x  x  x

. , (3,2) (3,4) (4,4), (4,3), "" , - (3,3) (3,4), (4,4), (4,3). , memoization .

+2

Computational Geometry. vertical sweep line .

, (p1, p2), p1 - , p2 - . ( p.x p.y).

.

  • - O(n log n)
  • sweep line status. , , alive. event queue, . event queue .
  • , event queue.
    • start point, sweep line status ( y-) ( O(log n) ) event queue ( ) ( O(log n) ). sweep line status, , , sweep line status. , , .
    • , sweep line status.

( n ):

  • O(n log n).
  • = 2 * n = O(n)
  • O(log n) ( event queue, sweep line status. , O(n log n).

, O(n log n).

. -. .

EDIT:

, , ( ), ( ).

+1

x y? ?

, , , x y. [(a, b), (a, d)] [(a, b), (c, b)].

- . , .

- . , .

- , - .

: . . Ex. x. , .

, . , , , . , .

. , .

0

...

:

  • V = , x.

  • H = ( ) x.

  • CH = An ( ) ( y-) .

  • CR = A ( y-) . , , . , .

:

V H .

, , CH.

, , CH.

, :

  • CR , . , , , .

  • CH :

    • Add a rectangle to CR with the last processed point as below, the current point as the top and y-coordinate of the vertical line to the left.

Done.

Note:

When the x-coordinate of the horizontal start points or end points or vertical lines is equal, the following order should be supported:

x of horizontal start < x of vertical line < x of horizontal finish

Otherwise, you skip the rectangles.

0
source

More articles:


All Articles