Für die Kollisionsberechnung ist das allerdings nur als diskrete Lösung einsetzbar und bei diskreter Kollisionsberechnung, kann man eigentlich nur wirklich sicher sein, dass die korrekt funktioniert, wenn sich Objekte nicht bewegen. Wenn man bei bewegenden Objekten korrekte Ergebnisse haben will, dann braucht man einen kontinuirlichen Lösungsansatz.
Da habe ich mir bis jetzt noch keine Gedanken drüber gemacht, mir fällt aber zumindest ein Algorithmus ein der funktionieren müsste, jedoch recht naiv und unter Umständen noch mit nicht bedachten Edgecases (also mit Vorsicht genießen). 1. Erzeuge Triangulation (z.B. mit Delaunay Triangulation). O(n * log n) 2. Erzeuge neue Liste L an möglichen Mittelpunkten für den größten Kreis, befülle Liste mit Schwerpunkten aller erzeugten Dreiecke aus (1.). O(n) 3. Finde für jeden Punkt in L den nächsten Punkt aus der originalen Liste (Eingabepunkte). Naive wäre das O(n³), jedoch über einen Tree reduzierbar auf O(n * log n). 4. Bestimme die größte Distanz von den Punkten zu ihrem nächstgelegenen. O(n) Dieser Algorithmus hat so aber noch Probleme mit Dreiecken am Rand. Diese haben Kreise die die Konvexe Hülle verlassen würden. Kann man lösen indem die Mittelpunkte auf das jeweilige Segment der Konvexen Hülle projiziert werden und dort ein weiterer Punkt für die maximale Bestimmung der Distanz eingefügt wird.
@@Brotcrunsher Danke für die schnelle Antwort! Die Dreiecke am Rand würden mich nicht stören. Ich suche ja den größtmöglichen Kreis mit Mittelpunkt innerhalb der konvexen Hülle. Bei meiner Aufgabe stört es nicht, wenn die Kreislinie dann teilweise außerhalb der Hülle liegt. Die Lösungsschritte 1, 2, 4 kann ich leicht nachvollziehen. Ich habe jedoch keine Ahnung, wie man Schritt 3 auf O(n*log n) reduziert. Aber ich bin ja auch nicht der Brotcrunsher.
Kommt auf den Algorithmus an, aber in der Regel sind es eine Ansammlung an Dreiecken. Ist auch in O(n*log(n)) möglich. Vielleicht komme ich dazu irgendwann noch.
Du hattest mal ein Video zu Teamspeak Plugins hochgeladen. Dort gab es einen src Ordner mit einer vscode Datei, diesen gibt es jetzt allerdings nicht mehr. Könntest du mir bitte den Quellcode von einem deiner Plugins zuschicken? Ich muss mir einmalig die Mühe machen, ein Teamspeak Plugin zu schreiben, welches jedes Mal eine https Anfrage an meinen Server sendet, wenn ein Client anfängt oder aufhört zu sprechen. Noch habe ich gar keine Ahnung wie das geht und finde auch nirgends gute Tutorials. admin@ileies.de
"Der schnellere Algorithmus ist schneller" - Brotcrunsher, 2021
Wie würdest du es in C programmieren?
Warum unterscheide ich zwischen unterer und oberer konvexen Hülle?
Für die Kollisionsberechnung ist das allerdings nur als diskrete Lösung einsetzbar und bei diskreter Kollisionsberechnung, kann man eigentlich nur wirklich sicher sein, dass die korrekt funktioniert, wenn sich Objekte nicht bewegen. Wenn man bei bewegenden Objekten korrekte Ergebnisse haben will, dann braucht man einen kontinuirlichen Lösungsansatz.
Wie berechnet man den größtmöglichen Kreis mit Mittelpunkt innerhalb der konvexen Hülle, der keine der ursprünglichen Originalpunkte enthält?
Da habe ich mir bis jetzt noch keine Gedanken drüber gemacht, mir fällt aber zumindest ein Algorithmus ein der funktionieren müsste, jedoch recht naiv und unter Umständen noch mit nicht bedachten Edgecases (also mit Vorsicht genießen).
1. Erzeuge Triangulation (z.B. mit Delaunay Triangulation). O(n * log n)
2. Erzeuge neue Liste L an möglichen Mittelpunkten für den größten Kreis, befülle Liste mit Schwerpunkten aller erzeugten Dreiecke aus (1.). O(n)
3. Finde für jeden Punkt in L den nächsten Punkt aus der originalen Liste (Eingabepunkte). Naive wäre das O(n³), jedoch über einen Tree reduzierbar auf O(n * log n).
4. Bestimme die größte Distanz von den Punkten zu ihrem nächstgelegenen. O(n)
Dieser Algorithmus hat so aber noch Probleme mit Dreiecken am Rand. Diese haben Kreise die die Konvexe Hülle verlassen würden. Kann man lösen indem die Mittelpunkte auf das jeweilige Segment der Konvexen Hülle projiziert werden und dort ein weiterer Punkt für die maximale Bestimmung der Distanz eingefügt wird.
@@Brotcrunsher Danke für die schnelle Antwort! Die Dreiecke am Rand würden mich nicht stören. Ich suche ja den größtmöglichen Kreis mit Mittelpunkt innerhalb der konvexen Hülle. Bei meiner Aufgabe stört es nicht, wenn die Kreislinie dann teilweise außerhalb der Hülle liegt. Die Lösungsschritte 1, 2, 4 kann ich leicht nachvollziehen. Ich habe jedoch keine Ahnung, wie man Schritt 3 auf O(n*log n) reduziert. Aber ich bin ja auch nicht der Brotcrunsher.
Für Autos müsste ein Algorithmus für 3D-Punkte her. Ist de konvexe Hülle dabei eine Ansammlung von Ebenen?
Kommt auf den Algorithmus an, aber in der Regel sind es eine Ansammlung an Dreiecken. Ist auch in O(n*log(n)) möglich. Vielleicht komme ich dazu irgendwann noch.
@@Brotcrunsher Oh ja, bitte mach das dazu mal was, das wäre sicherelich auch sehr interessant!
Du hattest mal ein Video zu Teamspeak Plugins hochgeladen. Dort gab es einen src Ordner mit einer vscode Datei, diesen gibt es jetzt allerdings nicht mehr. Könntest du mir bitte den Quellcode von einem deiner Plugins zuschicken? Ich muss mir einmalig die Mühe machen, ein Teamspeak Plugin zu schreiben, welches jedes Mal eine https Anfrage an meinen Server sendet, wenn ein Client anfängt oder aufhört zu sprechen. Noch habe ich gar keine Ahnung wie das geht und finde auch nirgends gute Tutorials. admin@ileies.de