SVG Intersection Test
-
Description

Purpose of this page is to simplify testing and debugging of some SVG related javascript libraries (see Libraries).
  • Drag shapes around to change intersections (should work on mobiles too).
  • 'Intersections' button under each sample recalculates intersections for that sample (useful for debugging).
  • Click sample Link to open test page with just that sample.
  • Tip: zoom in/out browser view (ctrl+ / ctrl- or ctrl mouse wheel).
  • Tip: orange button (top right) minimizes Description panel.

Changes:

v1.07 [2015-03-29]
Speed optimizations:
  • Added Speed test functionality/button. Intersection method is run on sample for 5 seconds. Average time is estimate of one method execution duration, in milliseconds. Result is displayed in alert window and logged in console.
  • Object.defineProperties is slow. when number of created Vector2D, Point2D and Matrix2D objects is high, like in calculating SVG intersections (multiplying, adding etc. creates new object), intersection calculation can be drastically faster when not using Object.defineProperties i.e. on my test machine, average calculation time of two test shapes intersections dropped
    • from ~3.5ms to ~0.54ms in Firefox
    • from ~5.35ms to ~0.65ms in Chrome
    • from ~11.25ms to ~6.3ms in IE11
  • Additionally, in Polynomial:
    • getRootsInInterval is implemented with newton_secant_bisection
    • fujiwara bounds calculation now reuses helper arrays
    • call to Math.pow in zeroErrorEstimate is circumvented
    • isNaN call in eval is avoided (it's a little slow in IE)
    Average times achieved after optimizations:
    • ~0.5ms in Firefox
    • ~0.5ms in Chrome
    • ~0.64ms in IE11 (~3.7ms when Developer Tools are open)
  • Mentioned test results are from Speed test applied on last sample with two paths in stretched SVG with viewBox.
v1.06 [2015-03-14]
  • Implemented support for intersections of elements that each have their own transformation matrix. In other words, rotated/scaled/skewed elements can be intersected.
  • Removed circle intersection methods - using ellipse methods instead.
  • Removed double Polygon/Polynomial/Rectangle intersections on successive segments mutual point.
  • Added workspace with just special cases of ellipse/ellipse intersections.
  • Multiple improvements/bugs resolved.
v1.05 [2015-03-05]
  • Some code changes uploaded at http://github.com/Quazistax. For latest changes look in dev branches of kld forks.
  • Default polynomial algorithm is kld\newton.
  • Removal of multiplicated intersection points.
    • In Bezier3/Bezier3, Bezier3/Bezier2, Bezier3/Ellipse; removal of same multiple roots.
    • Removed double Path intersections on successive segments mutual point.
  • intersectEllipseLine: handling of small errors resulting in missing border-case intersections.
  • getQuarticRoots(newton) bug solved: copy/paste mistake, resulting in NaN root.
  • Added intersections for rounded rectangle, reworked rectangle/polyline/polygon intersections to one lines intersection method.
  • intersectEllipseEllipse: solved bug when eliminating multiple intersections in result of 3 points.
v1.04 [2015-03-03]
  • Newton method enhanced with secant and bisection fallbacks = better convergence.
  • Polynomial extension: root lower and upper bounds calculation methods (Fujiwara, Rouche, Laguerre), Descartes rule of signs
  • getQuarticRoots(newton) changes: Fujiwara bounds calculation, calculation of near-zero error value
  • Improved detection of multiple (identical) points in ellipse/ellipse intersections.
  • Handling of possible root error that could lead to miss intersection in ellipse/ellipse intersections.
v1.03
  • Added dynamic Link for each sample. Link updates at the end of shape-drag operation.
    Link stores shape attributes in url parameters, so you can save modified or create new shape combinations, as links.
    • sh1 and sh2 are names of shape 1 and 2 (one of: line, rect, circle, ellipse, polyline, polygon, path).
    • ats1 and ats2 are attribute strings of shape elements 1 and 2.
    • caption is text written in sample window.
    Settings (radio&check boxes states) are not preserved in Link.
v1.02
  • Newton method development complete. (for use for finding quartic polynomial roots)
  • Added description and changelog.
  • Some UI changes.

Libraries:

Other:

Recalculate intersections
On settings change
On moving shape
On moved shape
Polynomial algorithm
kld
rpoly
kld / newton for quartic
Bisection accuracy
6
15
Other
Use improved algorithm
for ellipse/ellipse