마인드맵에서 각 노드를 추가/제거하는 작업을 할 때마다 자동으로 노드의 위치가 정해지는 알고리즘이 필요했고, 이 부분을 작업하게 되었다.

어떤 방법으로 정렬이 되어야할까?

다른 마인드맵에서 노드를 추가해보며 어떤식으로 동작이 되어야할지를 관찰했다.

자식노드가 한개일때
- 노드들이 일자로 정렬이 되어야 한다.
화면 기록 2023-12-06 오후 3.13.48.mov
노드의 크기가 늘어날 때
- 자식노드들도 크기가 늘어난 노드의 중앙에 위치하도록 같이 위치가 바뀌어야 한다.
- 세로로 늘어날 경우, 같은 깊이의 다른 노드들도 조금씩 밑 또는 위로 밀려난다.
- 가로로 늘어날 경우, 자식노드들의 위치도 오른쪽으로 같이 이동해야한다.
자식노드가 여러개가 되었을 때
- 자식 노드가 여러개가 되면 자식노드들끼리 서로의 크기에 맞춰 정렬이 되어야한다.
- 노드의 위치는 하위 자식 노드들의 크기를 모두 고려해서 결정해야한다.

알고리즘 구현

그래서 마인드맵 정렬을 위해선

자식 노드들의 최대 높이가 얼마인지를 구한다.
최대높이를 구하면 (현재위치의 y좌표) + 최대높이 / 2 의 값이 자식 노드가 그려지기 시작하는 좌표이다.
해당 호출을 head node에서부터 재귀적으로 반복하도록 하면 마인드맵을 정렬할 수 있다.

초기 구현

measureChildHeight: verticalSpacing을 고려해 최대 자식 높이를 구해주는 함수
arrageNode: 재귀적으로 호출되며 노드를 정렬하는 함수
1. measureChildHeight 함수를 이용해 자식노드의 최대 크기를 측정한다.
2. criteriaX : 자식노드들끼리는 x 좌표 시작 선이 같아야 한다. 이 기준점이다.
3. startX, startY : 실제 자식노드들의 중심좌표를 나타낸다.
  1. startX 값을 구하는 법 : 초기값을 criteriaX 에서 너비 / 2 만큼 더해준 값으로 설정한다.
  2. startY 값을 구하는 법 : 자식이 여러개 있을 때, 위에서 부터 아래로 그려지도록 해야한다. ⇒ 높이 + verticcalSpacing 만큼 값을 증가시켜준다.

class MindmapRightLayoutManager {
    private val horizontalSpacing = Dp(50f)
    private val verticalSpacing = Dp(50f)

    fun arrangeNode(node: Node): Node {
        val childHeightSum = measureChildHeight(node)
        val newNodes = mutableListOf<RectangleNode>()

        val nodeWidth = when (node) {
            is RectangleNode -> node.path.width
            is CircleNode -> node.path.radius
        }

        val criteriaX = node.path.centerX + nodeWidth + horizontalSpacing
        var startX: Dp
        var startY = node.path.centerY - (childHeightSum / 2)

        node.nodes.forEach { childNode ->
            startX = criteriaX + (childNode.path.width / 2)

            val childHeight = measureChildHeight(childNode)
            val newCenterY = startY + (childHeight / 2)
            val newPath = childNode.path.copy(centerX = startX, centerY = newCenterY)

            newNodes.add(
                childNode.copy(path = newPath),
            )

            startY += childHeight + verticalSpacing
        }

        newNodes.forEachIndexed { index, childNode ->
            newNodes[index] = arrangeNode(childNode) as RectangleNode
        }

        val newNode = when (node) {
            is RectangleNode -> node.copy(nodes = newNodes)
            is CircleNode -> node.copy(nodes = newNodes)
        }

        return newNode
    }

    private fun measureChildHeight(node: Node): Dp {
        var heightSum = Dp(0f)

        if (node.nodes.isNotEmpty()) {
            node.nodes.forEach { childNode ->
                heightSum += measureChildHeight(childNode)
            }
            heightSum += verticalSpacing * (node.nodes.size - 1)
        } else {
            heightSum = when (node) {
                is CircleNode -> node.path.radius
                is RectangleNode -> node.path.height
            }
        }

        return heightSum
    }
}

Head의 위치 옮기기

class MindMapRightLayoutManager {
    private val horizontalSpacing = Dp(50f)
    private val verticalSpacing = Dp(50f)

    fun arrangeNode(head: CircleNode): Node {
        val totalHeight = measureChildHeight(head)
        var newHead = head
        if (head.path.centerX.dpVal <= (totalHeight / 2).dpVal) {
            val newPath =
                head.path.copy(
                    centerY = totalHeight / 2 + horizontalSpacing,
                )
            newHead = newHead.copy(path = newPath)
        }
        return recurArrangeNode(newHead)
    }

    private fun recurArrangeNode(node: Node): Node {
        val childHeightSum = measureChildHeight(node)
        val newNodes = mutableListOf<RectangleNode>()

        val nodeWidth =
            when (node) {
                is RectangleNode -> node.path.width
                is CircleNode -> node.path.radius
            }

        val criteriaX = node.path.centerX + nodeWidth / 2 + horizontalSpacing
        var startX: Dp
        var startY = node.path.centerY - (childHeightSum / 2)

        node.nodes.forEach { childNode ->
            startX = criteriaX + (childNode.path.width / 2)

            val childHeight = measureChildHeight(childNode)
            val newY = startY + (childHeight / 2)
            val newPath = childNode.path.copy(centerX = startX, centerY = newY)

            newNodes.add(
                childNode.copy(path = newPath),
            )

            startY += childHeight + verticalSpacing
        }

        newNodes.forEachIndexed { index, childNode ->
            newNodes[index] = recurArrangeNode(childNode) as RectangleNode
        }
        val newNode =
            when (node) {
                is RectangleNode -> node.copy(nodes = newNodes)
                is CircleNode -> {
                    node.copy(
                        nodes = newNodes,
                    )
                }
            }

        return newNode
    }

    fun measureChildHeight(node: Node): Dp {
        var heightSum = Dp(0f)

        if (node.nodes.isNotEmpty()) {
            node.nodes.forEach { childNode ->
                heightSum += measureChildHeight(childNode)
            }
            heightSum += verticalSpacing * (node.nodes.size - 1)
        } else {
            heightSum =
                when (node) {
                    is CircleNode -> node.path.radius
                    is RectangleNode -> node.path.height
                }
        }

        return heightSum
    }
}

자료구조 변경 후 적용

class MindMapRightLayoutManager {
    private val horizontalSpacing = Dp(50f)
    private val verticalSpacing = Dp(50f)

    fun arrangeNode(tree: Tree) {
        val root = tree.getRootNode()
        val totalHeight = measureChildHeight(root, tree)
        val newHead =
            if (root.path.centerX.dpVal <= (totalHeight / 2).dpVal) {
                val newPath =
                    root.path.copy(
                        centerY = totalHeight / 2 + horizontalSpacing,
                    )
                root.copy(path = newPath)
            } else {
                root
            }
        tree.setRootNode(newHead)
        recurArrangeNode(newHead, tree)
    }

    private fun recurArrangeNode(
        currentNode: Node,
        tree: Tree,
    ) {
        val childHeightSum = measureChildHeight(currentNode, tree)

        val nodeWidth =
            when (currentNode) {
                is RectangleNode -> currentNode.path.width
                is CircleNode -> currentNode.path.radius
            }

        val criteriaX = currentNode.path.centerX + nodeWidth / 2 + horizontalSpacing
        var startX: Dp
        var startY = currentNode.path.centerY - (childHeightSum / 2)

        currentNode.children.forEach { childId ->
            val child = tree.getNode(childId)
            val childHeight = measureChildHeight(child, tree)
            val newY = startY + (childHeight / 2)

            startX =
                when (child) {
                    is CircleNode -> criteriaX + (child.path.radius / 2)
                    is RectangleNode -> criteriaX + (child.path.width / 2)
                }
            val newChild =
                when (child) {
                    is CircleNode -> {
                        val newPath = child.path.copy(centerX = startX, centerY = newY)
                        child.copy(path = newPath)
                    }

                    is RectangleNode -> {
                        val newPath = child.path.copy(centerX = startX, centerY = newY)
                        child.copy(path = newPath)
                    }
                }

            tree.setNode(childId, newChild)
            recurArrangeNode(newChild, tree)
            startY += childHeight + verticalSpacing
        }
    }

    fun measureChildHeight(
        node: Node,
        tree: Tree,
    ): Dp {
        var heightSum = Dp(0f)

        if (node.children.isNotEmpty()) {
            node.children.forEach { childId ->
                val childNode = tree.getNode(childId)
                heightSum += measureChildHeight(childNode, tree)
            }
            heightSum += verticalSpacing * (node.children.size - 1)
        } else {
            heightSum =
                when (node) {
                    is CircleNode -> node.path.radius
                    is RectangleNode -> node.path.height
                }
        }
        return heightSum
    }
}