算法需要，以确定是否一个矩形完全覆盖由另一组矩形 [英] Algorithm required to determine if a rectangle is completely covered by another set of rectangles

问题描述

我在寻找一种算法，将确定一个新的矩形完全覆盖一组现有的矩形。把这个问题的另一种方法，是新的联合国矩形存在完全覆盖现有​​的矩形区域？

似乎有很多的算法来确定矩形重叠等问题，但我真的不能找到任何解决这个确切的问题。

使用x，y坐标

的矩形将被重新presented。这个问题涉及到地理测绘。

修改 - 从张贴的OP评论：

  

该矩形在X对准/ Y轴

解决方案

如果矩形排列，很容易：

让我们假设你有矩形，A0，想知道如果它是完全由（B1，B2，B3 ...）= B

  A：=（A0）
而病人：=弹出乙
  对于R于A
    若P完全覆盖R：
      从A删除ř
    否则若P和R不重叠：
      从A删除ř
      在subrentangles小号打破R：=（S1，S2，S3 ...）以下的交点\
                                                     以P边缘
      按S为A
如果A为空：
   说B叠A0
其他：
   说B没有完全覆盖A0
 

I am searching for an algorithm that will determine if a new rectangle is completely covered by a set of existing rectangles. Another way of putting the question, is does the new rectangle exist completely with the area covered by the existing rectangles?

There seem to be lots of algorithms to determine rectangle overlap and so on, but I can't really find anything that solves this exact problem.

The rectangles will be represented using x, y coordinates. This problem relates to geographical mapping.

Edit - from comment posted by the OP:

The rectangles are aligned on the X/Y axis

解决方案

If rectangles are aligned that's easy:

Let's say you have rectangle A0 and want to know if it is fully covered by (B1, B2, B3...) = B

A := (A0)
while P := pop B
  for R in A
    if P fully covers R:
      remove R from A
    else if P and R does overlap:
      remove R from A
      break R in subrentangles S := (S1, S2, S3,...) following the intersections \
                                                     with P edges
      push S into A
if A is empty:
   say B covers A0
else:
   say B does not fully cover A0

这篇关于算法需要，以确定是否一个矩形完全覆盖由另一组矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！