Android词云放置算法

词云(WordCloud)是分析数据时一项有趣的展示方式, 它将数据中的关键词按权重设置不同的大小, 放置成一定的形状(比如圆形). 它包括关键词的统计提取和放置, 这里在安卓端实现一个放置词云的View.

Google一下word cloud algorithm词云算法, 这里有介绍
https://stackoverflow.com/questions/342687/algorithm-to-implement-a-word-cloud-like-wordle
主要思想是:

1. 先放权重大的词
2. 放好后就不动
3. 放置时如果跟已放好的词重叠了, 就按照螺旋线向外移动到下一个位置

简单实现

使用自定义ViewGroup实现, 每个关键词用一个TextView表示, 放置到ViewGroup中, 这样的好处是方便处理单个词的样式和事件. 主要就是重写onLayout()方法

@Override
    protected void onLayout(boolean changed, int left, int top, int right, int bottom) {
        int n = getChildCount();
        for(int i = 0; i < n; i++) {
            View v = getChildAt(i);
            if(placed.contains(v)) {
                continue;
            }
            int w = v.getMeasuredWidth();
            int h = v.getMeasuredHeight();

            int pivotX = getWidth() / 3 + random.nextInt(getWidth() / 3);
            int pivotY = getHeight() / 3 + random.nextInt(getHeight() / 3);

            List<Point> spiral = generateSpiral();
            for(Point p : spiral) {
                pivotX += p.x;
                pivotY += p.y;

                Log.d("chao", "place " + pivotX + "," + pivotY);
                Rect r1 = getVisualRect(pivotX, pivotY, w, h, v.getRotation());
                boolean isOverlap = false;
                for(View pv : placed) {
                    Rect r2 = getVisualRect(pv);
                    if(isOverlap(r1, r2)) {
                        isOverlap = true;
                        break;
                    }
                }
                if(isOverlap) {

                } else {
                    Log.d("chao", "placed");
                    Rect r = getRect(pivotX, pivotY, w, h);
                    v.layout(r.left, r.top, r.right, r.bottom);
                    break;
                }
            }
            placed.add(v);
        }
    }

为了同时有水平摆放和垂直摆放, 添加TextView时随机给90度或270度的旋转. 注意虽然TextView旋转了, 但是它的位置属性还是旋转前的, 因此在检测重叠前要转换成旋转后的.

    float[] rotates = {
            0f,90f,270f
    };

    public void addTextView(String word, int weight) {
        TextView tv = new TextView(getContext());
        tv.setText(word);
        tv.setTextSize(weight);
        tv.setRotation(rotates[random.nextInt(rotates.length)]);
        tv.setOnClickListener(this);
        addView(tv, params);
    }

检测两个矩形是否重叠的算法

    public static boolean isOverlap(Rect r1, Rect r2) {
        return r1.right >= r2.left && r2.right >= r1.left
                && r1.bottom >= r2.top && r2.bottom >= r1.top;
    }

这样就实现了, 看一下效果不是很好, 这是因为用的是”直角螺旋线算法”, 即按照左上右下的顺序移动坐标, 距离逐渐增大. 要实现放置成圆形的效果, 需要加入真正的螺旋线算法.

一般数学中没讲过螺旋线, 网上找一下, 写一个生成螺旋线点的算法, 用自定义View验证

public class SpiralView extends View {

    Paint paint;
    List<Point> points;

    public SpiralView(Context context) {
        this(context, null);
    }

    public SpiralView(Context context, @Nullable AttributeSet attrs) {
        this(context, attrs, 0);
    }

    public SpiralView(Context context, @Nullable AttributeSet attrs, int defStyleAttr) {
        super(context, attrs, defStyleAttr);
        paint = new Paint();
        paint.setColor(Color.RED);
        paint.setStyle(Paint.Style.FILL);

        points = generateSpiral();
    }

    @Override
    protected void onDraw(Canvas canvas) {
        int cx = getWidth() / 2;
        int cy = getHeight() / 2;
        for(Point p : points) {
            canvas.drawCircle(cx + p.x, cy + p.y, 5, paint);
        }
    }

    private List<Point> generateSpiral() {
        List<Point> res = new ArrayList<>();
        int A = 10;
        int w = 1;
        double sita = Math.PI;
        for(double t = 0; t < 10 * Math.PI; t+=0.1) {
            int x = Double.valueOf(A * Math.cos(w * t + sita)).intValue();
            int y = Double.valueOf(A * Math.sin(w * t + sita)).intValue();
            A += 1;
            res.add(new Point(x, y));
            Log.e("chao", x + ", " + y);
        }
        return res;
    }
}

在把这个算法加入到onLayout()方法中就大功告成了

@Override
    protected void onLayout(boolean changed, int left, int top, int right, int bottom) {
        int n = getChildCount();
        for(int i = 0; i < n; i++) {
            View v = getChildAt(i);
            if(placed.contains(v)) {
                continue;
            }
            int w = v.getMeasuredWidth();
            int h = v.getMeasuredHeight();

            int pivotX = getWidth() / 3 + random.nextInt(getWidth() / 3);
            int pivotY = getHeight() / 3 + random.nextInt(getHeight() / 3);

            List<Point> spiral = generateSpiral();
            for(Point p : spiral) {
                pivotX += p.x;
                pivotY += p.y;

                Log.d("chao", "place " + pivotX + "," + pivotY);
                Rect r1 = getVisualRect(pivotX, pivotY, w, h, v.getRotation());
                boolean isOverlap = false;
                for(View pv : placed) {
                    Rect r2 = getVisualRect(pv);
                    if(isOverlap(r1, r2)) {
                        isOverlap = true;
                        break;
                    }
                }
                if(isOverlap) {

                } else {
                    Log.d("chao", "placed");
                    Rect r = getRect(pivotX, pivotY, w, h);
                    v.layout(r.left, r.top, r.right, r.bottom);
                    break;
                }
            }
            placed.add(v);
        }
    }

Github地址

https://github.com/rome753/WordCloudView