Module: Turf::Lineclip

Defined in:
lib/turf/lib/lineclip.rb

Overview

:nodoc:

Class Method Summary collapse

Class Method Details

.bit_code(p, bbox) ⇒ Object

bit code reflects the point position relative to the bbox:

     left  mid  right
top  1001  1000  1010
mid  0001  0000  0010

bottom 0101 0100 0110



109
110
111
112
113
114
115
116
 
# File 'lib/turf/lib/lineclip.rb', line 109

def self.bit_code(p, bbox) # rubocop:disable Naming/MethodParameterName
  code = 0
  code |= 1 if p[0] < bbox[0] # left
  code |= 2 if p[0] > bbox[2] # right
  code |= 4 if p[1] < bbox[1] # bottom
  code |= 8 if p[1] > bbox[3] # top
  code
end

.intersect(a, b, edge, bbox) ⇒ Object

intersect a segment against one of the 4 lines that make up the bbox



92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/turf/lib/lineclip.rb', line 92

def self.intersect(a, b, edge, bbox) # rubocop:disable Naming/MethodParameterName
  if edge.anybits?(8)
    [a[0] + (((b[0] - a[0]) * (bbox[3] - a[1]).to_f) / (b[1] - a[1])), bbox[3]]
  elsif edge.anybits?(4)
    [a[0] + (((b[0] - a[0]) * (bbox[1] - a[1]).to_f) / (b[1] - a[1])), bbox[1]]
  elsif edge.anybits?(2)
    [bbox[2], a[1] + (((b[1] - a[1]) * (bbox[2] - a[0]).to_f) / (b[0] - a[0]))]
  elsif edge.anybits?(1)
    [bbox[0], a[1] + (((b[1] - a[1]) * (bbox[0] - a[0]).to_f) / (b[0] - a[0]))]
  end
end

.lineclip(points, bbox, result = []) ⇒ Object

Cohen-Sutherland line clipping algorithm, adapted to efficiently handle polylines rather than just segments.



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/turf/lib/lineclip.rb', line 8

def self.lineclip(points, bbox, result = [])
  len = points.length
  code_a = bit_code(points[0], bbox)
  part = []
  a = nil
  b = nil

  (1...len).each do |i|
    a = points[i - 1]
    b = points[i]
    code_b = last_code = bit_code(b, bbox)

    loop do
      if (code_a | code_b).zero?
        # accept
        part << a

        if code_b != last_code
          # segment went outside
          part << b

          if i < len - 1
            # start a new line
            result << part
            part = []
          end
        elsif i == len - 1
          part << b
        end
        break
      elsif code_a.anybits?(code_b)
        # trivial reject
        break
      elsif code_a != 0
        # a outside, intersect with clip edge
        a = intersect(a, b, code_a, bbox)
        code_a = bit_code(a, bbox)
      else
        # b outside
        b = intersect(a, b, code_b, bbox)
        code_b = bit_code(b, bbox)
      end
    end

    code_a = last_code
  end

  result << part unless part.empty?

  result
end

.polygonclip(points, bbox) ⇒ Object

Sutherland-Hodgeman polygon clipping algorithm



61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/turf/lib/lineclip.rb', line 61

def self.polygonclip(points, bbox)
  result = []
  prev = nil
  prev_inside = nil

  # clip against each side of the clip rectangle
  [8, 4, 2, 1].each do |edge|
    result = []
    prev = points.last
    prev_inside = bit_code(prev, bbox).nobits?(edge)

    points.each do |p|
      inside = bit_code(p, bbox).nobits?(edge)

      # if segment goes through the clip window, add an intersection
      result << intersect(prev, p, edge, bbox) if inside != prev_inside

      result << p if inside # add a point if it's inside

      prev = p
      prev_inside = inside
    end

    points = result
    break if points.empty?
  end

  result
end