programming και μαθηματικό πρόβλημα

[crmaris]

Το πρόβλημα που αντιμετωπίζω δεν έχει να κάνει με μια συγκεκριμένη γλώσσα προγραμματισμού αλλά είναι κυρίως μαθηματικό. Λοιπόν έχω μια συνδεσμολογία δικτύου από 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;

κάθε βοηθεια παιδιά ευπρόσδεκτη γιατί έφαγα όλη την μέρα σήμερα και άκρη δεν έβγαλα.

[DarkSaga]

recursive για τα δυο νεα childs που θέλεις να ταξινομήσεις μάλλον

και αποθηκευση σαν bubble sort

[bold]

ελα ρε συ ευκολο ειναι!!! (πλακα κανω -εκανα μιση ωρα να καταλαβω τι θες)

ισως αυτο που ψαχνεις να ειναι αυτο:

...Orientation in 3D of a point relative to a plane?

[crmaris]

thanks πάρα πολύ παιδιά για τις απαντήσεις σας. Θα τα ψάξω και τα δυο που μου λέτε για να δω μπας και κάνω τίποτα.. Μιλάμε χτες έφαγα όλη την μέρα με αυτό το πράγμα και άκρη δεν κατάφερα να βγάλω.

[crmaris]

Αρχική απάντηση από bold [Σήμερα, στις 16:09]

ελα ρε συ ευκολο ειναι!!! (πλακα κανω -εκανα μιση ωρα να καταλαβω τι θες)

ισως αυτο που ψαχνεις να ειναι αυτο:

...Orientation in 3D of a point relative to a plane?

τώρα πρόσεξα ότι είναι για 3D επίπεδα μόνο και όχι για 2D (το λέει και ο τίτλος του άλλωστε). Οπότε δεν κάνει. Θέλει τροποποίηση ο κώδικας που έβαλα για 3 σημεία ώστε να δέχεται παραπάνω αλλά από μαθηματικά δεν σκαμπάζω και πολλά

[crmaris]

εδώ η λύση σε αυτό που είχα ρωτήσει.. Την είχα καιρό τώρα αλλά βαριόμουν το γράψιμο

Για να βρούμε το orientation (πιο είναι πιο αριστερά, κέντρο, πιο δεξιά ) όλων των child nodes ενός node σε καρτεσιανό επίπεδο συντεταγμένων και έστω ότι γνωρίζουμε φυσικά τις συντεταγμένες (x,y) των nodes χρησιμοποιούμε τον παρακάτω κώδικα.

Καταρχήν η function orientation

function Tform1.Orientation(x,x1,x2: Integer): Integer;

var

Orin: Double;

node,node1,node2:Tnode;

begin

with Graphlist do

begin

node:=TNode(objects[x]);

node1:=TNode(objects[x1]);

node2:=TNode(objects[x2]);

(* Linear determinant of the 3 points *)

Orin := (node2.x - node1.x) * (node.y - node1.y) - (node.x - node1.x) * (node2.y - node1.y);

if Orin > 0.0 then Result := +1 (* Orientation is to the left-hand side *)

else if Orin < 0.0 then Result := -1 (* Orientaion is to the right-hand side *)

else

Result := 0; (* Orientation is neutral if result is 0 *)

end; // tis with

end;

και η function ColumnSortdescending

function ColumnSortDescending(List: TStringList; Index1, Index2: Integer): Integer;

var

int1,int2:integer;

begin

// get the strings to compare

int1 := strtoint(Copy(List[index1],0,5));

int2 := strtoint(Copy(List[index2],0,5));

if int1<int2 then result:=1

else if int1>int2 then result:=-1

else if int1=int2 then result:=0;

end; // function Column...

τις οποίες χρησιμοποιώ παρακάτω..

Έστω ότι το node έχει 4 child nodes και list η λίστα με τους αναγνωριστικούς αριθμούς των nodes (για παράδειγμα το node 1 (κεντρικό) έχει child τα nodes 2,3,4,5 )

v,j:integer; {μεταβλητές για τις for}

vert1,vert2:integer; {οι αναγνωριστικοι αριθμοί των nodes}

list,list1,list2:TstringList; {λίστες όπου αποθηκεύω τα nodes,orientation κτλ.}

orin:Integer {η sum τιμή του orientation για κάθε node}

if list.count=4 then // αν τα child nodes είναι τέσσερα

begin

for v:= 0 to List.Count - 1 do

begin

for j:=0 to List.Count - 1 do

begin

if v<>j then

begin

w:=list[v];

w1:=list[j];

vert1:=strtoint(copy(w,1,5));

vert2:=strtoint(copy(w1,1,5));

list1.add(format('%2d%4d%4d',[orientation(vert1,vert2,temp.index),vert1,vert2]));

end; // tis if

end; // tis for j=0

end; // tis for v=0

{ μέχρι εδώ βρήκα το orientation των node μεταξύ τους (πχ το 2 με το 3, το 2 με το 4, το 2 με το 5 κτλ). Η list1 θα έχει την μορφή

2 3 1(η τιμή του orientation)

2 4 1

2 5 1

Αυτό που πρέπει να κάνω τώρα είναι να προσθέσω όλα τα αποτελέσματα orientation τώρα για κάθε node και μετά να τα συγκρίνω μεταξύ τους. Το πιο αριστερό θα έχει την πιο θετική τιμή (πχ 3) και το πιο δεξιό την πιο αρνητική (πχ -3)}

v1:=0;

v2:=list1.Count div list.count; // για lisτ.count=4 το v2=3

repeat

orin:=0;

for v := v1 to v2-1 do // παίρνω ανά τρεις γραμμές την list και προσθέτω

begin

w:=list1[v];

v3:=strtoint(copy(w,1,2));

vert1:=strtoint(copy(w,3,4));

orin:=v3+orin;

end;

list2.add(format('%5d%4d',[orin,vert1]));

list2.customSort(@ColumnSortdescending);

{στην list2 βάζω τα child nodes με την τελική τιμή του orientation και μετά κάνω sort ξεκινώντας από την μεγαλύτερη τιμή προς την μικρότερη}

if list2.Count=4 then

begin

//showmessage(list2.gettext);

w:=list2[0];

w1:=list2[1];

w2:=list2[2];

w3:=list2[3];

temp.left_child:=strtoint(copy(w,6,4)); //το τέρμα αριστερό child

temp.left_child1:=strtoint(copy(w1,6,4)); // το αμέσως πιο αριστερό child

temp.right_child:=strtoint(copy(w2,6,4)); // το δεξί child

temp.right_child1:=strtoint(copy(w3,6,4)); // το τέρμα πιο δεξιό child

list2.clear;

end;

//to pio arnitiko einai deksia

//to pio thetiko einai aristera

inc(v1,list1.Count div list.count);

inc(v2,list1.Count div list.count);

until v2>list1.count ;

end; // tis if list.count =4

στο δικό μου πρόγραμμα μπορώ και βρίσκω το orientation για μέχρι 12 child nodes σε κάθε node..

και ένα παράδειγμα

Εδώ έχουμε την έξοδο της list2 {showmessage(list2.gettext). Βλέπουμε ότι η τιμή για το node 7 είναι 3 (τέρμα αριστερά) για το node 13 είναι 1(αμέσως πιο αριστερά) για το node 32 είναι -1 και για το node 8 είναι -3 (τέρμα δεξιά)..

Αυτά

[mariosalice]

Εξαρτάται ποιος είναι ο άξονας που κοιτάζεις.

Στο πρώτο παράδειγμα που έχεις θα σου δώσει αποτέλεσμα που θα σου απαντάει στο ερώτημα αν το σημείο p(x,y) βρίσκεται στην ίδια ευθεία με τα άλλα δύο σημεία ή αν βρίσκεται δεξιά ή αριστερά από την ευθεία που σχηματίζουν τα δύο σημεία 1(x,y) & 2(x,y), κοιτώντας από το δεύτερο σημείο το πρώτο.

Δiαφορετικά, αν κοιτάζεις θετικά στον άξονα των y, δεν σου χρειάζονται οι τιμές y και το πρόβλημα λύνεται πανεύκολα χρησιμοποιώντας μόνο τις τιμές 1x, 2x, 3x ... nx.

Δεν είδα τον κώδικα σου στο τελευταίο ποστ, αλλά αν κρίνω από το πρώτο ποστ κάτι δεν μου πάει καλά από μια πρώτη ματιά.

[crmaris]

το παραπάνω δουλευει σε ολους τους αξονες-συντεταγμενες και ειναι δοκιμασμενο σε προγραμμα το οποιο κανει simulation αλγοριθμους δικτύων.. Αν δεν ήτανε δοκιμασμένο ή δεν έτρεχε σωστά δεν θα έμπαινα καν στον κόπο να γράψω όλα το παραπάνω κατεβατό..

Με μια ματιά κατάφερες και έβγαλες ετημυγορία για τον κώδικά μου.. Sorry για το ύφος της απάντησης αλλά πρέπει να τον δεις πολύ καλύτερα τον κώδικα από μια απλή ματιά για να καταλάβεις αν δουλεύει σωστά η όχι.. Επίσης η function orientation στηρίζεται στο εσωτερικό γινόμενο δυο διανυσμάτων και παίρνει υπόψην και χ και y.. Στο πρόβλημα μου χρειαζόμουνα μια λύση που να δουλεύει και στους δυο άξονες ταυτόχρονα και όχι να παίρνω κάθε μια φορά ως προς ένα άξονα.. Πάντως αν έχεις κάποια βελτίωση στον κώδικά μου να κάνεις ή να ποστάρεις κάτι σέ άλλη γλώσσα που να λύνει το παραπάνω πρόβλημα ευχαρίστως να την δούμε..

[mariosalice]

Στο πρόγραμμα σου πού και πώς ορίζεται ο άξονας αναφοράς?

Αυτό δεν είδα.

Για παράδειγμα, αν ο άξονας αναφοράς είναι η ευθεία p(x,y) 1(x,y), δηλαδή από τον αρχικό κό κόμβο κοιτάμε τον πρώτο κόμβο, τότε το πρόγραμμα σου θα βγάλει αποτέλεσμα?

Δηλαδή δεν είδα να ορίζεις τον πρώτο κόμβο αναφοράς που θα καθορίσει τον άξονα.

Αντίθετα, το πρόγραμμα στο πρώτο ποστ αποτελεί και τη λύση που θέλεις, γιατί σου δίνει τον άξονα αναφοράς (την ευθεία), που είναι η 2->1.

Αρκεί να αλλάξεις τα ονόματα (να γίνει το σημείο 2 σημείο p, το σημείο 1 το σημείο αναφοράς που θα δηλώνει τον άξονα, και το σημείο p να γίνει σημείο 2) και να βάλεις στο πρόγραμμα μεταβλητές.

Μετά θα σου δίνει το αποτέλεσμα για κάθε κόμβο που ζητάς αν είναι δεξιά ή αριστερά από τον άξονα που ορίζεις.

Δηλαδή έστω ότι ορίζεις από τον κόμβο p μια ευθεία προς τον κόμβο 4 και θέλεις να μάθεις αν ο κόμβος 6 είναι δεξιά ή αριστερά του άξονα p->4.

Αυτό θα σου το δείξει μια χαρά το πρόγραμμα που έχεις στο πρώτο ποστ και μπορεί να λειτουργήσει για όσους κόμβους θέλεις και σε όποιο άξονα θέλεις.

Αυτό που νομίζω ότι δεν κατάλαβες στο πρώτο πρόγραμμα είναι ότι σου δίνει τον άξονα που είναι 2->1 και σου βγάζει αποτέλεσμα αν το σημείο p είναι δεξιά, αριστερά ή στην ίδια ευθεία με τον άξονα 2->1.

[crmaris]

τώρα κατάφερα και μπήκα στο forum γιατί εδώ και 4 μερες στην Μυτιλήνη δεν είχαμε net (μέσω πανεπιστημίου) λόγω ΟΤΕ.. Και μετά μιλάμε για ευρυζονικότητα.. Στο πρόγραμμά μου και στο function το σημείο αναφοράς (και όχι άξονας ) είναι οι συντεταγμένες του root node.. Βάση αυτού βρίσκουμε πιο child node ειναι πιο αριστερά κτλ.. Το γινόμενο που βλέπεις στο fuction με τις συντεταγμένες βγάζει την πραγματική γωνία κάθε διανύσματος (νομίζω arctan ). Το πρόγραμμά μου βγάζει αποτελέσματα για μέχρι και 12 child nodes (checked).. Επίσης κατάλαβα πολύ καλά τι κάνει το πρώτο function και στο γράφω κιόλας (βάση του εσωτερικού γινομένου των διανυσμάτων βρίσκει την θέση τους στο χώρο ως προς το σημείο αναφοράς).. Εγώ ήθελα όμως να βρίσκω παραπάνω από 2 nodes orientation οπότε έκανα ένα συνδιασμό του function με έναν αλγόριθμο ταξινόμησης και όλα ok..