Πολύπλοκος αλγόριθμος για εισαγωγή συντεταγμένων σε array

Σε αυτή την περιοχή μπορείτε να βρείτε ή να αναζητήσετε πληροφορίες σχετικές με την PHP

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

Απάντηση
trilos021
Δημοσιεύσεις: 131
Εγγραφή: 04 Νοέμ 2003 18:06

Πολύπλοκος αλγόριθμος για εισαγωγή συντεταγμένων σε array

Δημοσίευση από trilos021 » 04 Αύγ 2013 11:49

Καλησπέρα,

έχω ένα array στο οποίο έχω αποθηκεύσει κάποιες random συντεταγμένες. Ο πίνακας έχει τη παρακάτω μορφή:

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

Array ( 
[0] => Array ( [lat] => 38.900516 [lgn] => -77.076881 ) 
[1] => Array ( [lat] => 38.900491 [lgn] => -77.0768505 ) 
[2] => Array ( [lat] => 38.900466 [lgn] => -77.07682 ) 
[3] => Array ( [lat] => 38.9004775 [lgn] => -77.07677425 ) 
[4] => Array ( [lat] => 38.900489 [lgn] => -77.0767285 )....)
Αυτό που θέλω να κάνω είναι να εισάγω κάθε δέκατη τιμή του πίνακα σε ένα νέο array (δλδ το $array_new να περιέχει τιμές $array_old[0], $array_old[9]...κοκ). Το πρόβλημα είναι ότι κατά την εισαγωγή κάθε τιμής στο νέο πίνακα να ελέγχω αν υπάρχει ήδη συντεταγμένη μέσα στο νέο πίνακα η οποία να είναι λιγότερο από 20 μέτρα κοντά στη συντεταγμένη που πάω να εισάγω. Αν υπάρχει τέτοια συντεταγμένη να μην γίνει η εισαγωγή της "νεας" τιμής.

geomagas
Δημοσιεύσεις: 667
Εγγραφή: 06 Απρ 2013 13:36
Τοποθεσία: Ηράκλειο Κρήτης
Επικοινωνία:

Πολύπλοκος αλγόριθμος για εισαγωγή συντεταγμένων σε array

Δημοσίευση από geomagas » 04 Αύγ 2013 13:27

trilos021 έγραψε:Αυτό που θέλω να κάνω είναι να εισάγω κάθε δέκατη τιμή του πίνακα σε ένα νέο array (δλδ το $array_new να περιέχει τιμές $array_old[0], $array_old[9]...κοκ).
Αυτό που λες είναι "κάθε 9η τιμή".
Για κάθε 10η:

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

$new_array=array();
for&#40;$i=0;$i<count&#40;$old_array&#41;;$i=$i+10&#41;
  if&#40;!has_near&#40;$new_array,$old_array&#91;$i&#93;,20&#41;&#41;
    $new_array&#91;&#93;=$old_array&#91;$i&#93;;

function has_near&#40;$arr,$val,$d&#41;
  &#123;
  $has=False;
  $i=0;
  while&#40;!$has && &#40;$i<count&#40;$arr&#41;&#41;&#41;
    &#123;
    $has|=&#40;distance&#40;$val,$arr&#91;$i&#93;&#41;<$d&#41;;
    $i++;
    &#125;
  return $has;
  &#125;
Την distance() την έχεις ήδη.

alou
Script Master
Δημοσιεύσεις: 1374
Εγγραφή: 24 Αύγ 2007 19:52
Επικοινωνία:

Πολύπλοκος αλγόριθμος για εισαγωγή συντεταγμένων σε array

Δημοσίευση από alou » 04 Αύγ 2013 16:32

Μια σκέψη:
Πιθανώς αξίζει να εξετάσεις το ενδεχόμενο τέτοιες δουλειές να γίνονται από τη βάση σου πάντως, με κάποιες χιλιάδες σημεία, τέτοιες δουλειές ίσως να 'κοστίζουν ακριβά' στην php.

Αν και δεν έχω εμπειρία στα συγκεκριμένα data types της mysql, νομίζω ότι θα κάνουν τη ζωή σου πολύ πιο εύκολη αν έχεις απαιτήσεις για άντληση δεδομένων με ανάλογες προδιαγραφές:

http://dev.mysql.com/doc/refman/5.0/en/ ... abase.html

trilos021
Δημοσιεύσεις: 131
Εγγραφή: 04 Νοέμ 2003 18:06

Πολύπλοκος αλγόριθμος για εισαγωγή συντεταγμένων σε array

Δημοσίευση από trilos021 » 04 Αύγ 2013 17:11

η αλήθεια είναι ότι γίνονται 72εκατ. συνδιασμοί περίπου (σε ~3800 τιμές του πίνακα) μέχρι να φτιαχτεί ο νέος πίνακας. Υπάρχει τρόπος να εισάγω τα lat και lng σε βάση και να τα ταξινομίσω ανάλογα με την απόσταση πχ από το πρώτο σημείο?αν γίνει αυτό μετά επιλέγω ουσιαστικά κάθε 20 εγγραφές από τη βάση και δεν θα υπάρχουν κοντινά σημεία μεταξύ τους

geomagas
Δημοσιεύσεις: 667
Εγγραφή: 06 Απρ 2013 13:36
Τοποθεσία: Ηράκλειο Κρήτης
Επικοινωνία:

Πολύπλοκος αλγόριθμος για εισαγωγή συντεταγμένων σε array

Δημοσίευση από geomagas » 07 Αύγ 2013 16:11

Δύσκολα θα πειστώ ότι μία ΒΔ είναι κατάλληλη για τέτοιες δουλειές... Από κατασκευής, έχει άλλη αποστολή. Μπορεί να καταφέρεις να αποθηκεύσεις τα δεδομένα σου με μορφή/σειρά που θα σε βολεύει, αλλά οι queries που θα χρειαστεί να γράψεις θα είναι Βαβέλ...

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

Αν θέλεις να προσανατολιστείς προς τα εκεί, το link του alou είναι πολύ χρήσιμο (αν και θέλει πολύ διάβασμα, κι εγώ είμαι δίπλα στο κύμα :wink: ).

Πάντως, το καλύτερο θα ήταν να πεις τι θέλεις να κάνεις γενικότερα. Να έχουμε πιο σφαιρική όψη. Συγκεκριμένη πρόταση για λύση δεν θα βρεις αν "κοιτάμε από την κλειδαρότρυπα"...

Άβαταρ μέλους
greekbytes
WebDev Moderator
Δημοσιεύσεις: 2438
Εγγραφή: 15 Νοέμ 2002 15:42
Τοποθεσία: Αθήνα
Επικοινωνία:

Πολύπλοκος αλγόριθμος για εισαγωγή συντεταγμένων σε array

Δημοσίευση από greekbytes » 09 Αύγ 2013 10:21

Ρίχνω μια εναλλακτική..

Μπορείς να δεις την MongoDB, που έχει build in δυνατότητες για geospatial indexing/searching. Δεν την έχω δοκιμάσει για κάτι τέτοιο, αλλά εχω ακούσει πολύ καλά λόγια.

http://www.mongodb.org/

http://docs.mongodb.org/manual/applicat ... l-indexes/

Άβαταρ μέλους
jpk
Δημοσιεύσεις: 441
Εγγραφή: 09 Μαρ 2011 21:17

Πολύπλοκος αλγόριθμος για εισαγωγή συντεταγμένων σε array

Δημοσίευση από jpk » 09 Αύγ 2013 15:13

Ρίξε μια ματιά στο
http://stackoverflow.com/questions/2234 ... mplex-calc

Το συγκεκριμένο το βρήκα τώρα , ψάχνοντας να σου στείλω κάτι σχετικό με αυτό που χρησιμοποιώ εγώ και χωρίς να σε μπλέξω. Αν θες να συζητήσουμε για την θεωρία που κρύβει πες το. Λίγο πολύ είναι ένα proximity query μεταξύ δύο σημείων με latitude longitude σε miles. Λέω λίγο πολύ για πολλούς λόγους που αν θες τους συζητάμε. (Αν το proximity query των spatial της mysql γινόταν με πιο αποδοτικό τρόπο σε επίπεδο geographical points σίγουρα θα το προτιμούσα)

Από απόδοση αν ο πίνακας που έχει το latitude longitude έχει indexes σε αυτά (χωριστά) , είσαι πολύ καλά . Χρησιμοποιώ κάτι που βασίζεται στην ίδια λογική σε πραγματικά πολυσύχναστο site , καιρό τώρα και με σωστά indexes στα join νομίζω ότι δεν υπάρχει πρόβλημα απόδοσης. Σίγουρα το τι θες πραγματικά να κάνεις (που δεν το πολυκατάλαβα) παίζει ρόλο , άλλη λύση υπάρχει ανάλογα τις απαιτήσεις της εφαρμογής σου τόσο σε επίπεδο δόμησης δεδομένων και χρήσης τους όσο και σε επίπεδο υλοποίησης εφαρμογής.

Άβαταρ μέλους
nirvana
Δημοσιεύσεις: 241
Εγγραφή: 01 Σεπ 2005 18:28
Τοποθεσία: Αγ. Παρασκευή

Πολύπλοκος αλγόριθμος για εισαγωγή συντεταγμένων σε array

Δημοσίευση από nirvana » 11 Αύγ 2013 01:10

To thema einai kathe pote tha kaneis auti tin douleia? Tha einai mia kai eksw ('i telos pantwn 1-2 fores tin mera me ena cronjob)? 'I se kathe request tha prepei na kaneis autous tous ypologismous?

An einai 1 kai eksw, egw tha proteina na vreis mia vivliothiki se php kai na kaneis apla tin douleia sou.

An tha exeis kapoio xristi pou tha perimenei apotelesma kathe fora, nomizw oti prepei na prosanatolisteis allou, giati i php sigoura xolenei (typou geospatial indexing kai searching me mongo db 'i kapoio searching software typou Solr). Episeis to array me tis syntetagmenes tha allazei syxna? Giati me auta ta software, oti allazei xreiazetai re-indexing, i opoia einai mia sxetika xronovora/epiponi diadikasia pou ginetai me to skeptiko oti oti ton xrono spatalas apo sto indexing, to kerdizeis sto query. Ena akoma zitima einai, eisai diatethimenos na spataliseis xrono (gia ekpaidefsi) kai resources gia na xrisimopoiiseis kapoia texnologia san kai autes? Egw proswpika exw xrisimopoiisei to solr gia auti tin douleia. Einai poly kalo software, alla den tha sou krypsw oti vasanistika poly gia na to mathw.

B.t.w molis eida to link tou jpk. Fainetai na exei para poly endiaferon. Sigoura tha to diavasw molis vrw ligo xrono! Auto pou skeftomai einai oti to arthro xrisimopoiei mia statheri aktina tis gis, to opoio fovamai oti tha deixnei megalyteres apostaseis stous polous kai mikroteres ston isimerino se sxesi me tin pragmatiki apostasi.

Άβαταρ μέλους
nirvana
Δημοσιεύσεις: 241
Εγγραφή: 01 Σεπ 2005 18:28
Τοποθεσία: Αγ. Παρασκευή

Πολύπλοκος αλγόριθμος για εισαγωγή συντεταγμένων σε array

Δημοσίευση από nirvana » 11 Αύγ 2013 03:02

Pragmati se ena allo site pou vrika (andrew.hedges.name/experiments/haversine/) xrisimopoiei ton idio tropo kai leei:
Note: this formula does not take into account the non-spheroidal (ellipsoidal) shape of the Earth. It will tend to overestimate trans-polar distances and underestimate trans-equatorial distances. The values used for the radius of the Earth (3961 miles & 6373 km) are optimized for locations around 39 degrees from the equator (roughly the Latitude of Washington, DC, USA).
O jpk to anefere vevaia:
Λίγο πολύ είναι ένα proximity query μεταξύ δύο σημείων με latitude longitude σε miles.
Apla, egw to episimainw, afou, an i efarmogi einai pagkosmia 'i prepei na einai poly akrivis, prepei na eimaste idiaitera prosektikoi :).

Άβαταρ μέλους
jpk
Δημοσιεύσεις: 441
Εγγραφή: 09 Μαρ 2011 21:17

Πολύπλοκος αλγόριθμος για εισαγωγή συντεταγμένων σε array

Δημοσίευση από jpk » 14 Αύγ 2013 17:57

Υπάρχουν δυο τρία πολύ ενδιαφέροντα με αυτό το θέμα χωρίς να μπω στην βαθιά θεωρία . Το πρώτο είναι ότι η Γη δεν είναι τόσο πεπλατυσμένη όσο νομίζουμε. Η αντίληψή μας για την Γη συνήθως έρχεται από χάρτες που αποτυπώνουν δυσδιάστατα ένα τρισδιάστατο αντικείμενο παραλληλόγραμμα.

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

Εν τέλει , αυτό το χρησιμοποιώ σε site παγκόσμιο. Αν δεις πάνω στην σφαίρα τις αποκλείσεις που έχει αυτή η συνάρτηση με αυτές του Bessel ή του Ηayford θα καταλάβεις ότι όσο είσαι πιο κοντά στον ισημερινό τόσο καλύτερα τα πάει η απλή προσέγγιση.

Σίγουρα οι χρήστες είναι πιο κοντά στον ισημερινό, και για κάποιους που είναι στην Αλάσκα ή στην Γροιλανδία τα 100 χιλιόμετρα λάθος ακόμα και να υπάρχουν δεν είναι ζήτημα. (Λιγότερα είναι αλλά δεν είμαι πρόχειρος να τα μετρήσω)

Από αυτό κρατάω ότι σε κάποια φάση που θα έχω χρόνο θα μετατρέψω τις συναρτήσεις Bessel-Hayford σε query, αλλά και ακόμα και ένα query να μην είναι μπορεί να είναι μια χαρά ένα καλό stored procedure.

Απάντηση

Επιστροφή στο “PHP Προγραμματισμός”

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

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