Έλεγχος επικαλυπτώμενων παραληλογράμων σε gmap

[jimmysnn_17]

Καλησπέρα σας,
σε βάση δεδομένων έχω καταχωρήσεις από τις συντεταγμένες σημείων σε χάρτη (latitude/ longitude). Για κάθε σημείο φτιάχνω ένα παραλληλόγραμο και καταχωρώ στη βάση τις συντεταγμένες των σημείων του παραληλογράμου (νοτιοδυτικο σημείο και βορειοανατολικό). Θέλω να ελέγξω αν υπάρχουν επικαλυπτώμενα παραλληλόγραμα και αν υπάρχουν να φτιάχνω ένα μεγαλύτερο που να περιέχει όλα τα σημεία. Καμία ιδέα πως μπορεί να υλοποιηθεί? Είτε με ερώτημα MySQL είτε με java?

Ευχαριστώ!

 

[DeltaLover]

Δες αυτα τα links:

 

http://stackoverflow.com/questions/2628118/rectangles-covering

 

http://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other?rq=1

 

http://stackoverflow.com/questions/5919298/algorithm-for-finding-the-fewest-rectangles-to-cover-a-set-of-rectangles?rq=1
 

[jimmysnn_17]

Καταρχάς ευχαριστώ πολύ για την απάντηση σου.
Το αν δύο ή περισσότερα παραλληλόγραμα επικαλύπτωνται το βρίσκω με πολλούς τρόπους, no problem. Αυτό που δεν μπορώ να καταλάβω είναι, αν έχω για παράδειγμα 3 παραλληλόγραμα που επικαλύπτωναι,  πως θα βρω τις συντεταγμένες απο το νέο  παραλληλόγραμο που θα περιλαμβάνει και τα 3 σημεία.

 

Για το κάθε σημείο χρησιμοποιώ αυτή τη συνάρτηση για να φτιάξω το παραλληλόγραμο:
http://stackoverflow.com/questions/2151645/draw-polygon-x-meters-around-a-point/2159804#2159804

 

[DeltaLover]

Ειναι ευκολο να λυσεις το προβλημα σου:

 

1) Εστω οτι ολα τα παραλληλογραμμα ειναι σε μια λιστα με το ονομα : to_process

 

2) Ορισε μια λιστα με παραλληλογραμμα με το ονομα already_processed

 

3) Επαναλαβε την παρακατω διαδικασια μεχρι to_process να μεινει αδεια

 

    για το πρωτο item της to_process ψαξε σειριακα ολα τα επομενα μεχρι να β    ρεις overlap
       
    Αν δεν βρεις overlap αφαιρεσε το item αυτο απο to_process και προσθεεσε το στην already_processed  
    Αν βρεις overlap τοτε φτιαξε ενα νεο rectangle που να επικαλυπτει τα δυο αυτα, δηλαδη το πανω αριστερα σημειο θα εχει τα ελαχιστα χ,ψ απο τα δυο ενω το κατω αριστερα τα μεγιστα

 

    Αφαιρεσε και τα δυο αυτα απο to_process και προσθεσε σε αυτο το καινουργιο μεγαλο rectangle

 

    Συνεχισε μεχρι οπως ειπαμε να μην εχεις τιποτα στο to_process

 

4) Οταν η διαδικασια αυτη τελειωσει η λιστα already_processed εχει τα ζητουμενα rectangles

 

Προσεξε ομως, αυτη δεν ειναι η βελτιστη αλγοριθμικα λυση, ειναι αυτο που λεμε brutal solution κατι που ειναι καλο για μικρο αριθμο rects. Αν προκειται να εχεις πολυ μεγαλο αριθμο rects πρεπει να δωσεις πιο γρηγορη λυση, διαβαζωντας τα links που εβαλα παραπανω..  Μπορω να σκεφτω και αλλη λυση η οποια δεν περιεχεται στα λινκς αλλα χρησιμοποιει προχωρημενα data structures πως graphs και ισως genetic algorithms αλλα για την ωρα δεν αξιζει να μπερδευτεις με αυτα...

 

[jimmysnn_17]

Ευχαριστώ πολύ για τη βοήθεια!

[DeltaLover]

νο προβλεμ jimmy... 

[pmav99]

Υπάρχουν και βιβλιοθήκες που μπορούν να το κάνουν αυτό

http://www.vividsolutions.com/jts/jtshome.htm