Ευρεση γρηγοροτερου μονοπατιου

[khr1s]

Γεια σας παδια!

 

Εχει κολησει το μυαλο μου και δεν μπορω να σκεφτω και θα θελα λιγη βοηθεια.

 

Εχω μεσα σε ενα ArrayList τις συντεταγμενες των κορυφων ενος πολυγωνου(το οποιο ειναι το ελαχιστο σχημα που περικλειει καποια σημεια, σημαντικο αυτο). Αυτες τις κορυφες τις βρηκα μεσω QuickHull.

 

Επισης 2 απο τις κορυφες αυτες ειναι η  Start και η End, τις οποιες τις εχω και μεσα στο arraylist τυπου point μαζι με τις αλλες αλλα και ξεχωριστα σε 2 μεταβλητες τυπου point(με ενα Χ και ενα Υ).

 

Aυτο που θελω ειναι να με βοηθησει καποιος στο πως θα βρω μεσω πoιας φορας κινησης θα παω πιο γρηγορα απο την κορυφη Start στην End.

 

 

Σκεφτηκα να βρω την εξισωση της μπλε ευθειας και επειτα να ταξινομησω τα απο πανω της στοιχεια ως προς το Χ μεσα σε ενα νεο arraylist και τα απο κατω ως προς Χ παλι σε ενα νεο arraylist και να μετρησω την αποσταση απο το ενα μεχρι το αλλο.

 

Καμια γνωμη ?

 

Edit: Ξεχασα να πω οτι χρησιμοποιω java.

[Kercyn]

Γιατί δε φτιάχνεις ένα γράφο με τα σημεία σου και να κάνεις traverse αυτόν;

 

https://en.wikipedia.org/wiki/Dijkstra's_algorithm

 

EDIT: Υπέθεσα ότι μπορείς να χρησιμοποιήσεις τα καφέ points, αν μπορείς να κινηθείς μόνο στην πράσινη γραμμή, κάνε αυτό που λέει ο albNiK.

[albNik]

Aυτο που θελω ειναι να με βοηθησει καποιος στο πως θα βρω μεσω πoιας φορας κινησης θα παω πιο γρηγορα απο την κορυφη Start στην End.

Απλα θα υπολογίσεις τις δυο διαδρομες και θα τις συγκρίνεις.

[Kercyn]

Κάτι άλλο, το hull σου γιατί είναι concave; Ένα σημείο κάτω αριστερά γιατί συμμετέχει στο hull όταν είναι ξεκάθαρα πιο μέσα; Αυτό που έχω βάλει σε κύκλο μου φαίνεται πιο μέσα από τα άλλα δύο αλλά δεν είμαι σίγουρος.

 

[khr1s]

Κάτι άλλο, το hull σου γιατί είναι concave; Ένα σημείο κάτω αριστερά γιατί συμμετέχει στο hull όταν είναι ξεκάθαρα πιο μέσα. Αυτό που έχω βάλει σε κύκλο μου φαίνεται πιο μέσα από τα άλλα δύο αλλά δεν είμαι σίγουρος.

 

Χωρίς τίτλο.png

 

Το Hull που ποσταρα το εφτιαξα προχειρα στο paint. Δεν ειναι κανονικο προσπαθησα με το ματι να το φτιαξω.

 

Αρα παω για γραφο, δεν υπαρχει κατι πιο γρηγορο και μη περιπλοκο προγραμματιστικα, σωστα ?

[Kercyn]

Αν όντως μπορείς να χρησιμοποιήσεις τα καφέ σημεία και δεν είσαι περιορισμένος στην πράσινη γραμμή, νομίζω ότι είναι πολύ απλό πρόβλημα αν χρησιμοποιήσεις γράφο.

[khr1s]

Οχι, μονο τα εξωτερικα σημεια πανω στο πολυγωνο πρεπει να χρησιμοποιησω για να παω απο το ενα κοκκινο στο αλλο .

[V.I.Smirnov]

Υπάρχουν πολλοί τρόποι.

Αν θέσεις τα σημεία των περιμέτρων σε δυο γράφους, ένα για το "πάνω" τμήμα και ένα για το "κάτω", μπορείς εύκολα να βρεις την συντομότερη διαδρομή με τον αλγόριθμο του Dijkstra.

Ή σε έναν γράφο μόνον, ο οποίος όμως θα είναι κατευθυντικός.

 

Απλούστερος τρόπος είναι να συγκρίνεις τα μήκη των δύο διαδρομών start->end, μια φορά με ωρολογιακή σάρωση ("πάνω") και τη δεύτερη με αντιωρολογιακή ("κάτω").

Εναλλακτικά μπορείς να θεωρήσεις τα δυο πολύγωνα που ορίζει το τμήμα (start,end), η συντομότερη διαδρομή θα ανήκει σε εκείνο με την μικρότερη περίμετρο...

Δεν νομίζω πάντως ότι χρειάζεται γράφος για κάτι τόσο απλό.

 

-

[groot]

Γεια σας παδια!

 

Εχει κολησει το μυαλο μου και δεν μπορω να σκεφτω και θα θελα λιγη βοηθεια.

 

Εχω μεσα σε ενα ArrayList τις συντεταγμενες των κορυφων ενος πολυγωνου(το οποιο ειναι το ελαχιστο σχημα που περικλειει καποια σημεια, σημαντικο αυτο). Αυτες τις κορυφες τις βρηκα μεσω QuickHull.

 

Επισης 2 απο τις κορυφες αυτες ειναι η  Start και η End, τις οποιες τις εχω και μεσα στο arraylist τυπου point μαζι με τις αλλες αλλα και ξεχωριστα σε 2 μεταβλητες τυπου point(με ενα Χ και ενα Υ).

 

Aυτο που θελω ειναι να με βοηθησει καποιος στο πως θα βρω μεσω πoιας φορας κινησης θα παω πιο γρηγορα απο την κορυφη Start στην End.

 

 

Σκεφτηκα να βρω την εξισωση της μπλε ευθειας και επειτα να ταξινομησω τα απο πανω της στοιχεια ως προς το Χ μεσα σε ενα νεο arraylist και τα απο κατω ως προς Χ παλι σε ενα νεο arraylist και να μετρησω την αποσταση απο το ενα μεχρι το αλλο.

 

Καμια γνωμη ?

 

Edit: Ξεχασα να πω οτι χρησιμοποιω java.

Με τα σημεία που το συνολικό distance από την μπλε ευθεία είναι μικρότερο.

 

Δηλαδή, στο σχήμα έχεις δύο επιλογές. Αριστερόστροφα ή δεξιόστροφα. Για κάθε route, μετράς το distance (π.χ. mean square error φάση) κάθε σημείου από την μπλε ευθεία. Το σταθμίζεις με τον αριθμό των σημείων για να μην σε επηρεάζει πόσα σημεία θα έχεις.

 

Το route με το μικρότερο error θα είναι το πιο σύντομο.

 

 

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

 

public double distanceFromLine(Point lineStart, Point lineEnd);

και με τα streams της Java 8 έχεις one liner τον υπολογισμό.

[khr1s]

Με τα σημεία που το συνολικό distance από την μπλε ευθεία είναι μικρότερο.

 

Δηλαδή, στο σχήμα έχεις δύο επιλογές. Αριστερόστροφα ή δεξιόστροφα. Για κάθε route, μετράς το distance (π.χ. mean square error φάση) κάθε σημείου από την μπλε ευθεία. Το σταθμίζεις με τον αριθμό των σημείων για να μην σε επηρεάζει πόσα σημεία θα έχεις.

 

Το route με το μικρότερο error θα είναι το πιο σύντομο.

 

 

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

 

public double distanceFromLine(Point lineStart, Point lineEnd);

και με τα streams της Java 8 έχεις one liner τον υπολογισμό.

 

 

 

Βρηκα την μεθοδο αυτη:

public double getDistanceToLine(Point a, Point  
{
   return Math.abs((b.getX() - a.getX()) * (a.getY() - this.y) - (a.getX() - this.x) * (b.getY() - a.getY()))
                / Math.sqrt(Math.pow(b.getX() - a.getX(), 2) + Math.pow(b.getY() - a.getY(), 2));
 }

Λες δηλαδη αρχικα να ελεγξω ενα ενα τα σημεια για το αν ειναι κατω ή πανω απο την γραμη.

Επειτα για ολα τα πανω σημεια και ολα τα κατω να βρω τις αποστασεις αυτες και να τις προσθεσω και επειτα να κανω την συγκριση μεταξυ τους?

 

Και μετα να παω απο σημειο σε σημειο(μεσω μια ταξινομισης με βαση την τιμη του Χ για καθε σημειο) για να βρω και το μηκος της διαδρομης?

 

Αν καταλαβα καλα.

[eaglej]

Πληροφορική ΑΠΘ σπουδάζεις ? Αν πήρες έτοιμο τον quickhull δες πως σου τυπώνει τα σημεία!

[groot]

Ή, ακόμα πιο απλά, αντί για Point μπορείς να έχεις Line. Δεν φτιάχνεις μία List αλλά δύο. Μία για αριστερά και μια για δεξιά.

 

Εάν δε κάνεις την Line να χωράει μέσα της ενδιάμεσα Point τότε έχεις μόνο δύο Line αντί για List και μία μέθοδο της Line απλά συγκρίνεις το συνολικό μήκος.

 

 

Δηλαδή, στην Line θα έχεις μία μέθοδο:

 

public void addPoint(Point pointToAdd) {
  // check if the new point is at the end

  // if not at the end, find previous and adjust total length

  // if at the end, append it and adjust length
}

public void addPoints(List<Point> pointsToAdd) {
  ListIterator itPoint = pointsToAdd.listIterator();
  while (itPoint.hasNext())
    this.addPoint(itPoint.next());
}

Οπότε, όταν υπολογίσεις το σχήμα σου και ξέρεις το start point για τον υπολογισμό που θέλεις, απλά περνάς τα σημεία σε δύο Line και συγκρίνεις total lengths.