切分矩形

Question

我需要從接收其他矩形作爲參數的函數獲取AS3矩形對象。結果與Photoshop中的切片工具非常相似。這是非常難以解釋，所以這裏是一個畫面：

http://yvaing.free.fr/flash/squaresCut.png

藍色方塊是給定爲參數和綠色的是結果的矩形。給定矩形可以重疊，如圖片2所示或不在框架中。

我不尋找一個圖形化的實現，而是一種獲得矩形對象的方式。

你知道有lib能做嗎？

Answer 1

看起來像一個有趣的問題，所以我給了它一個裂縫。我的想法是隻是蠻力它由：

1. 確定哪個點中產生的矩形的角落可以是。
2. 從此列表中刪除所有重複項。
3. 檢查所有矩形，理論上可以繪製矩形的點將列表中的所有4個角落。
4. 過濾掉所有無效的矩形
5. 減少所有有效矩形到所需的最低金額（如果一個有效的矩形包含另一個有效矩形的「孩子」被刪除（這與我們原來的長方形等的一個相交）。

看來工作（雖然我還沒有廣泛的測試）。

這裏有一個demo。很抱歉的調色板。我即興發揮。

這裏的源代碼（可以概率相當優化一點）：

package 
{ 
    import flash.display.*; 
    import flash.events.*; 
    import flash.geom.*; 
    import flash.text.TextField; 
    import flash.text.TextFieldAutoSize; 
    import flash.text.TextFormat; 
    import flash.utils.getTimer; 

    public class Main extends Sprite { 

     private var m_colors : Array = [0xffaaaa, 0x77ff77, 0xaaaaff, 0xffff44, 0xff44ff, 0xaaffff, 0x444444, 0xffaa55, 0xaaff55, 0x55aaff, 0x55ffaa]; 
     private var m_roomRect : Rectangle; 
     private var m_sourceRects : Vector.<Rectangle> = new Vector.<Rectangle>(); 
     private var m_currentDragRect : Rectangle; 
     private var m_dragMousePoint : Point = new Point(); 
     private var m_outputTextField : TextField; 

     public function Main() : void { 
      m_roomRect = new Rectangle(40, 40, 400, 400); 

      m_sourceRects.push(new Rectangle(60, 60, 60, 80)); 
      m_sourceRects.push(new Rectangle(130, 220, 70, 80)); 
      m_sourceRects.push(new Rectangle(160, 260, 100, 80)); 

      this.stage.addEventListener(MouseEvent.MOUSE_DOWN, onMouseEvent); 
      this.stage.addEventListener(MouseEvent.MOUSE_MOVE, onMouseEvent); 
      this.stage.addEventListener(MouseEvent.MOUSE_UP, onMouseEvent); 

      var tf : TextField = new TextField(); 
      tf.defaultTextFormat = new TextFormat("_sans", 12); 
      tf.text = "Click and drag blue rectangles to move them"; 
      tf.autoSize = TextFieldAutoSize.LEFT; 
      tf.x = (m_roomRect.left + m_roomRect.right)/2 - tf.width/2; 
      tf.y = m_roomRect.top - tf.height; 
      this.stage.addChild(tf); 

      m_outputTextField = new TextField(); 
      m_outputTextField.defaultTextFormat = tf.defaultTextFormat; 
      m_outputTextField.width = m_roomRect.width; 
      m_outputTextField.x = m_roomRect.x; 
      m_outputTextField.y = m_roomRect.bottom + 5; 
      this.stage.addChild(m_outputTextField); 

      redraw(); 
     } 

     private function onMouseEvent(event : MouseEvent):void { 
      switch(event.type) { 
       case MouseEvent.MOUSE_DOWN: 
        checkMouseDownOnRect(); 
        break; 
       case MouseEvent.MOUSE_MOVE: 
        checkMouseDrag(); 
        break; 
       case MouseEvent.MOUSE_UP: 
        m_currentDragRect = null; 
        break; 
      } 
     } 

     private function checkMouseDownOnRect():void { 
      m_currentDragRect = null; 
      m_dragMousePoint = new Point(this.stage.mouseX, this.stage.mouseY); 

      for each(var sourceRect : Rectangle in m_sourceRects) { 
       if (sourceRect.containsPoint(m_dragMousePoint)) { 
        m_currentDragRect = sourceRect; 
        break; 
       } 
      } 
     } 

     private function checkMouseDrag():void { 
      if (m_currentDragRect != null) { 
       m_currentDragRect.x += this.stage.mouseX - m_dragMousePoint.x; 
       m_currentDragRect.y += this.stage.mouseY - m_dragMousePoint.y; 
       m_dragMousePoint.x = this.stage.mouseX; 
       m_dragMousePoint.y = this.stage.mouseY; 
       redraw(); 
      } 
     } 

     private function redraw():void { 
      // calculate data 
      var time : int = getTimer(); 
      var data : CalculationData = calculate(); 
      var calcTime : int = getTimer() - time; 

      // draw room bounds 
      this.graphics.clear(); 
      this.graphics.lineStyle(3, 0x0); 
      this.graphics.drawRect(m_roomRect.x, m_roomRect.y, m_roomRect.width, m_roomRect.height); 

      // draw generated rectangles 
      for (var i : int = 0; i < data.outputRects.length; i++) { 
       var color : int = m_colors[i % m_colors.length]; 
       var rect : Rectangle = data.outputRects[i]; 
       this.graphics.lineStyle(2, color, 0.5); 
       this.graphics.beginFill(color, 0.5); 
       this.graphics.drawRect(rect.x, rect.y, rect.width, rect.height); 
       this.graphics.endFill(); 
      } 

      // draw horisontal lines (a line that crosses each red point) for debug purposes 
      for each (var lineY : int in data.lines) { 
       this.graphics.lineStyle(1, 0, 0.2); 
       this.graphics.moveTo(m_roomRect.x, lineY); 
       this.graphics.lineTo(m_roomRect.x + m_roomRect.width, lineY); 
       this.graphics.endFill(); 
      } 

      // the original rectangles 
      for each (var sourceRect : Rectangle in m_sourceRects) { 
       this.graphics.lineStyle(2, 0x0); 
       this.graphics.beginFill(0x0000aa, 0.5); 
       this.graphics.drawRect(sourceRect.x, sourceRect.y, sourceRect.width, sourceRect.height); 
       this.graphics.endFill(); 
      } 

      // draw all points that was used to generate the output rectangles for debug purposes 
      for each (var p : Point in data.points) { 
       this.graphics.lineStyle(0, 0, 0); 
       this.graphics.beginFill(0xff0000, 1); 
       this.graphics.drawCircle(p.x, p.y, 3); 
       this.graphics.endFill(); 
      } 

      m_outputTextField.text = "Rect count: " + data.outputRects.length + " (calculation time: " + calcTime + "ms)"; 
     } 

     private function calculate(): CalculationData { 
      // list of y coords for horisontal lines, 
      // which are interesting when determining which rectangles to generate 
      var lines : Vector.<int> = new Vector.<int>(); 

      // list of all points which are interesting 
      // when determining where the corners of the generated rect could be 
      var points : Vector.<Point> = new Vector.<Point>(); 

      // add the 4 corners of the room to interesting points 
      points.push(new Point(m_roomRect.left, m_roomRect.top)); 
      points.push(new Point(m_roomRect.right, m_roomRect.top)); 
      points.push(new Point(m_roomRect.left, m_roomRect.bottom)); 
      points.push(new Point(m_roomRect.right, m_roomRect.bottom)); 

      for (var i:int = 0; i < m_sourceRects.length; i++) { 
       var sourceRect : Rectangle = m_sourceRects[i]; 

       // source rect is completely outside of the room, we shoud ignore it 
       if (!m_roomRect.containsRect(sourceRect) && !m_roomRect.intersects(sourceRect)) { 
        continue; 
       } 

       // push the y coord of the rect's top edge to the list of lines if it's not already been added 
       if (lines.indexOf(sourceRect.y) == -1) { 
        lines.push(sourceRect.y); 
       } 

       // push the y coord of the rect's bottom edge to the list of lines if it's not already been added 
       if (lines.indexOf(sourceRect.bottom) == -1) { 
        lines.push(sourceRect.bottom); 
       } 

       // add the 4 corners of the source rect to the list of interesting points 
       addCornerPoints(points, sourceRect); 

       // find the intersections between source rectangles and add those points 
       for (var j:int = 0; j < m_sourceRects.length; j++) { 
        if (j != i) { 
         var intersect : Rectangle = m_sourceRects[i].intersection(m_sourceRects[j]); 
         if (intersect.width != 0 && intersect.height != 0) { 
          addCornerPoints(points, intersect); 
         } 
        } 
       } 
      } 

      for (i = 0; i < lines.length; i++) { 
       // add the points where the horisontal lines intersect with the room's left and right edges 
       points.push(new Point(m_roomRect.x, lines[i])); 
       points.push(new Point(m_roomRect.right, lines[i])); 

       var lineRect : Rectangle = new Rectangle(m_roomRect.x, m_roomRect.y, 
                 m_roomRect.width, lines[i] - m_roomRect.y); 

       // add all points where the horisontal lines intersect with the source rectangles 
       for (a = 0; a < m_sourceRects.length;a++) { 
        intersect = m_sourceRects[a].intersection(lineRect); 
        if (intersect.width != 0 && intersect.height != 0) { 
         addCornerPoints(points, intersect); 
        } 
       } 
      } 

      // clamp all points that are outside of the room to the room edges 
      for (i = 0; i < points.length; i++) { 
       points[i].x = Math.min(Math.max(m_roomRect.left, points[i].x), m_roomRect.right); 
       points[i].y = Math.min(Math.max(m_roomRect.top, points[i].y), m_roomRect.bottom); 
      } 

      removeDuplicatePoints(points); 

      var outputRects : Vector.<Rectangle> = new Vector.<Rectangle>(); 

      var pointsHash : Object = { }; 
      for (a = 0; a < points.length; a++) { 
       pointsHash[points[a].x + "_" + points[a].y] = true; 
      } 

      for (var a:int = 0; a < points.length; a++) { 
       for (var b:int = 0; b < points.length; b++) { 
        if (b != a && points[b].x > points[a].x && points[b].y == points[a].y) { 
         for (var c:int = 0; c < points.length; c++) { 
          // generate a rectangle that has its four corners in our points of interest 
          if (c != b && c != a && points[c].y > points[b].y && points[c].x == points[b].x) { 
           var r : Rectangle = new Rectangle(points[a].x, points[a].y, points[b].x - points[a].x, points[c].y - points[b].y); 
           // make sure the rect has the bottom left corner in one of our points 
           if (pointsHash[r.left+"_"+r.bottom]) { 
            var containsOrIntersectsWithSource : Boolean = false; 
            for (i = 0; i < m_sourceRects.length;i++) { 
             if (r.containsRect(m_sourceRects[i]) || r.intersects(m_sourceRects[i])) { 
              containsOrIntersectsWithSource = true; 
              break; 
             } 
            } 

            // we don't add any rectangles that either intersects with a source rect 
            // or completely contains a source rect 
            if (!containsOrIntersectsWithSource) { 
             outputRects.push(r); 
            } 
           } 
          } 
         } 
        } 
       } 
      } 

      trace("outputRects before cleanup:", outputRects.length); 
      combineOutputRects(outputRects) 
      trace("outputRects after cleanup", outputRects.length); 

      var data : CalculationData = new CalculationData(); 
      data.outputRects = outputRects; 
      data.lines = lines; 
      data.points = points; 

      return data; 
     } 

     private function addCornerPoints(points : Vector.<Point>, rect : Rectangle) : void { 
      points.push(new Point(rect.left, rect.top)); 
      points.push(new Point(rect.right, rect.top)); 
      points.push(new Point(rect.left, rect.bottom)); 
      points.push(new Point(rect.right, rect.bottom)); 
     } 

     // removes all rectangle that are already contained in another rectangle 
     private function combineOutputRects(outputRects : Vector.<Rectangle>):Boolean { 
      for (var a : int = 0; a < outputRects.length; a++) { 
       for (var b : int = 0; b < outputRects.length; b++) { 
        if (b != a) { 
         if (outputRects[a].containsRect(outputRects[b])) { 
          trace("\tremoved rect " + outputRects[b] + ", it was contained in " + outputRects[a]); 
          outputRects.splice(b, 1); 
          b--; 
          a = 0; 
         } 
        } 
       } 
      } 
      return false; 
     } 

     private function removeDuplicatePoints(points : Vector.<Point>) : void { 
      var usedPoints : Object = {}; 
      for (var i : int = 0; i < points.length; i++) { 
       if (usedPoints[points[i].toString()]) { 
        points.splice(i, 1); 
        i--; 
       } else { 
        usedPoints[points[i].toString()] = true; 
       } 
      } 
     } 
    } 
} 

import flash.geom.Point; 
import flash.geom.Rectangle; 

class CalculationData { 
    public var outputRects : Vector.<Rectangle> = new Vector.<Rectangle>; 
    public var lines : Vector.<int> = new Vector.<int>; 
    public var points : Vector.<Point> = new Vector.<Point>; 
}