Binäre suche für 2D Punkte



  • Ich habe eine Menge von Punkten (int x, int y), die ich mir zuerst merken möchte und dann zu einem späteren Zeitpunkt herausfinden möchte ob ein angefragter punkt (int xLater, int yLater) unter den gemerkten punkten ist oder nicht.
    Als code in etwa so:

    awesomeClass.add(someRandom_x, someRandom_y);
    
    if(awesomeClass.contains(someSpecified_x, someSpecified_y)) {
       //blupp
    }
    

    Einen unkomplizierten Vorschlag wie man das lösen kann? Am liebsten mit Vector. Ich hatte an einen Binärbaum gedacht, nur kann man da irgendwie schlecht 2D-Punkte einsortieren.



  • std::set und std::unordered_set tun genau das, was du willst.



  • Bevor die Frage kommt, wie du zweidimensionale Objekte ins Set bekommst: std::tuple bzw. std::pair .



  • ProblemSteller schrieb:

    Ich hatte an einen Binärbaum gedacht, nur kann man da irgendwie schlecht 2D-Punkte einsortieren.

    Warum soll das nicht gehen?



  • manni66 schrieb:

    ProblemSteller schrieb:

    Ich hatte an einen Binärbaum gedacht, nur kann man da irgendwie schlecht 2D-Punkte einsortieren.

    Warum soll das nicht gehen?

    Man muss die punkte ja irgendwie sortieren, damit man sie im baum wiederfindet und mir kam gleich in den sinn, dass man 2d punkte nicht sortieren kann, oder?



  • Problemsteller schrieb:

    manni66 schrieb:

    ProblemSteller schrieb:

    Ich hatte an einen Binärbaum gedacht, nur kann man da irgendwie schlecht 2D-Punkte einsortieren.

    Warum soll das nicht gehen?

    Man muss die punkte ja irgendwie sortieren, damit man sie im baum wiederfindet und mir kam gleich in den sinn, dass man 2d punkte nicht sortieren kann, oder?

    Wie würdest du Wörter sortieren?



  • @Problemsteller
    Wenn du bloss exakte Übereinstimmungen finden musst, dann ist das kein Problem.
    Dazu kannst du ne map oder ne unordered_map nehmen - ziemlich egal.

    Und klar kann man 2D Koordinaten sortieren.

    Etwas schwieriger wird es dann erst wenn du keine exakte Übereinstimmungen mehr hast, sondern anfängst benachbarte Punkte zu suchen.


Log in to reply