Anzahl von gerundeten Punkten bestimmen

[blablaman]

Hallo,

ich stehe hier vor einer kleinen Aufgabe. Ich habe eine Menge von Punkten, die ich auf eine bestimmte Anzahl von Nachkommastellen runden kann.

Die Anzahl der ungerundeten Punkte kann man schnell bestimmen. Wenn ich jetzt zum Beispiel die Punkte auf eine Nachkommastelle runde.

Bsp P1(1,33|2,34) -> (1,3|2,3)
P2(1,32|2,31) -> (1,3|2,3)
P1(1,53|2,64) -> (1,5|2,6)
P2(1,52|2,61) -> (1,5|2,6)


Dann würden vier Punkte zu zwei "zusammenfallen". Ich würde ja Punkt für Punkt durchgehen und vergleichen müssen und das in einer Liste abspeichern und die Listengröße dann bestimmen.

Gibt es da eine effiziente Lösung ?

Grüße


blablaman

 

[Quurks]

Vermutlich weniger.

Du köntest etwa so vorgehen:

1) Runde einen Punkt
2) Wenn Punkt nicht in Liste füge ihn in die Liste ein
3) Gehe solange noch Punkte vorhanden zu 1)

Als Liste würde ich dir eine LinkedList empfehlen.

 

[javimka]

Von wie vielen Punkten ist denn die Rede?

Wenn du alle n Punkte in einer Liste speicherst und sie danach durchgehst und jeden mit jedem vergleichst, dann läuft das in O(n^2). Für wenige Punkte ist das aber in Ordnung.

Etwas schneller (theoretisch) wäre es, wenn du die Liste sortierst (O(n*log n )) und dann einmal durchgehst (O(n)) und alle Punkte vergleichst. Aber du müsstest nach 2 Parametern sortieren, weil ein Punkt ja aus zwei Elementen besteht, das ist nicht so trivial.

Dann gibt es Datenstrukturen wie Segment-Tree oder Intervall-Tree, aber wenn du nicht mit mindestens 1000 Punkten arbeitest, sind das Kanonen für die Spatzenjagd

//EDIT
@Quurks
Warum LinkedList? Ich denke eine ArrayListe wäre der Aufgabe besser gewachsen. Sie ist viel schneller, wenn man einfach durchiterieren will. Die Stärke von LinkedList kommt zum Vorschein, wenn oft Elemente an beliebiger Stelle eingefügt oder gelöscht werden sollen.

 

[blablaman]

Danke für die schnelle Antworten erstmal.

Für ein Polygon habe ich jetzt zum Beispiel 520, wobei die Anzahl variiert.

Ich probiere das mal mit dem LinkedList Ansatz

Grüße


blablaman

 

[SlaterB]

@javimka
O(n) wäre, die gerundeten Punkte in ein HashSet einzufügen, entsprechenden hashcode() vorausgesetzt
Set entfernt/ erkennt Doppelte

 

[javimka]

@SlaterB
Du meinst, wenn er durch die Punkte durchiteriert (O(n)) soll er jeden einzelnen dem HashSet hinzufügen? Läuft das add() von Hashset denn in O(1)? Vorstellbar ist zwar, dass es amortisiert in O(1) läuft, aber ich glaube es nicht. Wenn es in O(logn) oder gar O(n) läuft, läuft das ganze ja dann auch nur in O(nlogn) oder O(n^2), dann ist nichts gewonnen. Ausser du willst darauf hinaus, dass man bereits existierende Algorithemn bevorzugen soll, anstatt das Rad neu zu erfinden

 

[SlaterB]

add() von Hashset läuft in O(1), ja, wobei dieses 1 durchaus zigmal größer sein kann als das 1 bei anderen Datenstrukturen,
aber konstanter Faktor interessiert ja weniger,
muss hier nicht breit diskutiert werden, aber wenn du schon O(x) aufzählst, dann schau dir ruhig mal Hash & Co. an

 

[javimka]

Habs mir angeschaut und in HashSet das gefunden:

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

Sieht nach ner Schleife aus, die in O(n) läuft . Jedenfalls auf den ersten Blick, aber ich lass mich auch gerne vom Gegenteil überzeugen.

 

[SlaterB]

Hashtabelle ? Wikipedia
die Schleife gehört zum Theme 'Kollisionen'

 

[javimka]

Habs ausprobiert und... du hast Recht
HashSet => O(n)