ScalaFX/JavaFX 8 get nearest Nodes

Question

Currently experimenting with ScalaFX a bit.

Imagine the following:

I have some nodes and they are connected by some edges.

Now when I click the mousebutton I want to select the ones next to the mouse click, e.g. if I click between 1 and 2, I want those two to be selected, if I click before 0, only that one (as it's the first) etc.

Currently (and just as a proof of concept) I am doing this by adding in some helper structures. I have a HashMap of type [Index, Node] and select them like so:

wrapper.onMouseClicked = (mouseEvent: MouseEvent) =>
{
    val lowerIndex: Int = (mouseEvent.sceneX).toString.charAt(0).asDigit
    val left = nodes.get(lowerIndex)
    val right = nodes.get(lowerIndex+1)

    left.get.look.setStyle("-fx-background-color: orange;")
    right.get.look.setStyle("-fx-background-color: orange;")
}

this does it's just, but I need to have an additional datastructure and it will get really tedious in 2D, like when I have a Y coordinate as well.

What I would prefer would be some method like mentioned in

How to detect Node at specific point in JavaFX?

or

JavaFX 2.2 get node at coordinates (visual tree hit testing)

These questions are based on older versions of JavaFX and use deprecated methods.

I could not find any replacement or solution in ScalaFX 8 so far. Is there a nice way to get all the nodes within a certain radius?

score 1 · Accepted Answer · edited May 23 '17 at 12:08

So "Nearest neighbor search" is the general problem you are trying to solve.

Your problem statement is a bit short on details. E.g., are nodes equidistant from each other? are nodes arranged in a grid pattern or randomly? is the node distance modeled based upon a point at the node center, a surrounding box, the actual closest point on an arbitrarily shaped node? etc.

I'll assume randomly placed shapes that may overlap, and picking is not based upon painting order, but on the closest corners of the bounding boxes of shapes. A more accurate picker might work by comparing the clicked point against against an elliptical area surrounding the actual shape rather than the shapes bounding box (as the current picker will be a bit finicky to use for things like overlapping diagonal lines).

A k-d tree algorithm or an R-tree could be used, but in general a linear brute force search will probably just work fine for most applications.

Sample brute force solution algorithm

private Node findNearestNode(ObservableList<Node> nodes, double x, double y) {
    Point2D pClick = new Point2D(x, y);
    Node nearestNode = null;
    double closestDistance = Double.POSITIVE_INFINITY;

    for (Node node : nodes) {
        Bounds bounds = node.getBoundsInParent();
        Point2D[] corners = new Point2D[] {
                new Point2D(bounds.getMinX(), bounds.getMinY()),
                new Point2D(bounds.getMaxX(), bounds.getMinY()),
                new Point2D(bounds.getMaxX(), bounds.getMaxY()),
                new Point2D(bounds.getMinX(), bounds.getMaxY()),
        };

        for (Point2D pCompare: corners) {
            double nextDist = pClick.distance(pCompare);
            if (nextDist < closestDistance) {
                closestDistance = nextDist;
                nearestNode = node;
            }
        }
    }

    return nearestNode;
}

Executable Solution

import javafx.application.Application;
import javafx.collections.ObservableList;
import javafx.geometry.*;
import javafx.scene.*;
import javafx.scene.effect.DropShadow;
import javafx.scene.layout.Pane;
import javafx.scene.paint.Color;
import javafx.scene.shape.*;
import javafx.stage.Stage;

import java.io.IOException;
import java.net.*;
import java.util.Random;

public class FindNearest extends Application {
    private static final int N_SHAPES = 10;
    private static final double W = 600, H = 400;

    private ShapeMachine machine;

    public static void main(String[] args) {
        launch(args);
    }

    @Override
    public void init() throws MalformedURLException, URISyntaxException {
        double maxShapeSize = W / 8;
        double minShapeSize = maxShapeSize / 2;
        machine = new ShapeMachine(W, H, maxShapeSize, minShapeSize);
    }

    @Override
    public void start(final Stage stage) throws IOException, URISyntaxException {
        Pane pane = new Pane();
        pane.setPrefSize(W, H);
        for (int i = 0; i < N_SHAPES; i++) {
            pane.getChildren().add(machine.randomShape());
        }

        pane.setOnMouseClicked(event -> {
            Node node = findNearestNode(pane.getChildren(), event.getX(), event.getY());
            highlightSelected(node, pane.getChildren());
        });

        Scene scene = new Scene(pane);
        configureExitOnAnyKey(stage, scene);

        stage.setScene(scene);
        stage.setResizable(false);
        stage.show();
    }

    private void highlightSelected(Node selected, ObservableList<Node> children) {
        for (Node node: children) {
           node.setEffect(null);
        }

        if (selected != null) {
            selected.setEffect(new DropShadow(10, Color.YELLOW));
        }
    }

    private Node findNearestNode(ObservableList<Node> nodes, double x, double y) {
        Point2D pClick = new Point2D(x, y);
        Node nearestNode = null;
        double closestDistance = Double.POSITIVE_INFINITY;

        for (Node node : nodes) {
            Bounds bounds = node.getBoundsInParent();
            Point2D[] corners = new Point2D[] {
                    new Point2D(bounds.getMinX(), bounds.getMinY()),
                    new Point2D(bounds.getMaxX(), bounds.getMinY()),
                    new Point2D(bounds.getMaxX(), bounds.getMaxY()),
                    new Point2D(bounds.getMinX(), bounds.getMaxY()),
            };

            for (Point2D pCompare: corners) {
                double nextDist = pClick.distance(pCompare);
                if (nextDist < closestDistance) {
                    closestDistance = nextDist;
                    nearestNode = node;
                }
            }
        }

        return nearestNode;
    }

    private void configureExitOnAnyKey(final Stage stage, Scene scene) {
        scene.setOnKeyPressed(keyEvent -> stage.hide());
    }
}

Auxiliary random shape generation class

This class is not key to the solution, it just generates some shapes for testing.

class ShapeMachine {

    private static final Random random = new Random();
    private final double canvasWidth, canvasHeight, maxShapeSize, minShapeSize;

    ShapeMachine(double canvasWidth, double canvasHeight, double maxShapeSize, double minShapeSize) {
        this.canvasWidth = canvasWidth;
        this.canvasHeight = canvasHeight;
        this.maxShapeSize = maxShapeSize;
        this.minShapeSize = minShapeSize;
    }

    private Color randomColor() {
        return Color.rgb(random.nextInt(256), random.nextInt(256), random.nextInt(256), 0.1 + random.nextDouble() * 0.9);
    }

    enum Shapes {Circle, Rectangle, Line}

    public Shape randomShape() {
        Shape shape = null;

        switch (Shapes.values()[random.nextInt(Shapes.values().length)]) {
            case Circle:
                shape = randomCircle();
                break;
            case Rectangle:
                shape = randomRectangle();
                break;
            case Line:
                shape = randomLine();
                break;
            default:
                System.out.println("Unknown Shape");
                System.exit(1);
        }

        Color fill = randomColor();
        shape.setFill(fill);
        shape.setStroke(deriveStroke(fill));
        shape.setStrokeWidth(deriveStrokeWidth(shape));
        shape.setStrokeLineCap(StrokeLineCap.ROUND);
        shape.relocate(randomShapeX(), randomShapeY());

        return shape;
    }

    private double deriveStrokeWidth(Shape shape) {
        return Math.max(shape.getLayoutBounds().getWidth() / 10, shape.getLayoutBounds().getHeight() / 10);
    }

    private Color deriveStroke(Color fill) {
        return fill.desaturate();
    }

    private double randomShapeSize() {
        double range = maxShapeSize - minShapeSize;
        return random.nextDouble() * range + minShapeSize;
    }

    private double randomShapeX() {
        return random.nextDouble() * (canvasWidth + maxShapeSize) - maxShapeSize / 2;
    }

    private double randomShapeY() {
        return random.nextDouble() * (canvasHeight + maxShapeSize) - maxShapeSize / 2;
    }

    private Shape randomLine() {
        int xZero = random.nextBoolean() ? 1 : 0;
        int yZero = random.nextBoolean() || xZero == 0 ? 1 : 0;

        int xSign = random.nextBoolean() ? 1 : -1;
        int ySign = random.nextBoolean() ? 1 : -1;

        return new Line(0, 0, xZero * xSign * randomShapeSize(), yZero * ySign * randomShapeSize());
    }

    private Shape randomRectangle() {
        return new Rectangle(0, 0, randomShapeSize(), randomShapeSize());
    }

    private Shape randomCircle() {
        double radius = randomShapeSize() / 2;
        return new Circle(radius, radius, radius);
    }

}

Further example placing objects in a zoomable/scrollable area

This solution uses the nearest node solution code from above and combines it with the zoomed node in a ScrollPane code from: JavaFX correct scaling. The purpose is to demonstrate that the choosing algorithm works even on nodes which have had a scaling transform applied to them (because it is based upon boundsInParent). The code is just meant as a proof of concept and not as a stylistic sample of how to structure the functionality into a class domain model :-)

import javafx.application.Application;
import javafx.beans.property.ObjectProperty;
import javafx.beans.property.SimpleObjectProperty;
import javafx.beans.value.*;
import javafx.collections.ObservableList;
import javafx.event.*;
import javafx.geometry.Bounds;
import javafx.geometry.Point2D;
import javafx.scene.*;
import javafx.scene.control.*;
import javafx.scene.effect.DropShadow;
import javafx.scene.image.*;
import javafx.scene.input.*;
import javafx.scene.layout.*;
import javafx.scene.paint.Color;
import javafx.scene.shape.*;
import javafx.stage.Stage;

import java.net.MalformedURLException;
import java.net.URISyntaxException;

public class GraphicsScalingApp extends Application {
    private static final int N_SHAPES = 10;
    private static final double W = 600, H = 400;

    private ShapeMachine machine;

    public static void main(String[] args) {
        launch(args);
    }

    @Override
    public void init() throws MalformedURLException, URISyntaxException {
        double maxShapeSize = W / 8;
        double minShapeSize = maxShapeSize / 2;
        machine = new ShapeMachine(W, H, maxShapeSize, minShapeSize);
    }

    @Override
    public void start(final Stage stage) {
        Pane pane = new Pane();
        pane.setPrefSize(W, H);
        for (int i = 0; i < N_SHAPES; i++) {
            pane.getChildren().add(machine.randomShape());
        }

        pane.setOnMouseClicked(event -> {
            Node node = findNearestNode(pane.getChildren(), event.getX(), event.getY());
            System.out.println("Found: " + node + " at " + event.getX() + "," + event.getY());
            highlightSelected(node, pane.getChildren());
        });

        final Group group = new Group(
                pane
        );

        Parent zoomPane = createZoomPane(group);

        VBox layout = new VBox();
        layout.getChildren().setAll(createMenuBar(stage, group), zoomPane);

        VBox.setVgrow(zoomPane, Priority.ALWAYS);

        Scene scene = new Scene(layout);

        stage.setTitle("Zoomy");
        stage.getIcons().setAll(new Image(APP_ICON));
        stage.setScene(scene);
        stage.show();
    }

    private Parent createZoomPane(final Group group) {
        final double SCALE_DELTA = 1.1;
        final StackPane zoomPane = new StackPane();

        zoomPane.getChildren().add(group);

        final ScrollPane scroller = new ScrollPane();
        final Group scrollContent = new Group(zoomPane);
        scroller.setContent(scrollContent);

        scroller.viewportBoundsProperty().addListener(new ChangeListener<Bounds>() {
            @Override
            public void changed(ObservableValue<? extends Bounds> observable,
                                Bounds oldValue, Bounds newValue) {
                zoomPane.setMinSize(newValue.getWidth(), newValue.getHeight());
            }
        });

        scroller.setPrefViewportWidth(256);
        scroller.setPrefViewportHeight(256);

        zoomPane.setOnScroll(new EventHandler<ScrollEvent>() {
            @Override
            public void handle(ScrollEvent event) {
                event.consume();

                if (event.getDeltaY() == 0) {
                    return;
                }

                double scaleFactor = (event.getDeltaY() > 0) ? SCALE_DELTA
                        : 1 / SCALE_DELTA;

                // amount of scrolling in each direction in scrollContent coordinate
                // units
                Point2D scrollOffset = figureScrollOffset(scrollContent, scroller);

                group.setScaleX(group.getScaleX() * scaleFactor);
                group.setScaleY(group.getScaleY() * scaleFactor);

                // move viewport so that old center remains in the center after the
                // scaling
                repositionScroller(scrollContent, scroller, scaleFactor, scrollOffset);

            }
        });

        // Panning via drag....
        final ObjectProperty<Point2D> lastMouseCoordinates = new SimpleObjectProperty<Point2D>();
        scrollContent.setOnMousePressed(new EventHandler<MouseEvent>() {
            @Override
            public void handle(MouseEvent event) {
                lastMouseCoordinates.set(new Point2D(event.getX(), event.getY()));
            }
        });

        scrollContent.setOnMouseDragged(new EventHandler<MouseEvent>() {
            @Override
            public void handle(MouseEvent event) {
                double deltaX = event.getX() - lastMouseCoordinates.get().getX();
                double extraWidth = scrollContent.getLayoutBounds().getWidth() - scroller.getViewportBounds().getWidth();
                double deltaH = deltaX * (scroller.getHmax() - scroller.getHmin()) / extraWidth;
                double desiredH = scroller.getHvalue() - deltaH;
                scroller.setHvalue(Math.max(0, Math.min(scroller.getHmax(), desiredH)));

                double deltaY = event.getY() - lastMouseCoordinates.get().getY();
                double extraHeight = scrollContent.getLayoutBounds().getHeight() - scroller.getViewportBounds().getHeight();
                double deltaV = deltaY * (scroller.getHmax() - scroller.getHmin()) / extraHeight;
                double desiredV = scroller.getVvalue() - deltaV;
                scroller.setVvalue(Math.max(0, Math.min(scroller.getVmax(), desiredV)));
            }
        });

        return scroller;
    }

    private Point2D figureScrollOffset(Node scrollContent, ScrollPane scroller) {
        double extraWidth = scrollContent.getLayoutBounds().getWidth() - scroller.getViewportBounds().getWidth();
        double hScrollProportion = (scroller.getHvalue() - scroller.getHmin()) / (scroller.getHmax() - scroller.getHmin());
        double scrollXOffset = hScrollProportion * Math.max(0, extraWidth);
        double extraHeight = scrollContent.getLayoutBounds().getHeight() - scroller.getViewportBounds().getHeight();
        double vScrollProportion = (scroller.getVvalue() - scroller.getVmin()) / (scroller.getVmax() - scroller.getVmin());
        double scrollYOffset = vScrollProportion * Math.max(0, extraHeight);
        return new Point2D(scrollXOffset, scrollYOffset);
    }

    private void repositionScroller(Node scrollContent, ScrollPane scroller, double scaleFactor, Point2D scrollOffset) {
        double scrollXOffset = scrollOffset.getX();
        double scrollYOffset = scrollOffset.getY();
        double extraWidth = scrollContent.getLayoutBounds().getWidth() - scroller.getViewportBounds().getWidth();
        if (extraWidth > 0) {
            double halfWidth = scroller.getViewportBounds().getWidth() / 2;
            double newScrollXOffset = (scaleFactor - 1) * halfWidth + scaleFactor * scrollXOffset;
            scroller.setHvalue(scroller.getHmin() + newScrollXOffset * (scroller.getHmax() - scroller.getHmin()) / extraWidth);
        } else {
            scroller.setHvalue(scroller.getHmin());
        }
        double extraHeight = scrollContent.getLayoutBounds().getHeight() - scroller.getViewportBounds().getHeight();
        if (extraHeight > 0) {
            double halfHeight = scroller.getViewportBounds().getHeight() / 2;
            double newScrollYOffset = (scaleFactor - 1) * halfHeight + scaleFactor * scrollYOffset;
            scroller.setVvalue(scroller.getVmin() + newScrollYOffset * (scroller.getVmax() - scroller.getVmin()) / extraHeight);
        } else {
            scroller.setHvalue(scroller.getHmin());
        }
    }

    private SVGPath createCurve() {
        SVGPath ellipticalArc = new SVGPath();
        ellipticalArc.setContent("M10,150 A15 15 180 0 1 70 140 A15 25 180 0 0 130 130 A15 55 180 0 1 190 120");
        ellipticalArc.setStroke(Color.LIGHTGREEN);
        ellipticalArc.setStrokeWidth(4);
        ellipticalArc.setFill(null);
        return ellipticalArc;
    }

    private SVGPath createStar() {
        SVGPath star = new SVGPath();
        star.setContent("M100,10 L100,10 40,180 190,60 10,60 160,180 z");
        star.setStrokeLineJoin(StrokeLineJoin.ROUND);
        star.setStroke(Color.BLUE);
        star.setFill(Color.DARKBLUE);
        star.setStrokeWidth(4);
        return star;
    }

    private MenuBar createMenuBar(final Stage stage, final Group group) {
        Menu fileMenu = new Menu("_File");
        MenuItem exitMenuItem = new MenuItem("E_xit");
        exitMenuItem.setGraphic(new ImageView(new Image(CLOSE_ICON)));
        exitMenuItem.setOnAction(new EventHandler<ActionEvent>() {
            @Override
            public void handle(ActionEvent event) {
                stage.close();
            }
        });
        fileMenu.getItems().setAll(exitMenuItem);
        Menu zoomMenu = new Menu("_Zoom");
        MenuItem zoomResetMenuItem = new MenuItem("Zoom _Reset");
        zoomResetMenuItem.setAccelerator(new KeyCodeCombination(KeyCode.ESCAPE));
        zoomResetMenuItem.setGraphic(new ImageView(new Image(ZOOM_RESET_ICON)));
        zoomResetMenuItem.setOnAction(new EventHandler<ActionEvent>() {
            @Override
            public void handle(ActionEvent event) {
                group.setScaleX(1);
                group.setScaleY(1);
            }
        });
        MenuItem zoomInMenuItem = new MenuItem("Zoom _In");
        zoomInMenuItem.setAccelerator(new KeyCodeCombination(KeyCode.I));
        zoomInMenuItem.setGraphic(new ImageView(new Image(ZOOM_IN_ICON)));
        zoomInMenuItem.setOnAction(new EventHandler<ActionEvent>() {
            @Override
            public void handle(ActionEvent event) {
                group.setScaleX(group.getScaleX() * 1.5);
                group.setScaleY(group.getScaleY() * 1.5);
            }
        });
        MenuItem zoomOutMenuItem = new MenuItem("Zoom _Out");
        zoomOutMenuItem.setAccelerator(new KeyCodeCombination(KeyCode.O));
        zoomOutMenuItem.setGraphic(new ImageView(new Image(ZOOM_OUT_ICON)));
        zoomOutMenuItem.setOnAction(new EventHandler<ActionEvent>() {
            @Override
            public void handle(ActionEvent event) {
                group.setScaleX(group.getScaleX() * 1 / 1.5);
                group.setScaleY(group.getScaleY() * 1 / 1.5);
            }
        });
        zoomMenu.getItems().setAll(zoomResetMenuItem, zoomInMenuItem,
                zoomOutMenuItem);
        MenuBar menuBar = new MenuBar();
        menuBar.getMenus().setAll(fileMenu, zoomMenu);
        return menuBar;
    }


    private void highlightSelected(Node selected, ObservableList<Node> children) {
        for (Node node : children) {
            node.setEffect(null);
        }

        if (selected != null) {
            selected.setEffect(new DropShadow(10, Color.YELLOW));
        }
    }

    private Node findNearestNode(ObservableList<Node> nodes, double x, double y) {
        Point2D pClick = new Point2D(x, y);
        Node nearestNode = null;
        double closestDistance = Double.POSITIVE_INFINITY;

        for (Node node : nodes) {
            Bounds bounds = node.getBoundsInParent();
            Point2D[] corners = new Point2D[]{
                    new Point2D(bounds.getMinX(), bounds.getMinY()),
                    new Point2D(bounds.getMaxX(), bounds.getMinY()),
                    new Point2D(bounds.getMaxX(), bounds.getMaxY()),
                    new Point2D(bounds.getMinX(), bounds.getMaxY()),
            };

            for (Point2D pCompare : corners) {
                double nextDist = pClick.distance(pCompare);
                if (nextDist < closestDistance) {
                    closestDistance = nextDist;
                    nearestNode = node;
                }
            }
        }

        return nearestNode;
    }


    // icons source from:
    // http://www.iconarchive.com/show/soft-scraps-icons-by-deleket.html
    // icon license: CC Attribution-Noncommercial-No Derivate 3.0 =?
    // http://creativecommons.org/licenses/by-nc-nd/3.0/
    // icon Commercial usage: Allowed (Author Approval required -> Visit artist
    // website for details).

    public static final String APP_ICON = "http://icons.iconarchive.com/icons/deleket/soft-scraps/128/Zoom-icon.png";
    public static final String ZOOM_RESET_ICON = "http://icons.iconarchive.com/icons/deleket/soft-scraps/24/Zoom-icon.png";
    public static final String ZOOM_OUT_ICON = "http://icons.iconarchive.com/icons/deleket/soft-scraps/24/Zoom-Out-icon.png";
    public static final String ZOOM_IN_ICON = "http://icons.iconarchive.com/icons/deleket/soft-scraps/24/Zoom-In-icon.png";
    public static final String CLOSE_ICON = "http://icons.iconarchive.com/icons/deleket/soft-scraps/24/Button-Close-icon.png";
}

So there is no built in solution? *sighs* I was hoping that the absolute positions would be saved somewhere easily accessible :( — , Mar 09 '16 at 19:13
Well the node positions are saved with the node, I get them from the node using `getBoundsInParent`. There are various other built-in functions which transform the node co-ordinates to local or scene co-ordinates (search the [node javadoc](https://docs.oracle.com/javase/8/javafx/api/javafx/scene/Node.html) for "localTo"). There are also in-built picking functions, but those pick the node based upon a hit, not the nearest node in the case of miss. So to find the nearest node based upon a miss, you need to provide that logic yourself. It's a pretty straight-forward search algorithm. — jewelsea, Mar 09 '16 at 20:20
Ya, the algorithm is straightforward, but it doesn't work for me. May be because of my ZoomableScrollPane, but it simply doesn't select the right ones :( — , Mar 09 '16 at 20:27
Ya, definitely because of scrolling/zooming. Would need to calculate that out. Oh boy, that's so complicated for something that should be so easy :/ — , Mar 09 '16 at 20:39
When I added scrolling and zooming functionality, the original nearest neighbor detection algorithm implementation worked fine for me without modifications (see updated sample in answer). — jewelsea, Mar 10 '16 at 01:08

ScalaFX/JavaFX 8 get nearest Nodes

1 Answers1