Orientation in 2D of a point relative to two other points

Γενικά θέματα για τις γλώσσες προγραμματισμού που δεν καλύπτονται από τις άλλες περιοχές της κατηγορίας.

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
crmaris
Δημοσιεύσεις: 17
Εγγραφή: 20 Δεκ 2004 23:46

Orientation in 2D of a point relative to two other points

Δημοσίευση από crmaris » 11 Ιουν 2007 01:34

καλησπέρα. Το πρόβλημα που αντιμετωπίζω δεν έχει να κάνει με μια συγκεκριμένη γλώσσα προγραμματισμού αλλά είναι κυρίως μαθηματικό. Λοιπόν έχω μια συνδεσμολογία δικτύου από nodes η οποία αναπαριστάτε σε ένα καρτεσιανό επίπεδο. Έχω ένα node a το οποίο ενώνεται με 2 άλλα nodes (child nodes) b και c. Ψάχνω λοιπόν να βρώ το orientation των nodes b και c ως προς το node a(root)(δηλαδή πιο είναι αριστερά από το a και πιo είναι δεξιά του). Μέχρι εδώ το βρήκα αυτό εύκολα. Αυτό που θέλω να κάνω τώρα είναι αν το node a έχει παραπάνω από 2 childs πως βρίσκω το orientation τους. Δηλαδή πιο είναι πιο δεξιά, πιο αμέσως πιο δεξιά κτλ..

Ο κώδικας για την εύρεση του orientation ενός σημείου (συντεταγμένες node,x,y)ως προς δύο άλλα σημεία ειναι ο παρακάτω. Εγώ θέλω να τον τροποποιήσω για να βρίσκω το orientation ως προς παραπάνω από δύο σημεία.

function Orientation(x1, y1, x2, y2, Px, Py: Double): Integer;
var
Orin: Double;
begin
(* Linear determinant of the 3 points *)
Orin := (x2 - x1) * (py - y1) - (px - x1) * (y2 - y1);

if Orin > 0.0 then Result := +1 (* Orientaion is to the right-hand side *)
else if Orin < 0.0 then Result := -1 (* Orientaion is to the left-hand side *)
else
Result := 0; (* Orientaion is neutral if result is 0 *)
end;

κάθε βοηθεια ευπρόσδεκτη.

Άβαταρ μέλους
dik_
Δημοσιεύσεις: 476
Εγγραφή: 07 Ιουν 2007 11:28

Orientation in 2D of a point relative to two other points

Δημοσίευση από dik_ » 12 Ιουν 2007 05:01

Χμμ, η απάντησή μου δυστυχώς δεν είναι αρκετά γενική, απαντώ έχοντας στο νου μου τι θα έκανα εγώ σε java:

Θα είχα ένα List από Node objects, θα έφτιαχνα κι ένα Comparator, του οποίου η compare() θα ήταν ουσιαστικά η μέθοδος που παραθέτεις, και θα σόρταρα τη λίστα με τη sort(), παίρνοντας τα Nodes από αριστερά προς τα δεξιά (ή αντίθετα).

Η γενική ιδέα είναι με μια λούπα να κάνεις iterate όλα τα nodes σου, και χρησιμοποιώντας τη μέθοδό σου να τα ταξινομήσεις...

crmaris
Δημοσιεύσεις: 17
Εγγραφή: 20 Δεκ 2004 23:46

Orientation in 2D of a point relative to two other points

Δημοσίευση από crmaris » 13 Ιουν 2007 12:15

ευχαριστώ καταρχήν για την απάντηση. Φτιάχνω και εγώ λίστα σε delphi αφού συγκρίνω τις συντεταγμένες των nodes. Το θέμα είναι ότι ο κωδικός που παραθέτω λειτουργεί σωστά για μέχρι 2 child nodes. Από 2 και πάνω υπάρχει πρόβλημα.. Εγώ ψάχνω να βρω τώρα σε πιο μαθηματικό θεώρημα βασίζεται ο κώδικας του orientation για να τον μετατρέψω για πολλαπλά σημεία για τα οποία ξέρω τις συντεταγμένες τους.. Δηλαδή ψάχνω την λογική στην οποία βασίζεται το θεώρημα και αν υπάρχει κάτι για πάνω από 3 σημεία (γιαυτό και το έβαλα στα γενικά γιατί δεν με ενδιαφέρει η γλώσσα υλοποίησης αλλά το σκεπτικό που βασίζεται).

Άβαταρ μέλους
dik_
Δημοσιεύσεις: 476
Εγγραφή: 07 Ιουν 2007 11:28

Orientation in 2D of a point relative to two other points

Δημοσίευση από dik_ » 13 Ιουν 2007 12:39

Τελικά, αυτό που σε ενδιαφέρει δεν είναι απλώς να συγκρίνεις τα x των σημείων; Όσο μικρότερο το x, τόσο πιο αριστερά το node... Άρα σορτάρεις τη λίστα βάσει του x, αν δηλαδή έχεις 4 nodes με x Α(12), Β(34), Γ(7) και Δ(45), τότε η σορταρισμένη λίστα σου θα είναι Γ, Α, Β, Δ.

Άμα λάχει, βάζεις και το parent node μέσα, ας πούμε το Β εδώ, και ξέρεις ότι τα Γ και Α είναι αριστερά του, ενώ το Δ δεξιά του. Δηλαδή:

Κώδικας: Επιλογή όλων

            Β
            |
+------+----+------+
|      |           |
Γ      Α           Δ

crmaris
Δημοσιεύσεις: 17
Εγγραφή: 20 Δεκ 2004 23:46

Orientation in 2D of a point relative to two other points

Δημοσίευση από crmaris » 19 Ιουν 2007 00:19

τα nodes ειναι σε ενα χωρο οπως στην εικόνα οπότε με το x μονο δεν κάνω δουλειά
Συνημμένα
tree.jpg

Απάντηση

Επιστροφή στο “γλώσσες προγραμματισμού - γενικά”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης