labelling.go

Documentation: gonum.org/v1/plot

     1  // Copyright ©2017 The Gonum Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // This is an implementation of the Talbot, Lin and Hanrahan algorithm
     6  // described in doi:10.1109/TVCG.2010.130 with reference to the R
     7  // implementation in the labeling package, ©2014 Justin Talbot (Licensed
     8  // MIT+file LICENSE|Unlimited).
     9  
    10  package plot
    11  
    12  import (
    13  	"math"
    14  )
    15  
    16  const (
    17  	// dlamchE is the machine epsilon. For IEEE this is 2^{-53}.
    18  	dlamchE = 1.0 / (1 << 53)
    19  
    20  	// dlamchB is the radix of the machine (the base of the number system).
    21  	dlamchB = 2
    22  
    23  	// dlamchP is base * eps.
    24  	dlamchP = dlamchB * dlamchE
    25  )
    26  
    27  const (
    28  	// free indicates no restriction on label containment.
    29  	free = iota
    30  	// containData specifies that all the data range lies
    31  	// within the interval [label_min, label_max].
    32  	containData
    33  	// withinData specifies that all labels lie within the
    34  	// interval [dMin, dMax].
    35  	withinData
    36  )
    37  
    38  // talbotLinHanrahan returns an optimal set of approximately want label values
    39  // for the data range [dMin, dMax], and the step and magnitude of the step between values.
    40  // containment is specifies are guarantees for label and data range containment, valid
    41  // values are free, containData and withinData.
    42  // The optional parameters Q, nice numbers, and w, weights, allow tuning of the
    43  // algorithm but by default (when nil) are set to the parameters described in the
    44  // paper.
    45  // The legibility function allows tuning of the legibility assessment for labels.
    46  // By default, when nil, legbility will set the legibility score for each candidate
    47  // labelling scheme to 1.
    48  // See the paper for an explanation of the function of Q, w and legibility.
    49  func talbotLinHanrahan(dMin, dMax float64, want int, containment int, Q []float64, w *weights, legibility func(lMin, lMax, lStep float64) float64) (values []float64, step, q float64, magnitude int) {
    50  	const eps = dlamchP * 100
    51  
    52  	if dMin > dMax {
    53  		panic("labelling: invalid data range: min greater than max")
    54  	}
    55  
    56  	if Q == nil {
    57  		Q = []float64{1, 5, 2, 2.5, 4, 3}
    58  	}
    59  	if w == nil {
    60  		w = &weights{
    61  			simplicity: 0.25,
    62  			coverage:   0.2,
    63  			density:    0.5,
    64  			legibility: 0.05,
    65  		}
    66  	}
    67  	if legibility == nil {
    68  		legibility = unitLegibility
    69  	}
    70  
    71  	if r := dMax - dMin; r < eps {
    72  		l := make([]float64, want)
    73  		step := r / float64(want-1)
    74  		for i := range l {
    75  			l[i] = dMin + float64(i)*step
    76  		}
    77  		magnitude = minAbsMag(dMin, dMax)
    78  		return l, step, 0, magnitude
    79  	}
    80  
    81  	type selection struct {
    82  		// n is the number of labels selected.
    83  		n int
    84  		// lMin and lMax are the selected min
    85  		// and max label values. lq is the q
    86  		// chosen.
    87  		lMin, lMax, lStep, lq float64
    88  		// score is the score for the selection.
    89  		score float64
    90  		// magnitude is the magnitude of the
    91  		// label step distance.
    92  		magnitude int
    93  	}
    94  	best := selection{score: -2}
    95  
    96  outer:
    97  	for skip := 1; ; skip++ {
    98  		for _, q := range Q {
    99  			sm := maxSimplicity(q, Q, skip)
   100  			if w.score(sm, 1, 1, 1) < best.score {
   101  				break outer
   102  			}
   103  
   104  			for have := 2; ; have++ {
   105  				dm := maxDensity(have, want)
   106  				if w.score(sm, 1, dm, 1) < best.score {
   107  					break
   108  				}
   109  
   110  				delta := (dMax - dMin) / float64(have+1) / float64(skip) / q
   111  
   112  				const maxExp = 309
   113  				for mag := int(math.Ceil(math.Log10(delta))); mag < maxExp; mag++ {
   114  					step := float64(skip) * q * math.Pow10(mag)
   115  
   116  					cm := maxCoverage(dMin, dMax, step*float64(have-1))
   117  					if w.score(sm, cm, dm, 1) < best.score {
   118  						break
   119  					}
   120  
   121  					fracStep := step / float64(skip)
   122  					kStep := step * float64(have-1)
   123  
   124  					minStart := (math.Floor(dMax/step) - float64(have-1)) * float64(skip)
   125  					maxStart := math.Ceil(dMax/step) * float64(skip)
   126  					for start := minStart; start <= maxStart && start != start-1; start++ {
   127  						lMin := start * fracStep
   128  						lMax := lMin + kStep
   129  
   130  						switch containment {
   131  						case containData:
   132  							if dMin < lMin || lMax < dMax {
   133  								continue
   134  							}
   135  						case withinData:
   136  							if lMin < dMin || dMax < lMax {
   137  								continue
   138  							}
   139  						case free:
   140  							// Free choice.
   141  						}
   142  
   143  						score := w.score(
   144  							simplicity(q, Q, skip, lMin, lMax, step),
   145  							coverage(dMin, dMax, lMin, lMax),
   146  							density(have, want, dMin, dMax, lMin, lMax),
   147  							legibility(lMin, lMax, step),
   148  						)
   149  						if score > best.score {
   150  							best = selection{
   151  								n:         have,
   152  								lMin:      lMin,
   153  								lMax:      lMax,
   154  								lStep:     float64(skip) * q,
   155  								lq:        q,
   156  								score:     score,
   157  								magnitude: mag,
   158  							}
   159  						}
   160  					}
   161  				}
   162  			}
   163  		}
   164  	}
   165  
   166  	if best.score == -2 {
   167  		l := make([]float64, want)
   168  		step := (dMax - dMin) / float64(want-1)
   169  		for i := range l {
   170  			l[i] = dMin + float64(i)*step
   171  		}
   172  		magnitude = minAbsMag(dMin, dMax)
   173  		return l, step, 0, magnitude
   174  	}
   175  
   176  	l := make([]float64, best.n)
   177  	step = best.lStep * math.Pow10(best.magnitude)
   178  	for i := range l {
   179  		l[i] = best.lMin + float64(i)*step
   180  	}
   181  	return l, best.lStep, best.lq, best.magnitude
   182  }
   183  
   184  // minAbsMag returns the minumum magnitude of the absolute values of a and b.
   185  func minAbsMag(a, b float64) int {
   186  	return int(math.Min(math.Floor(math.Log10(math.Abs(a))), (math.Floor(math.Log10(math.Abs(b))))))
   187  }
   188  
   189  // simplicity returns the simplicity score for how will the curent q, lMin, lMax,
   190  // lStep and skip match the given nice numbers, Q.
   191  func simplicity(q float64, Q []float64, skip int, lMin, lMax, lStep float64) float64 {
   192  	const eps = dlamchP * 100
   193  
   194  	for i, v := range Q {
   195  		if v == q {
   196  			m := math.Mod(lMin, lStep)
   197  			v = 0
   198  			if (m < eps || lStep-m < eps) && lMin <= 0 && 0 <= lMax {
   199  				v = 1
   200  			}
   201  			return 1 - float64(i)/(float64(len(Q))-1) - float64(skip) + v
   202  		}
   203  	}
   204  	panic("labelling: invalid q for Q")
   205  }
   206  
   207  // maxSimplicity returns the maximum simplicity for q, Q and skip.
   208  func maxSimplicity(q float64, Q []float64, skip int) float64 {
   209  	for i, v := range Q {
   210  		if v == q {
   211  			return 1 - float64(i)/(float64(len(Q))-1) - float64(skip) + 1
   212  		}
   213  	}
   214  	panic("labelling: invalid q for Q")
   215  }
   216  
   217  // coverage returns the coverage score for based on the average
   218  // squared distance between the extreme labels, lMin and lMax, and
   219  // the extreme data points, dMin and dMax.
   220  func coverage(dMin, dMax, lMin, lMax float64) float64 {
   221  	r := 0.1 * (dMax - dMin)
   222  	max := dMax - lMax
   223  	min := dMin - lMin
   224  	return 1 - 0.5*(max*max+min*min)/(r*r)
   225  }
   226  
   227  // maxCoverage returns the maximum coverage achievable for the data
   228  // range.
   229  func maxCoverage(dMin, dMax, span float64) float64 {
   230  	r := dMax - dMin
   231  	if span <= r {
   232  		return 1
   233  	}
   234  	h := 0.5 * (span - r)
   235  	r *= 0.1
   236  	return 1 - (h*h)/(r*r)
   237  }
   238  
   239  // density returns the density score which measures the goodness of
   240  // the labelling density compared to the user defined target
   241  // based on the want parameter given to talbotLinHanrahan.
   242  func density(have, want int, dMin, dMax, lMin, lMax float64) float64 {
   243  	rho := float64(have-1) / (lMax - lMin)
   244  	rhot := float64(want-1) / (math.Max(lMax, dMax) - math.Min(dMin, lMin))
   245  	if d := rho / rhot; d >= 1 {
   246  		return 2 - d
   247  	}
   248  	return 2 - rhot/rho
   249  }
   250  
   251  // maxDensity returns the maximum density score achievable for have and want.
   252  func maxDensity(have, want int) float64 {
   253  	if have < want {
   254  		return 1
   255  	}
   256  	return 2 - float64(have-1)/float64(want-1)
   257  }
   258  
   259  // unitLegibility returns a default legibility score ignoring label
   260  // spacing.
   261  func unitLegibility(_, _, _ float64) float64 {
   262  	return 1
   263  }
   264  
   265  // weights is a helper type to calcuate the labelling scheme's total score.
   266  type weights struct {
   267  	simplicity, coverage, density, legibility float64
   268  }
   269  
   270  // score returns the score for a labelling scheme with simplicity, s,
   271  // coverage, c, density, d and legibility l.
   272  func (w *weights) score(s, c, d, l float64) float64 {
   273  	return w.simplicity*s + w.coverage*c + w.density*d + w.legibility*l
   274  }
   275
View as plain text