루비에 중복 영역이없는 많은 사각형을 효율적으로 저장하려고 시도합니다.

Question

루비에서 하나의 변수에 여러 개의 사각형을 저장하고 싶습니다. 화면을 새로 고쳐야하는 직사각형을 추가하기 위해서입니다. 나는 위쪽, 왼쪽, 높이와 함께 클래스 Rectangle과 배열에 사각형 변수를 저장하려고 시도했다. 그러나 iterating하고 계산할 때 너무 느립니다.

새 직사각형을 추가 할 때 새로 고칠 화면에 중복 된 것이 없어야하며 중복을 제거하기 위해 계산하는 데 시간이 많이 걸리지 않아야합니다 (최상의 경우 시간이 없음).

죄송합니다, 저는 영어 원어민이 아니며 많은 아이디어에 감사드립니다.

는 '사각형'

클래스 사각형

attr_accessor :top,:left,:height,:width 

def initialize(options={}) 
    @top=options[:top] 
    @left=options[:left] 
    @height=options[:height] 
    @width=options[:width] 
end 

def bottom 
    @top+@height-1 
end 

def right 
    @left+@width-1 
end 

def coveredBy?(rectangle) 
    return false if @top<rectangle.top 
    return false if @left<rectangle.left 
    return false if bottom>rectangle.bottom 
    return false if right>rectangle.right 
    return true 
end 

def intersection!(rectangle) 
    if @top<rectangle.top 
     @top=rectangle.top 
    end 
    if @left<rectangle.left 
     @left=rectangle.left 
    end 
    if bottom>(t=rectangle.bottom) 
     @height=rectangle.bottom+1-@top 
    end 
    if right>(t=rectangle.right) 
     @width=rectangle.right+1-@left 
    end 
end 

def &(rectangle) 
    if @top>=rectangle.top 
     top=@top 
    else 
     top=rectangle.top 
    end 
    if @left>=rectangle.left 
     left=@left 
    else 
     left=rectangle.left 
    end 
    if bottom<=rectangle.bottom 
     height=bottom+1-top 
    else 
     height=rectangle.bottom+1-top 
    end 
    return nil if height<=0 
    if right<=rectangle.right 
     width=right+1-left 
    else 
     width=rectangle.right+1-left 
    end 
    return nil if width<=0 
    return Rectangle.new(
     :top=>top, 
     :left=>left, 
     :height=>height, 
     :width=>width 
    ) 
end 

def -(rectArg) 
    return [] if empty? 
    return [self] if bottom<rectArg.top 
    return [self] if @top>rectArg.bottom 
    return [self] if right<rectArg.left 
    return [self] if @left>rectArg.right 

    ret=[] 
    line=@top 
    if @top<rectArg.top 
     ret[ret.count]=Rectangle.new(
      :top=>line, 
      :left=>@left, 
      :height=>[rectArg.top-@top,@height].min, 
      :width=>@width 
     ) 
     line=ret.first.bottom+1 
    end 
    if @left<rectArg.left 
     ret[ret.count]=Rectangle.new(
      :top=>line, 
      :left=>@left, 
      :height=>[rectArg.bottom+1-line,bottom+1-line].min, 
      :width=>[rectArg.left-@left,@width].min 
     ) 
    end 
    if right>rectArg.right 
     ret[ret.count]=Rectangle.new(
      :top=>line, 
      :left=>rectArg.right+1, 
      :height=>[rectArg.bottom+1-line,bottom+1-line].min, 
      :width=>[right-rectArg.right,@width].min 
     ) 
    end 
    if bottom>rectArg.bottom 
     ret[ret.count]=Rectangle.new(
      :top=>rectArg.bottom+1, 
      :left=>@left, 
      :height=>[bottom-rectArg.bottom,@height].min, 
      :width=>@width 
     ) 
    end 
    ret 
end 

# Mit return true geht es deutlich schneller als mit ||. 
def outside?(rectangle) 
    return true if empty? 
    return true if rectangle.empty? 
    return true if bottom<rectangle.top 
    return true if @top>rectangle.bottom 
    return true if right<rectangle.left 
    return true if @left>rectangle.right 
    return false 
end 


# nebeneinander oder Überschneidung 
public def touching?(rectangle) 
    horizontalRange=((rectangle.left-1..(rectangle.left+rectangle.width))) 
    verticalRange=((rectangle.top-1..(rectangle.top+rectangle.height))) 
    horizontalRange.any?{|column| 
     column==@left||column==@left+@width 
    } && 
    verticalRange.any?{|line| 
     line==@top||line==@top+@height 
    } 
end 

def ==(rectangle) 
    #rectangle.kind_of?(self.class) && 
    @top==rectangle.top && 
    @height==rectangle.height && 
    @left==rectangle.left && 
    @width==rectangle.width 
end 

def !=(rectangle) 
    !(self==rectangle) 
end 

def empty? 
    return true if top.nil? 
    return true if left.nil? 
    return true if height.nil? 
    return true if height<=0 
    return true if width.nil? 
    return true if width<=0 
    # @empty=@height<=0 || @width<=0 if @empty.nil? 
    # @empty 
end 

public def area 
    # @area||=@height*@width 
    # @area 
    @height*@width 
end 

# nur wenn sie passgenau nebeneinander liegen 
# (Überschneidungen darf es nicht geben) 
public def mergeHorizontally(rectangle) 
    return nil if @top!=rectangle.top 
    return nil if @height!=rectangle.height 
    if @left+@width==rectangle.left 
     return Rectangle.new(
      :top=>@top, 
      :left=>@left, 
      :height=>@height, 
      :width=>@width+rectangle.width 
     ) 
    elsif rectangle.left+rectangle.width==@left 
     return Rectangle.new(
      :top=>rectangle.top, 
      :left=>rectangle.left, 
      :height=>rectangle.height, 
      :width=>rectangle.width+@width 
     ) 
    else 
     return nil 
    end 
end 

# nur wenn sie passgenau nebeneinander liegen 
# (Überschneidungen darf es nicht geben) 
public def mergeVertically(rectangle) 
    return nil if @left!=rectangle.left 
    return nil if @width!=rectangle.width 
    if @top+@height==rectangle.top 
     # return nil 
     return Rectangle.new(
      :top=>@top, 
      :left=>@left, 
      :height=>@height+rectangle.height, 
      :width=>@width 
     ) 
    elsif rectangle.top+rectangle.height==@top 
     # return nil 
     return Rectangle.new(
      :top=>rectangle.top, 
      :left=>rectangle.left, 
      :height=>rectangle.height+@height, 
      :width=>rectangle.width 
     ) 
    else 
     return nil 
    end 
end 

public def to_rects 
    Rectangles.new([self]) 
end 

public def >(rectangle) 
    return true if @height>rectangle.height 
    return true if @width>rectangle.width 
    return false 
end 

public def +(rectArg) 
    # @@log<<"Rectangle#+ ===================================================" 
    # @@log<<"rectArg: #{rectArg.class}" 
    newTop=[@top,rectArg.top].min 
    newLeft=[@left,rectArg.left].min 
    newHeight=[bottom,rectArg.bottom].max+1-newTop 
    newWidth=[right,rectArg.right].max+1-newLeft 
    Rectangle.new(
     :top=>newTop, 
     :left=>newLeft, 
     :height=>newHeight, 
     :width=>newWidth 
    ) 
end 

끝을 필요로

당신은 객체가 동일한 지 여부를 확인하기 위해 자신의 방법을 정의 할 필요가

Answer 1

.

class Rectangle 
    attr_accessor :top, :left, :width, :height 

    def initialize(top, left, width, height) 
    @top = top 
    @left = left 
    @width = width 
    @height = height 
    end 

    def ==(rect) 
    @top == rect.top && 
    @left == rect.left && 
    @width == rect.width && 
    @height == rect.height 
    end 
end 

rect1 = Rectangle.new(10, 10, 20, 30) 
rect2 = Rectangle.new(20, 20, 10, 15) 
rectangles = [rect1, rect2] 

rect3 = Rectangle.new(30, 30, 10, 10) 
rectangles.include?(rect3) # false 

rect_dup = rect1.dup 
rectangles.include?(rect_dup) # true 

편집 : 추가 벤치 마크

require 'benchmark' 

rectangles = [] 

1.upto(1000) do |i| 
    rectangles << Rectangle.new(i, i, 10, 10) 
end 

Benchmark.bm do |x| 
    x.report(:missing_rectangles) do 
    1.upto(1000) do |i| 
     rect = Rectangle.new(i, i + 5, 10, 10) 
     rectangles.include?(rect) 
    end 
    end 
end 

결과 :

    user  system  total real 
missing_rectangles 0.110000 0.000000 0.110000 ( 0.107022)