Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Werbeanzeige

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 693

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 382

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: 693

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?

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 693

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.

David Scherfgen

Administrator

Beiträge: 10 382

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