#java #recursion #dendrogram
#java #рекурсия #дендрограмма
Вопрос:
Я должен нарисовать дендрограмму следующим образом :
но намного больше. Который существует в качестве опции для представления некоторой кластеризации данных. Итак, я застрял с рекурсивным методом, чтобы фактически нарисовать дендрограмму.
Я понимаю принцип, согласно которому метод рисования должен быть таким
draw(cluster){
if(clusters.hasChildren()){
draw(cluster.child1)
draw(cluster.child2)
}
//draw actual cluster here
}
но я совершенно застрял в его реализации.
Мой метод на данный момент выглядит так
drawCluster(cluster, startX, startY){
if(cluster.hasChildren()){
drawCluster, cluster.child1(), cluster.child1().getDepth * 30, height - cluster.child2.getWidth * 20)
drawCluster, cluster.child2(), cluster.child2().getDepth * 30, height - 20)
}
if cluster.getDepth() == 0 )
drawLine(500 - 30), height, 500)
else
drawLine(500 - (width * 30), height, 500);
}
Таким образом, пространство, которое у меня есть для его рисования, составляет 500 пикселей в ширину, а высота total_number_of_Leafs * 20
На данный момент я рисую линию только для каждого кластера, чтобы правильно определить расстояния.
Каждый раз, когда я запускаю строку @ 500 пикселей минус глубина кластера, умноженная на 20.И нарисуйте линию до 500-го пикселя.
Также предполагается, что высота равна maxHeight . например, когда дело доходит до рисования, допустим, кластер с (1,2) высотой в аргументе будет равен 40. И так далее.
Но это работает не так хорошо. Я в основном застрял на том, как изменять значения каждый раз, когда я вызываю метод рисования. Также нужно ли мне передавать больше переменных, отличных от начала строки x и y?
Буду признателен за любую помощь, поскольку у меня есть крайний срок, который нужно успеть.
Заранее спасибо.
Комментарии:
1. Можете ли вы предоставить какой-нибудь минимальный воспроизводимый пример, включая структуру данных и тестовые данные?
2. Данные и фактическая кластеризация работают так, как задумано. Проверено с помощью операторов печати и т. Д. То же самое относится и к методам получения ширины кластера, глубины и т.д. Моя единственная проблема — это фактическое представление. Если бы вы могли дать мне несколько советов о том, как вызвать рекурсивный метод, чтобы нарисовать именно эту вещь на изображении, я думаю, этого будет достаточно, чтобы заставить мой метод работать.
3. Мы не говорили, что эти части неверны, нам было бы намного проще помочь вам, если бы мы знали структуру данных, которую вы используете, и имели какой-нибудь пример для тестирования.
4. Ну, поскольку это университетское задание, я не хочу указывать структуру данных и фактические входные данные, потому что я не уверен, должен ли я задавать такой вопрос здесь или нет. Я не думаю, что в этом что-то не так, это не похоже на то, что я прошу asnwer или что-то в этом роде. Но w / e. В любом случае, если бы вы могли создать что-то только для этого небольшого дерева, это было бы хорошо. Оставьте листы такими, какие они есть, и пусть узлы содержат сумму их базовых кластеров. или что-то подобное. Этого будет достаточно? Прошу прощения за путаницу.
Ответ №1:
Нарисовать дендрограмму точно так же рекурсивно на самом деле немного сложно.
Конечные узлы не должны «знать» свою y-позицию. Кроме того, ни один узел «напрямую» не знает, где он должен быть нарисован, и как должны быть нарисованы линии, соединяющие его с его дочерними элементами: вся эта информация недоступна до того, как все листья (или дочерние элементы каждого узла, соответственно) были нарисованы.
Я думаю, что итеративное решение могло бы быть проще и гибче. Однако здесь представлена реализация, использующая рекурсивный подход. Обратите внимание, что это очень простая реализация, которая (например) предполагает, что структура данных для дендрограммы представляет собой двоичное дерево, но это должно соответствовать примеру, который вы опубликовали.
Кстати: он заполняет доступное пространство, и я настоятельно рекомендую избегать «магических констант» и предположений о размере пикселей узлов или области рисования, как в drawLine(500 - (width * 30), height, 500) . Даже если вы не хотите вычислять их исходя из размера дерева и количества конечных узлов, вы должны по крайней мере ввести переменные для этого, чтобы вы могли легче изменить его позже.
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;
public class DendrogramPaintTest
{
public static void main(String[] args)
{
SwingUtilities.invokeLater(new Runnable()
{
@Override
public void run()
{
createAndShowGUI();
}
});
}
private static void createAndShowGUI()
{
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
DendrogramPaintPanel panel = new DendrogramPaintPanel();
f.getContentPane().add(panel);
f.setSize(1000,800);
f.setLocationRelativeTo(null);
f.setVisible(true);
}
}
class Node<T>
{
private final T contents;
private final List<Node<T>> children;
Node(T contents)
{
this.contents = contents;
this.children = Collections.emptyList();
}
Node(Node<T> child0, Node<T> child1)
{
this.contents = null;
List<Node<T>> list = new ArrayList<Node<T>>();
list.add(child0);
list.add(child1);
this.children = Collections.unmodifiableList(list);
}
public T getContents()
{
return contents;
}
public List<Node<T>> getChildren()
{
return Collections.unmodifiableList(children);
}
}
class DendrogramPaintPanel extends JPanel
{
private static <T> Node<T> create(T contents)
{
return new Node<T>(contents);
}
private static <T> Node<T> create(Node<T> child0, Node<T> child1)
{
return new Node<T>(child0, child1);
}
private Node<String> root;
private int leaves;
private int levels;
private int heightPerLeaf;
private int widthPerLevel;
private int currentY;
private final int margin = 25;
DendrogramPaintPanel()
{
root =
create(
create(
create("10"),
create(
create("9"),
create(
create("8"),
create("7")
)
)
),
create(
create(
create("6"),
create("5")
),
create(
create("4"),
create(
create("3"),
create(
create("2"),
create("1")
)
)
)
)
);
}
private static <T> int countLeaves(Node<T> node)
{
List<Node<T>> children = node.getChildren();
if (children.size() == 0)
{
return 1;
}
Node<T> child0 = children.get(0);
Node<T> child1 = children.get(1);
return countLeaves(child0) countLeaves(child1);
}
private static <T> int countLevels(Node<T> node)
{
List<Node<T>> children = node.getChildren();
if (children.size() == 0)
{
return 1;
}
Node<T> child0 = children.get(0);
Node<T> child1 = children.get(1);
return 1 Math.max(countLevels(child0), countLevels(child1));
}
@Override
protected void paintComponent(Graphics gr)
{
super.paintComponent(gr);
Graphics2D g = (Graphics2D)gr;
leaves = countLeaves(root);
levels = countLevels(root);
heightPerLeaf = (getHeight() - margin - margin) / leaves;
widthPerLevel = (getWidth() - margin - margin)/ levels;
currentY = 0;
g.translate(margin, margin);
draw(g, root, 0);
}
private <T> Point draw(Graphics g, Node<T> node, int y)
{
List<Node<T>> children = node.getChildren();
if (children.size() == 0)
{
int x = getWidth() - widthPerLevel - 2 * margin;
g.drawString(String.valueOf(node.getContents()), x 8, currentY 8);
int resultX = x;
int resultY = currentY;
currentY = heightPerLeaf;
return new Point(resultX, resultY);
}
if (children.size() >= 2)
{
Node<T> child0 = children.get(0);
Node<T> child1 = children.get(1);
Point p0 = draw(g, child0, y);
Point p1 = draw(g, child1, y heightPerLeaf);
g.fillRect(p0.x-2, p0.y-2, 4, 4);
g.fillRect(p1.x-2, p1.y-2, 4, 4);
int dx = widthPerLevel;
int vx = Math.min(p0.x-dx, p1.x-dx);
g.drawLine(vx, p0.y, p0.x, p0.y);
g.drawLine(vx, p1.y, p1.x, p1.y);
g.drawLine(vx, p0.y, vx, p1.y);
Point p = new Point(vx, p0.y (p1.y - p0.y)/2);
return p;
}
// Should never happen
return new Point();
}
}
Комментарии:
1. Очень полезно, спасибо. Однако с полями есть ошибка — она должна гласить: «int x = getWidth() — widthPerLevel — 2 * margin;» (где затем поле должно быть глобализировано).
2. @lemon Это был пример, который я быстро собрал, чтобы показать основную идею рекурсивного рисования в целом. Конечно, есть несколько возможных улучшений (также в зависимости от случая применения). Но включение поля в x-вычисление действительно делает его более независимым от изменения размера панели, поэтому я отредактировал его соответствующим образом — спасибо за этот намек.
Ответ №2:
Поскольку вы не можете предоставить какую-либо конкретную структуру данных, я могу предоставить только псевдокод. Наиболее важной частью, по-видимому, является построение дерева снизу вверх с учетом вычисленной ширины нижних уровней при построении более высоких уровней.
func drawCluster(node:Node, depth:int, top:int) -> int:
if node has children:
next_top = top
for child in node.children:
drawLine(depth, top, depth 1, next_top)
next_top = drawCluster(child, depth 1, next_top)
return next_top
else:
drawLabel(node.label, depth, top)
return top text_height
Очевидно, я не мог это проверить, но однажды я сделал нечто подобное для алгоритмов компоновки графов, поэтому я думаю, что это должно сработать, если я не неправильно понял ваш вопрос.
Комментарии:
1. Ну, то, как я пытался это сделать, заключалось в том, что сначала цикл for проходил через все кластеры. Поскольку некоторые кластеры на самом деле могут быть листьями по всей кластеризации, и в этом случае мне нужна строка, которая покрывает всю ширину. Затем, если у кластера есть дочерние элементы, я вызываю рекурсивный метод для рисования этого кластера. Я пытаюсь выяснить, как ваш метод можно объединить с тем, что я делаю, или мне нужно полностью его изменить.
2. Не уверен, что понимаю, что вы имеете в виду. Я думаю, что кластеры должны быть выровнены по правому краю… Что ж, в этом случае вы можете сделать аналогично, за исключением того, что вам также придется возвращать глубину кластера, вместо того, чтобы передавать ее в качестве параметра. (Возвращать кортежи в Java немного некрасиво, но выполнимо). Если это не то, что вы хотите, опубликуйте пример. Вам не нужно помещать весь свой код назначения в вопрос, просто найдите какую-то абстракцию, которая по-прежнему несет суть проблемы. Без этого действительно трудно помочь.