Class: PerfectShape::Line

Inherits:
Shape
  • Object
show all
Includes:
MultiPoint
Defined in:
lib/perfect_shape/line.rb

Instance Attribute Summary

Attributes included from MultiPoint

#points

Class Method Summary collapse

Instance Method Summary collapse

Methods included from MultiPoint

#first_point, #initialize, #max_x, #max_y, #min_x, #min_y, normalize_point_array

Methods inherited from Shape

#==, #bounding_box, #center_point, #center_x, #center_y, #height, #max_x, #max_y, #min_x, #min_y, #width

Class Method Details

.point_crossings(x1, y1, x2, y2, px, py) ⇒ Object

Calculates the number of times the line from (x1,y1) to (x2,y2) crosses the ray extending to the right from (px,py). If the point lies on the line, then no crossings are recorded. +1 is returned for a crossing where the Y coordinate is increasing -1 is returned for a crossing where the Y coordinate is decreasing



191
192
193
194
195
196
197
198
199
200
 
# File 'lib/perfect_shape/line.rb', line 191

def point_crossings(x1, y1, x2, y2, px, py)
  return 0 if (py <  y1 && py <  y2)
  return 0 if (py >= y1 && py >= y2)
  # assert(y1 != y2)
  return 0 if (px >= x1 && px >= x2)
  return ((y1 < y2) ? 1 : -1) if (px <  x1 && px <  x2)
  xintercept = x1 + (py - y1) * (x2 - x1) / (y2 - y1)
  return 0 if (px >= xintercept)
  (y1 < y2) ? 1 : -1
end

.point_distance(x1, y1, x2, y2, px, py) ⇒ Object

Returns the distance from a point to a line segment. The distance measured is the distance between the specified point and the closest point between the specified end points. If the specified point intersects the line segment in between the end points, this method returns 0.0.

Parameters:

  • x1 —

    the X coordinate of the start point of the specified line segment

  • y1 —

    the Y coordinate of the start point of the specified line segment

  • x2 —

    the X coordinate of the end point of the specified line segment

  • y2 —

    the Y coordinate of the end point of the specified line segment

  • px —

    the X coordinate of the specified point being measured against the specified line segment

  • py —

    the Y coordinate of the specified point being measured against the specified line segment

Returns:

  • a double value that is the distance from the specified point to the specified line segment.



180
181
182
183
184
 
# File 'lib/perfect_shape/line.rb', line 180

def point_distance(x1, y1,
                           x2, y2,
                           px, py)
  BigDecimal(::Math.sqrt(point_distance_square(x1, y1, x2, y2, px, py)).to_s)
end

.point_distance_square(x1, y1, x2, y2, px, py) ⇒ Object

Returns the square of the distance from a point to a line segment. The distance measured is the distance between the specified point and the closest point between the specified end points. If the specified point intersects the line segment in between the end points, this method returns 0.0.

Parameters:

  • x1 —

    the X coordinate of the start point of the specified line segment

  • y1 —

    the Y coordinate of the start point of the specified line segment

  • x2 —

    the X coordinate of the end point of the specified line segment

  • y2 —

    the Y coordinate of the end point of the specified line segment

  • px —

    the X coordinate of the specified point being measured against the specified line segment

  • py —

    the Y coordinate of the specified point being measured against the specified line segment

Returns:

  • a double value that is the square of the distance from the specified point to the specified line segment.



107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
 
# File 'lib/perfect_shape/line.rb', line 107

def point_distance_square(x1, y1,
                                 x2, y2,
                                 px, py)
  x1 = BigDecimal(x1.to_s)
  y1 = BigDecimal(y1.to_s)
  x2 = BigDecimal(x2.to_s)
  y2 = BigDecimal(y2.to_s)
  px = BigDecimal(px.to_s)
  py = BigDecimal(py.to_s)
  # Adjust vectors relative to x1,y1
  # x2,y2 becomes relative vector from x1,y1 to end of segment
  x2 -= x1
  y2 -= y1
  # px,py becomes relative vector from x1,y1 to test point
  px -= x1
  py -= y1
  dot_product = px * x2 + py * y2
  if dot_product <= 0.0
    # px,py is on the side of x1,y1 away from x2,y2
    # distance to segment is length of px,py vector
    # "length of its (clipped) projection" is now 0.0
    projected_length_square = BigDecimal('0.0')
  else
    # switch to backwards vectors relative to x2,y2
    # x2,y2 are already the negative of x1,y1=>x2,y2
    # to get px,py to be the negative of px,py=>x2,y2
    # the dot product of two negated vectors is the same
    # as the dot product of the two normal vectors
    px = x2 - px
    py = y2 - py
    dot_product = px * x2 + py * y2
    if dot_product <= 0.0
      # px,py is on the side of x2,y2 away from x1,y1
      # distance to segment is length of (backwards) px,py vector
      # "length of its (clipped) projection" is now 0.0
      projected_length_square = BigDecimal('0.0')
    else
      # px,py is between x1,y1 and x2,y2
      # dot_product is the length of the px,py vector
      # projected on the x2,y2=>x1,y1 vector times the
      # length of the x2,y2=>x1,y1 vector
      projected_length_square = dot_product * dot_product / (x2 * x2 + y2 * y2)
    end
  end
  # Distance to line is now the length of the relative point
  # vector minus the length of its projection onto the line
  # (which is zero if the projection falls outside the range
  #  of the line segment).
  length_square = px * px + py * py - projected_length_square
  length_square = BigDecimal('0.0') if length_square < 0
  length_square
end

.relative_counterclockwise(x1, y1, x2, y2, px, py) ⇒ Object

Returns an indicator of where the specified point (px,py) lies with respect to the line segment from (x1,y1) to (x2,y2).

The return value can be either 1, -1, or 0 and indicates in which direction the specified line must pivot around its first end point, (x1,y1), in order to point at the specified point (px,py). A return value of 1 indicates that the line segment must turn in the direction that takes the positive X axis towards the negative Y axis. In the default coordinate system used by Java 2D, this direction is counterclockwise.

A return value of -1 indicates that the line segment must turn in the direction that takes the positive X axis towards the positive Y axis. In the default coordinate system, this direction is clockwise.

A return value of 0 indicates that the point lies exactly on the line segment. Note that an indicator value of 0 is rare and not useful for determining collinearity because of floating point rounding issues.

If the point is colinear with the line segment, but not between the end points, then the value will be -1 if the point lies “beyond (x1,y1)” or 1 if the point lies “beyond (x2,y2)”.

Parameters:

  • x1 —

    the X coordinate of the start point of the specified line segment

  • y1 —

    the Y coordinate of the start point of the specified line segment

  • x2 —

    the X coordinate of the end point of the specified line segment

  • y2 —

    the Y coordinate of the end point of the specified line segment

  • px —

    the X coordinate of the specified point to be compared with the specified line segment

  • py —

    the Y coordinate of the specified point to be compared with the specified line segment

Returns:

  • an integer that indicates the position of the third specified coordinates with respect to the line segment formed by the first two specified coordinates.



56
57
58
59
60
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
 
# File 'lib/perfect_shape/line.rb', line 56

def relative_counterclockwise(x1, y1, x2, y2, px, py)
  x2 -= x1
  y2 -= y1
  px -= x1
  py -= y1
  ccw = px * y2 - py * x2
  if ccw == 0.0
    # The point is colinear, classify based on which side of
    # the segment the point falls on.  We can calculate a
    # relative value using the projection of px,py onto the
    # segment - a negative value indicates the point projects
    # outside of the segment in the direction of the particular
    # endpoint used as the origin for the projection.
    ccw = px * x2 + py * y2
    if ccw > 0.0
      # Reverse the projection to be relative to the original x2,y2
      # x2 and y2 are simply negated.
      # px and py need to have (x2 - x1) or (y2 - y1) subtracted
      #    from them (based on the original values)
      # Since we really want to get a positive answer when the
      #    point is "beyond (x2,y2)", then we want to calculate
      #    the inverse anyway - thus we leave x2 & y2 negated.
      px -= x2
      py -= y2
      ccw = px * x2 + py * y2
      ccw = 0.0 if ccw < 0.0
    end
  end
  (ccw < 0.0) ? -1 : ((ccw > 0.0) ? 1 : 0)
end

Instance Method Details

#contain?(x_or_point, y = nil, outline: true, distance_tolerance: 0) ⇒ Boolean

Checks if line contains point (two-number Array or x, y args), with distance tolerance (0 by default)

the line, false if the point lies outside of the line’s bounds.

Parameters:

  • x —

    The X coordinate of the point to test.

  • y (defaults to: nil) —

    The Y coordinate of the point to test.

  • distance_tolerance (defaults to: 0) —

    The distance from line to tolerate (0 by default)

Returns:

  • (Boolean) —

    true if the point lies within the bound of



215
216
217
218
219
220
 
# File 'lib/perfect_shape/line.rb', line 215

def contain?(x_or_point, y = nil, outline: true, distance_tolerance: 0)
  x, y = Point.normalize_point(x_or_point, y)
  return unless x && y
  distance_tolerance = BigDecimal(distance_tolerance.to_s)
  point_distance(x, y) <= distance_tolerance
end

#intersect?(rectangle) ⇒ Boolean

Returns:

  • (Boolean) 


317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
 
# File 'lib/perfect_shape/line.rb', line 317

def intersect?(rectangle)
  require 'perfect_shape/rectangle'
  x1 = points[0][0]
  y1 = points[0][1]
  x2 = points[1][0]
  y2 = points[1][1]
  out1 = out2 = nil
  return true if (out2 = rectangle.out_state(x2, y2)) == 0
  while (out1 = rectangle.out_state(x1, y1)) != 0
    return false if (out1 & out2) != 0
    if (out1 & (Rectangle::OUT_LEFT | Rectangle::OUT_RIGHT)) != 0
      x = rectangle.x
      x += rectangle.width if (out1 & Rectangle::OUT_RIGHT) != 0
      y1 = y1 + (x - x1) * (y2 - y1) / (x2 - x1)
      x1 = x
    else
      y = rectangle.y
      y += rectangle.height if (out1 & Rectangle::OUT_BOTTOM) != 0
      x1 = x1 + (y - y1) * (x2 - x1) / (y2 - y1)
      y1 = y
    end
  end
  true
end

#point_crossings(x_or_point, y = nil) ⇒ Object

Calculates the number of times the line crosses the ray extending to the right from (px,py). If the point lies on the line, then no crossings are recorded. +1 is returned for a crossing where the Y coordinate is increasing -1 is returned for a crossing where the Y coordinate is decreasing



239
240
241
242
243
 
# File 'lib/perfect_shape/line.rb', line 239

def point_crossings(x_or_point, y = nil)
  x, y = Point.normalize_point(x_or_point, y)
  return unless x && y
  Line.point_crossings(points[0][0], points[0][1], points[1][0], points[1][1], x, y)
end

#point_distance(x_or_point, y = nil) ⇒ Object 



222
223
224
225
226
 
# File 'lib/perfect_shape/line.rb', line 222

def point_distance(x_or_point, y = nil)
  x, y = Point.normalize_point(x_or_point, y)
  return unless x && y
  Line.point_distance(points[0][0], points[0][1], points[1][0], points[1][1], x, y)
end

#rect_crossings(rxmin, rymin, rxmax, rymax, crossings = 0) ⇒ Object

Accumulate the number of times the line crosses the shadow extending to the right of the rectangle. See the comment for the PerfectShape::Rectangle::RECT_INTERSECTS constant for more complete details.

crossings arg is the initial crossings value to add to (useful in cases where you want to accumulate crossings from multiple shapes)



252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
 
# File 'lib/perfect_shape/line.rb', line 252

def rect_crossings(rxmin, rymin, rxmax, rymax, crossings = 0)
  x0 = points[0][0]
  y0 = points[0][1]
  x1 = points[1][0]
  y1 = points[1][1]
  return crossings if y0 >= rymax && y1 >= rymax
  return crossings if y0 <= rymin && y1 <= rymin
  return crossings if x0 <= rxmin && x1 <= rxmin
  if x0 >= rxmax && x1 >= rxmax
    # Line is entirely to the right of the rect
    # and the vertical ranges of the two overlap by a non-empty amount
    # Thus, this line segment is partially in the "right-shadow"
    # Path may have done a complete crossing
    # Or path may have entered or exited the right-shadow
    if y0 < y1
        # y-increasing line segment...
        # We know that y0 < rymax and y1 > rymin
        crossings += 1 if (y0 <= rymin)
        crossings += 1 if (y1 >= rymax)
    elsif y1 < y0
        # y-decreasing line segment...
        # We know that y1 < rymax and y0 > rymin
        crossings -= 1 if (y1 <= rymin)
        crossings -= 1 if (y0 >= rymax)
    end
    return crossings
  end
  # Remaining case:
  # Both x and y ranges overlap by a non-empty amount
  # First do trivial INTERSECTS rejection of the cases
  # where one of the endpoints is inside the rectangle.
  return PerfectShape::Rectangle::RECT_INTERSECTS if ((x0 > rxmin && x0 < rxmax && y0 > rymin && y0 < rymax) ||
    (x1 > rxmin && x1 < rxmax && y1 > rymin && y1 < rymax))
  # Otherwise calculate the y intercepts and see where
  # they fall with respect to the rectangle
  xi0 = x0
  if y0 < rymin
    xi0 += ((rymin - y0) * (x1 - x0) / (y1 - y0))
  elsif y0 > rymax
    xi0 += ((rymax - y0) * (x1 - x0) / (y1 - y0))
  end
  xi1 = x1
  if y1 < rymin
    xi1 += ((rymin - y1) * (x0 - x1) / (y0 - y1))
  elsif y1 > rymax
    xi1 += ((rymax - y1) * (x0 - x1) / (y0 - y1))
  end
  return crossings if xi0 <= rxmin && xi1 <= rxmin
  if xi0 >= rxmax && xi1 >= rxmax
    if y0 < y1
      # y-increasing line segment...
      # We know that y0 < rymax and y1 > rymin
      crossings += 1 if (y0 <= rymin)
      crossings += 1 if (y1 >= rymax)
    elsif y1 < y0
      # y-decreasing line segment...
      # We know that y1 < rymax and y0 > rymin
      crossings -= 1 if (y1 <= rymin)
      crossings -= 1 if (y0 >= rymax)
    end
    return crossings
  end
  PerfectShape::Rectangle::RECT_INTERSECTS
end

#relative_counterclockwise(x_or_point, y = nil) ⇒ Object 



228
229
230
231
232
 
# File 'lib/perfect_shape/line.rb', line 228

def relative_counterclockwise(x_or_point, y = nil)
  x, y = Point.normalize_point(x_or_point, y)
  return unless x && y
  Line.relative_counterclockwise(points[0][0], points[0][1], points[1][0], points[1][1], x, y)
end