FastClip removes all segments that are completely outside the given clipping rectangle. To ensure that the removal doesn't cause a segment to cross the rectangle from the outside, it keeps points that cross at least two lines to infinity along the rectangle's edges. This is much quicker (along O(n))
(x0, y0, x1, y1 float64)
| 296 | // FastClip removes all segments that are completely outside the given clipping rectangle. To ensure that the removal doesn't cause a segment to cross the rectangle from the outside, it keeps points that cross at least two lines to infinity along the rectangle's edges. This is much quicker (along O(n)) than using p.And(canvas.Rectangle(x1-x0, y1-y0).Translate(x0, y0)) (which is O(n log n)). |
| 297 | // TODO: what's the difference with Clip? Can we remove one in favor of the other? |
| 298 | func (p *Path) FastClip(x0, y0, x1, y1 float64) *Path { |
| 299 | if x1 < x0 { |
| 300 | x0, x1 = x1, x0 |
| 301 | } |
| 302 | if y1 < y0 { |
| 303 | y0, y1 = y1, y0 |
| 304 | } |
| 305 | rect := Rect{x0, y0, x1, y1} |
| 306 | |
| 307 | // don't reuse memory since the new path may be much smaller and keep the extra capacity |
| 308 | q := &Path{} |
| 309 | if len(p.d) <= 4 { |
| 310 | return q |
| 311 | } |
| 312 | |
| 313 | // Note that applying AND to multiple Cohen-Sutherland outcodes will give us whether all points are left/right and/or above/below |
| 314 | // the rectangle. |
| 315 | var first, start, prev Point |
| 316 | var pendingMoveTo bool |
| 317 | var startOutcode int |
| 318 | var outcodes int // cumulative of removed segments |
| 319 | var closed bool |
| 320 | for i := 0; i < len(p.d); { |
| 321 | cmd := p.d[i] |
| 322 | i += cmdLen(cmd) |
| 323 | |
| 324 | end := Point{p.d[i-3], p.d[i-2]} |
| 325 | if cmd == MoveToCmd { |
| 326 | startOutcode = cohenSutherlandOutcode(rect, end, 0.0) |
| 327 | outcodes = startOutcode |
| 328 | start = end |
| 329 | pendingMoveTo = true |
| 330 | |
| 331 | // TODO: use new path format that encodes if closed at the beginning |
| 332 | closed = false |
| 333 | for j := i; j < len(p.d); { |
| 334 | cmd := p.d[j] |
| 335 | j += cmdLen(cmd) |
| 336 | if cmd == MoveToCmd { |
| 337 | break |
| 338 | } else if cmd == CloseCmd { |
| 339 | closed = true |
| 340 | break |
| 341 | } |
| 342 | } |
| 343 | continue |
| 344 | } |
| 345 | |
| 346 | endOutcode := cohenSutherlandOutcode(rect, end, 0.0) |
| 347 | outcodes &= endOutcode |
| 348 | switch cmd { |
| 349 | case QuadToCmd: |
| 350 | outcodes &= cohenSutherlandOutcode(rect, Point{p.d[i-5], p.d[i-4]}, 0.0) |
| 351 | case CubeToCmd: |
| 352 | outcodes &= cohenSutherlandOutcode(rect, Point{p.d[i-7], p.d[i-6]}, 0.0) |
| 353 | outcodes &= cohenSutherlandOutcode(rect, Point{p.d[i-5], p.d[i-4]}, 0.0) |
| 354 | case ArcToCmd: |
| 355 | rx, ry, phi := p.d[i-7], p.d[i-6], p.d[i-5] |