こんにちは。
スマホアプリをメインに開発している常にハードモードのロッキーです。
今回もかなりニッチな題材となりますが、「Flutterでサークルパッキング」を実装しましたので紹介します。
はじめに
そもそもサークルパッキングとは？と思われる方もいると思うのですが平たく言うと、決められたサイズの中に同じ大きさ、または異なる大きさの円を重ならないように敷き詰めるというものになります。
一見簡単そうな感じなのですが、これがかなりの難問で、数学的観点やアルゴリズムにまで話が及びます。
要件
そして今回実装するにあたり、要件としては以下の通りです。
- 表示するエリアは指定できる。
- 各円のサイズは異なる。
- 各円のサイズは割合を指定できる。
- 各円は重ならない。
シンキングタイム
この要件があったとして、どのようにしたら実装できるかさっぱりわかりませんでしたので、色々調査したのですが、可能性として考えられたのが、
1, 図形のbottom-left法
3, 神降臨
調査した結果、1はまあまあよいとして、2は処理時間の問題でだめという判断です。
今回は冒頭でリンクを貼った「参考サイト」をご覧いただけたらわかるように、やっていることが高度すぎてついていけませんでしたので、3を発動しました。
実装で参考にさせていただいたサイト
もっとググった結果、同じ疑問を持つ方がいました。
そして、神回答しているユーザさんを発見。
JSですがソースコードも公開されていましたので、これをDartに書き直して手を加えました。つまり私はググっただけというのが大体を占めますがそれも技術ということで・・w
実装
ただやっても面白くないので前回に引き続きおすすめプレイリストのサムネイル画像を当て込みました。
|
1 |
spotify: ^0.5.1 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 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 67 68 69 70 71 72 73 74 75 76 77 78 79 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 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 |
import 'dart:math'; import 'package:flutter/material.dart'; import 'package:spotify/spotify.dart' as Spotify; void main() => runApp(MyApp()); class MyApp extends StatelessWidget { @override Widget build(BuildContext context) { return MaterialApp( title: 'Flutter Demo', theme: ThemeData( primarySwatch: Colors.blue, ), home: _MyApp(), ); } } class _MyApp extends StatefulWidget { @override _MyAppState createState() => _MyAppState(); } class _MyAppState extends State<_MyApp> { List<Spotify.Track> _tracks; @override void initState() { _init(); super.initState(); } /// 初期設定 void _init() async { // SpotifyApiを使ってTOPトラック情報を取得する final spotify = Spotify.SpotifyApi( Spotify.SpotifyApiCredentials( "*****", "*****", ), ); final tracks = await spotify.artists.getTopTracks( '5yCWuaBlu42BKsnW89brND', "JP", ); setState(() { _tracks = tracks.toList(); }); } @override Widget build(BuildContext context) { if (_tracks == null) { return Scaffold( body: Container(), ); } final size = MediaQuery.of(context).size; final canvasSize = Size(size.width - 70, 240); final positions = CirclePacking.getCirclePositions( canvasSize, List.generate( _tracks.length, (index) => 5.0 + (Random().nextDouble() * 15.0)), ); final paints = positions .map((position) => _ChartCirclePoints.create(position.radius, position.offset)) .toList(); List<Widget> widgets = []; _tracks.asMap().forEach((index, track) { final position = positions[index]; widgets.add( Positioned( left: position.offset.dx - position.radius, top: position.offset.dy - position.radius, width: position.radius * 2, height: position.radius * 2, child: Container( decoration: BoxDecoration( shape: BoxShape.circle, image: DecorationImage( fit: BoxFit.fill, image: NetworkImage(track.album.images.first.url), ), ), ), ), ); }); return Scaffold( body: Container( color: Colors.white, child: Center( child: Container( width: canvasSize.width, height: canvasSize.height, decoration: BoxDecoration( border: Border.all( color: Colors.black, width: 2.0, )), child: Stack(children: widgets), ), ), ), ); } } /* * Circle Packing */ /// 算出されたデータを描写で必要なデータにするクラス class CirclePacking { /// 各位置データのリストを返す static List<CirclePosition> getCirclePositions( Size size, List<double> percents, ) { final packer = _Packer( percents, ratio: size.width / size.height, ); final circles = packer.createCircles(); final marginFactor = 0.1; final mx = size.width * marginFactor / 2; final my = size.height * marginFactor / 2; final dx = packer.width / 2; final dy = packer.height / 2; final zx = size.width * (1 - marginFactor) / packer.width; final zy = size.height * (1 - marginFactor) / packer.height; final zoom = zx < zy ? zx : zy; final positions = circles .map((c) => CirclePosition( Offset( (c.center.x + dx) * zoom + mx, (c.center.y + dy) * zoom + my), c.radius * zoom, )) .toList(); return positions; } } /// 位置データ class CirclePosition { const CirclePosition( this.offset, this.radius, ); final Offset offset; final double radius; } /* * Circle Packing Logic */ /// サークルパッキング算出ロジック class _Packer { _Packer( this.radiuses, { this.ratio = 1.0, }); final List<double> radiuses; final double ratio; double width; double height; double bounding; List<_Circle> createCircles() { var surface = .0; for (var i = 0; i < this.radiuses.length; i++) { surface += pi * pow(this.radiuses[i], 2); } final limit = surface / 1000; var step = surface / 2; List<_Circle> res = []; while (step > limit) { final placement = _compute(surface); if (placement.length != radiuses.length) { surface += step; } else { res = placement; surface -= step; } step /= 2; } return res; } List<_Circle> _compute(double surface) { bounding = sqrt(surface) * 100; width = sqrt(surface * ratio); height = width / ratio; List<_Circle> placed = [ _boundingCircle(1, 1, 1, -1), _boundingCircle(1, -1, -1, -1), _boundingCircle(-1, -1, -1, 1), _boundingCircle(-1, 1, 1, 1) ]; var unplaced = [...radiuses]; while (unplaced.length > 0) { Map<int, double> lambda = {}; Map<int, _Circle> circle = {}; for (var i = 0; i < unplaced.length; i++) { var min = 1e10; lambda[i] = -1e10; for (var j = 0; j < placed.length; j++) for (var k = j + 1; k < placed.length; k++) { final corners = _corner(unplaced[i], placed[j], placed[k]); for (var c = 0; c != corners.length; c++) { var minDistance = 1e10; var l = 0; for (l = 0; l != placed.length; l++) { if (l == j || l == k) continue; final d = placed[l].distance(corners[c]); if (d < 0) break; if (d < minDistance) minDistance = d; } if (l == placed.length) { if (minDistance < min) { min = minDistance; lambda[i] = 1 - minDistance / unplaced[i]; circle[i] = corners[c]; } } } } } var max = -1e10; var maxValue = -1; for (var i = 0; i < unplaced.length; i++) { if (i < lambda.length && lambda[i] > max) { max = lambda[i]; maxValue = i; } } if (maxValue == -1) break; unplaced.removeAt(maxValue); placed.add(circle[maxValue]); } placed.removeRange(0, 4); return placed; } bool _isInRect(double radius, _Point center) { if (center.x - radius < -width / 2) return false; if (center.x + radius > width / 2) return false; if (center.y - radius < -height / 2) return false; if (center.y + radius > height / 2) return false; return true; } _Circle _boundingCircle(double x0, double y0, double x1, double y1) { final xm = ((x1 - x0) * width).abs(); final ym = ((y1 - y0) * height).abs(); final m = xm > ym ? xm : ym; final theta = asin(m / 4 / bounding); final r = bounding * cos(theta); return _Circle( bounding, _Point(r * (y0 - y1) / 2 + (x0 + x1) * width / 4, r * (x1 - x0) / 2 + (y0 + y1) * height / 4), ); } List<_Circle> _corner(double radius, _Circle c1, _Circle c2) { var u = c1.center.vect(c2.center); final a = u.norm(); if (a == 0) return []; u = u.mult(1 / a); final b = c1.radius + radius; final c = c2.radius + radius; if (a > (b + c)) return []; final x = (a + (b * b - c * c) / a) / 2; final y = sqrt(b * b - x * x); final base = c1.center.add(u.mult(x)); List<_Circle> res = []; final p1 = _Point(base.x - u.y * y, base.y + u.x * y); final p2 = _Point(base.x + u.y * y, base.y - u.x * y); if (_isInRect(radius, p1)) res.add(_Circle(radius, p1)); if (_isInRect(radius, p2)) res.add(_Circle(radius, p2)); return res; } } class _Point { _Point( this.x, this.y, ); final double x; final double y; _Point mult(double a) { return _Point(x * a, y * a); } _Point add(_Point p) { return _Point(x + p.x, y + p.y); } double norm() { return sqrt(x * x + y * y); } _Point vect(_Point p) { return _Point(p.x - x, p.y - y); } double dist(_Point p) { return vect(p).norm(); } } class _Circle { _Circle( this.radius, this.center, ); final double radius; final _Point center; double surface() { return pi * radius * radius; } double distance(_Circle circle) { return center.dist(circle.center) - radius - circle.radius; } } class _ChartCirclePoints extends CustomPainter { static Widget create( double radius, Offset offset, ) { return CustomPaint( painter: _ChartCirclePoints( radius, offset, ), ); } const _ChartCirclePoints( this.radius, this.offset, ); final double radius; final Offset offset; @override void paint(Canvas canvas, Size size) { final paint = Paint() ..color = Colors.blue ..style = PaintingStyle.stroke ..strokeCap = StrokeCap.round ..strokeWidth = 2.0; canvas.drawCircle(offset, radius, paint); } @override bool shouldRepaint(CustomPainter oldDelegate) => false; } |
_MyAppStateのbuild関数内のpaintsをstackのchildlenに与えるとデバッグドローが表示されます。
最後に
今回の内容は、全く必要にならない可能性もありますが、一見単純な内容と思いきや、割と高度ということと、日本語はもとより英語サイトでもあまり記事がなかったので、誰かの役にたつのではと思い記事にしました。
最後におすすめプレイリストはこちらです。
ABOUT ME
