概要

YMTreeMap 是适用于 iOS 和 macOS 的高性能树状图布局引擎，用 Swift 编写。

YMTreeMap 的输入是任意数字的列表，输出将是以图形方式表示这些数字的布局矩形列表。布局矩形的顺序将与原始输入顺序匹配，因此应按照树状图的排序方式对输入数字进行排序。最后，布局矩形的大小将表示它响应的序号输入编号的相对权重。

YMTreeMap 使用“方形”布局树状图算法。方形优化了低纵横比：这意味着在合理的努力下，它会生成尽可能正方形的矩形。虽然不是完美的最佳算法，但在保持高性能的同时，该算法非常接近。

输出矩形可用于使用您喜欢的任何渲染系统轻松渲染形状：

• 使用CoreGraphics（在drawRect等中）
• 使用 OpenGL
• 使用自定义 UI 联机视图布局

用法

如何在 Swift 和 Objective-C 中使用随机颜色绘制小热图的基本示例。

迅速

var randomColor: UIColor {
  return UIColor(red: CGFloat(arc4random_uniform(255) % 255) / 255.0,
                 green: CGFloat(arc4random_uniform(255) % 255) / 255.0,
                 blue: CGFloat(arc4random_uniform(255) % 255) / 255.0,
                 alpha: 1)
}

override func draw(_ rect: CGRect) {
  let values = [ 445, 203, 110, 105, 95, 65, 33, 21, 10 ].sorted()

  // These two lines are actual YMTreeMap usage!
  let treeMap = YMTreeMap(withValues: values)
  let treeMapRects = treeMap.tessellate(inRect: self.bounds)

  let context = UIGraphicsGetCurrentContext()

  treeMapRects.forEach { (treeMapRect) in
    randomColor.setFill()
    context?.fill(treeMapRect)
  }
}

Objective-C

#define RANDOM_COLOR [UIColor colorWithRed:(rand() % 255)/255.0 green:(rand() % 255)/255.0 blue:(rand() % 255)/255.0 alpha:1.0]

- (void)drawRect:(CGRect)rect
{
    NSArray<NSNumber *> *values = @[ @445, @203, @110, @105, @95, @65, @33, @21, @10 ];

    // These two lines are actual YMTreeMap usage!
    YMTreeMap *tm = [[YMTreeMap alloc] initWithValues:values];
    NSArray<NSValue *> *treeMapRects = [tm tessellateInRect:rect];

    CGContextRef context = UIGraphicsGetCurrentContext();

    for (NSValue *rectVal in treeMapRects) {
        [RANDOM_COLOR setFill];
        CGContextFillRect(context, rectVal.CGRectValue);
    }
}

Examples

Here are examples of 30-item and 1000-item sorted treemaps in a verical-orientation.

Performance

Tests performed on-device after 3 seconds of idle time, in release configuration. All tests use the same input values, which were sorted lists of large integers.

Even with heat maps with up to 1,000 items, layout time is well controlled at 3.7ms. This should
enable use within a scrolling table view.

Pure Swift

iPhone 7 Plus

• [30 items ] Performed 1000 iterations in 114.331625ms; 8.746486/ms; 0.114332ms each
• [1000 items] Performed 1000 iterations in 3743.449875ms; 0.267133/ms; 3.743450ms each

Objective-C bridging into Swift

iPhone 7 Plus

• [30 items ] Performed 1000 iterations in 132.439167ms; 7.550636/ms; 0.132439ms each
• [1000 items] Performed 1000 iterations in 4493.055292ms; 0.222566/ms; 4.493055ms each

Example

To run the example project, clone the repo, and run from the Example directory first.pod install

Requirements

Installation

YMTreeMap is available through CocoaPods. To install
it, simply add the following line to your Podfile:

pod 'YMTreeMap'

Further Reading

Various papers on treemapping layout algorithms and usability that helped influence this project. A copy of each paper is in the Research folder.

Squarified Treemaps - Mark Bruls, Kees Huizing, Jarke J. van Wijk

Ordered Treemap Layouts - Ben Shneiderman, Martin Wattenberg

Ordered and Quantum Treemaps: Making Effective Use of 2D Space to Display Hierarchies - Benjamin B. Bederson, Ben Shneiderman, Martin Wattenberg

Treemaps for space-constrained visualization of hierarchies - Ben Shneiderman

Treemapping on Wikipedia

Animated Exploration of Dynamic Graphs with Radial Layout - Ka-Ping Yee, Danyel Fisher, Rachna Dhamija, Marti Hearst

Author

Adam Kaplan, adamkaplan@oath.com

License

YMTreeMap is available under the MIT license. See the LICENSE file for more info.

GitHub

https://github.com/yahoo/YMTreeMap