如何检查给定的非凸区域是否与给定的矩形完全重叠

Question

是否有明确的算法来检查给定的非凸区域是否与给定的矩形完全重叠？这两种形状都是由多条线定义的，所以我们做的是矢量几何。我不想碰撞检测，只想完全重叠。

故事如下:我们有一个SVG画布，用户可以在上面放置矩形，可能是旋转的。在画布上存在着基本的层系统(每个矩形都在它自己的层上)。请求如下:删除一个矩形，该矩形被其他与其重叠的矩形完全遮挡。因此，矩形以外的矩形构成非凸区域，也可能是不连续的.

目标编程语言是PHP，但任何语言的解决方案都是受欢迎的。

Answer 1

您可能需要查看一些空间拓扑套件(比如带有各种端口的JTS http://www.vividsolutions.com/jts/jtshome.htm )。

您可以在多个几何图形上执行联合/交叉等操作，在您的示例中，如果将复杂多边形与矩形合并，则结果应该是原始多边形，否则矩形将“窥视”某个位置。

Answer 2

这并不微妙，但您可以检查对象的任何点是否位于矩形的范围内，如果存在，则它不会完全覆盖它。

Answer 3

我不知道当矩形旋转时会发生什么。但这是我的第一次，很有可能我已经走远了。因为这是针对SVG的，所以我使用javascript。如果有用的话，将其移植到PHP应该比较简单。

(function(win) {
    function Rectangle(el) {
       this.element = el;
       this._area = ''
       Rectangle.instances.push(this);
    }
    Rectangle.instances = [];
    Rectangle.largest = function() {
       var areas = Rectangle.collect('area');
       var largest_area = Math.max.apply(Math, areas); 
       return Rectangle.instances[areas.indexOf(largest_area)]
    }
    Rectangle.collect = function(prop) {
       var props = [], m;
       for (var i=0, l = Rectangle.instances.length; i<l; i++) {
          if (m = Rectangle.instances[i][prop]) {
             var val = (typeof m === 'function') ? m.call(Rectangle.instances[i]) : m;
             props.push(val);
          }      
       }
       return props;
    }
    Rectangle.prototype.area = function() {
       if (!this._area) { this._area = this.element.width * this.element.height; }
       return this._area;
    }

    Rectangle.prototype.overlaps = function(r) {
       var origin_inside = r.element.x <= this.element.x && r.element.y <= this.element.y,
           ends_inside_x = r.element.x + r.element.width >= this.element.x + this.element.width,
           ends_inside_y = r.element.y + r.element.height >= this.element.y + this.element.height;

       return origin_inside && ends_inside_x && ends_inside_y

    }




  rect1 = new Rectangle({width:10, height: 20, x:10, y:30});
  rect2 = new Rectangle({width:5, height: 30, x:20, y:40});
  rect3 = new Rectangle({width:5, height: 1, x:12, y:31});


  console.log(rect2.overlaps(rect1)) //false
  console.log(Rectangle.largest().overlaps(rect2)) //false
  console.log(rect2.overlaps(rect2)) //true
  console.log(rect3.overlaps(rect1)) //true

   //to use this with actual SVG elements, 

   var svgCanvas = document.getElementById('svgElementId');
   var ctx = svgCanvas.contentDocument

   svgr1 = new Rectangle(ctx.getElementById('rect1'))
   svgr2 = new Rectangle(ctx.getElementById('rect2'))

   console.log(svgr1.overlaps(svgr2)) //true

})(this);