Class: PerfectShape::QuadraticBezierCurve
- Includes:
- MultiPoint
- Defined in:
- lib/perfect_shape/quadratic_bezier_curve.rb
Overview
Mostly ported from java.awt.geom: docs.oracle.com/javase/8/docs/api/java/awt/geom/QuadCurve2D.html
Instance Attribute Summary
Attributes included from MultiPoint
Class Method Summary collapse
-
.point_crossings(x1, y1, xc, yc, x2, y2, px, py, level = 0) ⇒ Object
Calculates the number of times the quadratic bézier curve from (x1,y1) to (x2,y2) crosses the ray extending to the right from (x,y).
Instance Method Summary collapse
-
#contain?(x_or_point, y = nil) ⇒ @code true
Checks if quadratic bézier curve contains point (two-number Array or x, y args).
-
#point_crossings(x_or_point, y = nil, level = 0) ⇒ Object
Calculates the number of times the quad crosses the ray extending to the right from (x,y).
Methods included from MultiPoint
#initialize, #max_x, #max_y, #min_x, #min_y
Methods inherited from Shape
#==, #bounding_box, #center_x, #center_y, #height, #max_x, #max_y, #min_x, #min_y, #normalize_point, #width
Class Method Details
.point_crossings(x1, y1, xc, yc, x2, y2, px, py, level = 0) ⇒ Object
Calculates the number of times the quadratic bézier curve from (x1,y1) to (x2,y2) crosses the ray extending to the right from (x,y). If the point lies on a part of the curve, then no crossings are counted for that intersection. the level parameter should be 0 at the top-level call and will count up for each recursion level to prevent infinite recursion +1 is added for each crossing where the Y coordinate is increasing -1 is added for each crossing where the Y coordinate is decreasing
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
# File 'lib/perfect_shape/quadratic_bezier_curve.rb', line 37 def point_crossings(x1, y1, xc, yc, x2, y2, px, py, level = 0) return 0 if (py < y1 && py < yc && py < y2) return 0 if (py >= y1 && py >= yc && py >= y2) # Note y1 could equal y2... return 0 if (px >= x1 && px >= xc && px >= x2) if (px < x1 && px < xc && px < x2) if (py >= y1) return 1 if (py < y2) else # py < y1 return -1 if (py >= y2) end # py outside of y11 range, and/or y1==y2 return 0 end # double precision only has 52 bits of mantissa return PerfectShape::Line.point_crossings(x1, y1, x2, y2, px, py) if (level > 52) x1c = BigDecimal((x1 + xc).to_s) / 2 y1c = BigDecimal((y1 + yc).to_s) / 2 xc1 = BigDecimal((xc + x2).to_s) / 2 yc1 = BigDecimal((yc + y2).to_s) / 2 xc = BigDecimal((x1c + xc1).to_s) / 2 yc = BigDecimal((y1c + yc1).to_s) / 2 # [xy]c are NaN if any of [xy]0c or [xy]c1 are NaN # [xy]0c or [xy]c1 are NaN if any of [xy][0c1] are NaN # These values are also NaN if opposing infinities are added return 0 if (xc.nan? || yc.nan?) point_crossings(x1, y1, x1c, y1c, xc, yc, px, py, level+1) + point_crossings(xc, yc, xc1, yc1, x2, y2, px, py, level+1); end |
Instance Method Details
#contain?(x_or_point, y = nil) ⇒ @code true
Checks if quadratic bézier curve contains point (two-number Array or x, y args)
the quadratic bézier curve, false if the point lies outside of the quadratic bézier curve’s bounds.
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 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 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 |
# File 'lib/perfect_shape/quadratic_bezier_curve.rb', line 80 def contain?(x_or_point, y = nil) x, y = normalize_point(x_or_point, y) return unless x && y x1 = points[0][0] y1 = points[0][1] xc = points[1][0] yc = points[1][1] x2 = points[2][0] y2 = points[2][1] # We have a convex shape bounded by quad curve Pc(t) # and ine Pl(t). # # P1 = (x1, y1) - start point of curve # P2 = (x2, y2) - end point of curve # Pc = (xc, yc) - control point # # Pq(t) = P1*(1 - t)^2 + 2*Pc*t*(1 - t) + P2*t^2 = # = (P1 - 2*Pc + P2)*t^2 + 2*(Pc - P1)*t + P1 # Pl(t) = P1*(1 - t) + P2*t # t = [0:1] # # P = (x, y) - point of interest # # Let's look at second derivative of quad curve equation: # # Pq''(t) = 2 * (P1 - 2 * Pc + P2) = Pq'' # It's constant vector. # # Let's draw a line through P to be parallel to this # vector and find the intersection of the quad curve # and the line. # # Pq(t) is point of intersection if system of equations # below has the solution. # # L(s) = P + Pq''*s == Pq(t) # Pq''*s + (P - Pq(t)) == 0 # # | xq''*s + (x - xq(t)) == 0 # | yq''*s + (y - yq(t)) == 0 # # This system has the solution if rank of its matrix equals to 1. # That is, determinant of the matrix should be zero. # # (y - yq(t))*xq'' == (x - xq(t))*yq'' # # Let's solve this equation with 't' variable. # Also let kx = x1 - 2*xc + x2 # ky = y1 - 2*yc + y2 # # t0q = (1/2)*((x - x1)*ky - (y - y1)*kx) / # ((xc - x1)*ky - (yc - y1)*kx) # # Let's do the same for our line Pl(t): # # t0l = ((x - x1)*ky - (y - y1)*kx) / # ((x2 - x1)*ky - (y2 - y1)*kx) # # It's easy to check that t0q == t0l. This fact means # we can compute t0 only one time. # # In case t0 < 0 or t0 > 1, we have an intersections outside # of shape bounds. So, P is definitely out of shape. # # In case t0 is inside [0:1], we should calculate Pq(t0) # and Pl(t0). We have three points for now, and all of them # lie on one line. So, we just need to detect, is our point # of interest between points of intersections or not. # # If the denominator in the t0q and t0l equations is # zero, then the points must be collinear and so the # curve is degenerate and encloses no area. Thus the # result is false. kx = x1 - 2 * xc + x2; ky = y1 - 2 * yc + y2; dx = x - x1; dy = y - y1; dxl = x2 - x1; dyl = y2 - y1; t0 = (dx * ky - dy * kx) / (dxl * ky - dyl * kx) return false if (t0 < 0 || t0 > 1 || t0 != t0) xb = kx * t0 * t0 + 2 * (xc - x1) * t0 + x1; yb = ky * t0 * t0 + 2 * (yc - y1) * t0 + y1; xl = dxl * t0 + x1; yl = dyl * t0 + y1; (x >= xb && x < xl) || (x >= xl && x < xb) || (y >= yb && y < yl) || (y >= yl && y < yb) end |
#point_crossings(x_or_point, y = nil, level = 0) ⇒ Object
Calculates the number of times the quad crosses the ray extending to the right from (x,y). If the point lies on a part of the curve, then no crossings are counted for that intersection. the level parameter should be 0 at the top-level call and will count up for each recursion level to prevent infinite recursion +1 is added for each crossing where the Y coordinate is increasing -1 is added for each crossing where the Y coordinate is decreasing
184 185 186 187 188 |
# File 'lib/perfect_shape/quadratic_bezier_curve.rb', line 184 def point_crossings(x_or_point, y = nil, level = 0) x, y = normalize_point(x_or_point, y) return unless x && y QuadraticBezierCurve.point_crossings(points[0][0], points[0][1], points[1][0], points[1][1], points[2][0], points[2][1], x, y, level) end |