computational-geometry

Fragen
ist ein Zweig der Informatik gewidmet dem Studium von Algorithmen, die in Bezug auf die Geometrie angegeben werden kann.
8
Antworten

Wählen Sie Rechtecke mit maximaler Schnittfläche

In diesem Problem ist r eine feste positive ganze Zahl. Sie erhalten N Rechtecke mit derselben Größe in der Ebene. Die Seiten sind entweder vertikal oder horizontal. Wir nehmen an, dass der Bereich des Schnittpunkts aller N Rechtecke einen Nicht...
18.08.2011, 10:09
3
Antworten

Punktposition in Tetraedernetzen

Gibt es irgendwelche erprobten Datenstrukturen für die Punktpositionierung in Tetraedernetzen, in denen die Tetraeder alle disjunkt sind, sich aber "berühren"? I.e. Die meisten Gesichter sind Gesichter von genau zwei Tetraedern. Nach OrtIch m...
07.08.2012, 15:41
5
Antworten

Erzeugen von Punkten in einem Bereich mit mindestens X Zwischenraumlänge dazwischen

Ich versuche, eine Methode zu finden, mit der ich eine Menge zufälliger Punkte in einem bestimmten Bereich (in meinem Fall ein Quadrat) erzeugen kann. Die eine Sache, die das zu einem solchen Problem macht, ist, dass jeder Punkt mindestens Y Ein...
20.06.2011, 16:25
5
Antworten

Wie bricht man eine Geometrie in Blöcke?

Ich bin mir sicher, dass es bereits einen Algorithmus gibt, der das tut, was ich brauche, aber ich bin mir nicht sicher, welcher Satz für Google oder welche Algorithmuskategorie es ist. Hier ist mein Problem: Ich habe ein Polyeder, das aus me...
03.06.2015, 22:21
1
Antwort

Schneller Ellipsoid (s) -Kreuzungsalgorithmus

Nehmen wir an, ich habe 1 Million willkürlich geformte, willkürlich orientierte N-dimensionale Ellipsoide, die zufällig durch den N-dimensionalen Raum verteilt sind. Bei einer Untermenge von Ellipsoiden möchte ich "schnell" die Menge aller Ellip...
10.06.2011, 00:05
1
Antwort

Gibt es eine effiziente Möglichkeit, die Anzahl der Schnittpunkte in einer gegebenen Menge von Liniensegmenten zu zählen?

Angenommen, ich habe n Liniensegmente in der allgemeinen Position. Wie kann ich schnell für jedes meiner n Segmente bestimmen, wie viele der anderen n-1 es schneidet? Ich kann das naiv in O (n 2 ) Zeit machen. Ich kann alle Schnittpunkte mit...
23.12.2012, 06:06
3
Antworten

Glätten Sie eine konvexe polygonale Form, so dass sie so groß wie möglich wird, während der Durchmesser beibehalten wird

Angesichts eines konvexen Polygons versuche ich, seine Form zu vergrößern (wie in "maximaler Bereich"), während ich den Durchmesser beibehalte. Der Durchmesser ist definiert als die Länge des längsten Segments, das innerhalb des Polygons platzie...
14.09.2010, 08:31
5
Antworten

Approximieren eines Polygons mit einem Kreis

Nun, die Annäherung eines Kreises mit einem Polygon und die Geschichte von Pythagoras mögen gut bekannt sein. Aber was ist umgekehrt? Ich habe einige Polygone, das sollten Kreise sein. Dies ist jedoch aufgrund von Messfehlern nicht der Fall....
12.02.2013, 14:21
3
Antworten

effizienter Algorithmus, um den nächsten Punkt in einem Graphen zu finden, der keine bekannte Gleichung hat

Ich stelle diese Fragen aus Neugier, denn meine schnelle und schmutzige Umsetzung scheint gut genug zu sein. Aber ich bin gespannt, was eine bessere Umsetzung wäre. Ich habe eine Grafik von realen Daten. Es gibt keine doppelten X-Werte und de...
22.07.2011, 14:46
4
Antworten

Der nächste Punkt auf einer Karte

Ich mache ein Programm, mit dem Sie auf eine Karte klicken können, um eine "Nahaufnahme" der Umgebung zu sehen, z. B. in Google Maps. Wenn ein Benutzer auf die Karte klickt, erhält er die X- und Y-Koordinate, auf die er geklickt hat. Nehme...
18.08.2011, 18:33