もくじ
こんにちは。
スマホアプリをメインに開発している常にハードモードのロッキーです。
今回もかなりニッチな題材となりますが、「Flutterでサークルパッキング」を実装しましたので紹介します。
はじめに
そもそもサークルパッキングとは？と思われる方もいると思うのですが平たく言うと、決められたサイズの中に同じ大きさ、または異なる大きさの円を重ならないように敷き詰めるというものになります。
一見簡単そうな感じなのですが、これがかなりの難問で、数学的観点やアルゴリズムにまで話が及びます。
要件
そして今回実装するにあたり、要件としては以下の通りです。
- 表示するエリアは指定できる。
- 各円のサイズは異なる。
- 各円のサイズは割合を指定できる。
- 各円は重ならない。
シンキングタイム
この要件があったとして、どのようにしたら実装できるかさっぱりわかりませんでしたので、色々調査したのですが、可能性として考えられたのが、
1, 図形のbottom-left法
3, 神降臨
調査した結果、1はまあまあよいとして、2は処理時間の問題でだめという判断です。
今回は冒頭でリンクを貼った「参考サイト」をご覧いただけたらわかるように、やっていることが高度すぎてついていけませんでしたので、3を発動しました。
実装で参考にさせていただいたサイト
もっとググった結果、同じ疑問を持つ方がいました。
そして、神回答しているユーザさんを発見。
JSですがソースコードも公開されていましたので、これをDartに書き直して手を加えました。つまり私はググっただけというのが大体を占めますがそれも技術ということで・・w
実装
ただやっても面白くないので前回に引き続きおすすめプレイリストのサムネイル画像を当て込みました。
spotify: ^0.5.1import '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に与えるとデバッグドローが表示されます。
最後に
今回の内容は、全く必要にならない可能性もありますが、一見単純な内容と思いきや、割と高度ということと、日本語はもとより英語サイトでもあまり記事がなかったので、誰かの役にたつのではと思い記事にしました。
最後におすすめプレイリストはこちらです。
