Du bist nicht angemeldet.

Werbeanzeige

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 692

Wohnort: Gießen

  • Private Nachricht senden

1

20.06.2018, 16:19

Kürzeste Verbindungsstrecke zwischen Punkten an zwei Rechtecken bestimmen

Hallo,
ich habe zwei Rechtecke gegeben. An jedem Rechteck befinden sich 8 Verbindungspunkte (oben, unten, links, rechts und die Eckpunkte). Jetzt möchte ich eine Linie von Rechteck A zu Rechteck B zeichnen und dabei die beiden kürzesten Verbindungspunkte herausbekommen.

Es geht hierbei um Javascript Code, ich habe schon einmal etwas funktionierendes aufgebaut, aber vielleicht geht es ja optimaler.

Quellcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    const startRectConnectorPositions = lane.startRect.getConnectorPositions(); // Alle Verbindungspunkte von Rechteck A holen
    const targetRectConnectorPositions = lane.targetRect.getConnectorPositions(); // Alle Verbindungspunkte von Rechteck B holen

    const laneConnections = [];

    startRectConnectorPositions.forEach(startPosition => { // Alle Eckpunkte von A mit allen Eckpunkten von B verrechnen
        targetRectConnectorPositions.forEach(targetPosition => {
            const distance = Math.hypot(targetPosition.x - startPosition.x, targetPosition.y - startPosition.y); // Die Distanz der Punkte berechnen
            laneConnections.push({
                start: startPosition,
                target: targetPosition,
                distance: distance
            });
        });
    });

    const targetLaneConnection = laneConnections.reduce((a, b) => a.distance < b.distance ? a : b); // Die kürzeste Distanz aus dem Array holen


Vielleicht gibt es da ja etwas performanteres / eleganteres :)

David Scherfgen

Administrator

Beiträge: 10 202

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

2

20.06.2018, 16:23

Du musst dir nicht alle möglichen Verbindungen merken, denn du schmeißt ja später alle bis auf eine weg. Es reicht, wenn du dir die aktuell beste gefundene merkst (inkl. Länge). Jedes Mal wenn du eine bessere findest, überschreibst du das. Am Ende hast du die beste.

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 692

Wohnort: Gießen

  • Private Nachricht senden

3

20.06.2018, 16:30

Äh ja, mein zweiter Ansatz wäre folgender

Quellcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    const startRectConnectorPositions = lane.startRect.getConnectorPositions();
    const targetRectConnectorPositions = lane.targetRect.getConnectorPositions();

    let targetLaneConnection = {
        start: null,
        target: null,
        distance: Number.MAX_VALUE
    };

    for (let i = 0; i < startRectConnectorPositions.length; i++) {
        const startPosition = startRectConnectorPositions[i];
        for (let j = 0; j < targetRectConnectorPositions.length; j++) {
            const targetPosition = targetRectConnectorPositions[j];
            const distance = Math.hypot(targetPosition.x - startPosition.x, targetPosition.y - startPosition.y);
            if(distance < targetLaneConnection.distance){
                targetLaneConnection.start = startPosition;
                targetLaneConnection.target = targetPosition;
                targetLaneConnection.distance = distance;
            }
        }
    }


Dort überschreibe ich dann immer die aktuelle mit der günstigeren

4

21.06.2018, 17:26

Geht es dir nur um die Eckpunkte oder generell die kürzest mögliche Strecke zwischen 2 Rechtecken?
Besucht mich und meinen Blog unter:
www.simple-world.org

Du magst Tower Defense?
Dann probier doch mal Coregrounds aus ;)

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 692

Wohnort: Gießen

  • Private Nachricht senden

5

21.06.2018, 19:47

Mir ging es um die 8 Außenpunkte, aber mittlerweile ist das auch wieder verworfen, da jetzt ein BPMN Prozess abgebildet werden soll (nur eine statische Grafik, ohne Drag And Drop etc.) und ich jetzt dabei bin, "intelligente" Lanes zu entwerfen, die sich selbst ihren Weg suchen, ohne andere Elemente zu blockieren

6

21.06.2018, 21:38

Nur um das mal erwähnt zu haben:
Du solltest definitiv das Wurzel ziehen vermeiden, sofern das möglich ist (ist vergleichsweise sehr teuer). Hier ist ein Fall wo es definitiv möglich ist.
Besucht mich und meinen Blog unter:
www.simple-world.org

Du magst Tower Defense?
Dann probier doch mal Coregrounds aus ;)

David Scherfgen

Administrator

Beiträge: 10 202

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

7

21.06.2018, 22:16

Generell würde ich zustimmen, aber in diesem Fall ist es höchstwahrscheinlich völlig wurscht. Du würdest erst bei geschätzt mehreren zehntausend Ausführungen einen Unterschied messen können. Hinzu kommt, dass Math.hypot eine native JavaScript-Funktion ist, während das Quadrieren und Addieren „manuell“ gemacht werden müsste, wodurch es je nach JavaScript-Engine sogar langsamer sein könnte.

Werbeanzeige