Polygon innerhalb des Polygon-Generalisierungsproblems

Ich möchte mich bei allen unten stehenden Beiträgen entschuldigen. Habe das falsche Forum ausgewählt, um dies ursprünglich zu posten. Anstatt dies jedoch zu einer völligen Verschwendung zu machen, habe ich die Frage zu einem echten "Theoretischen Informatik" -Problem überarbeitet.

Problem: Erstellen Sie einen Algorithmus, der eine Menge von n geordneten Punkten in einer 2D-Ebene verwendet, die die Kontur eines einfachen Polygons A bilden, das konkav sein kann oder nicht, und ein neues Polygon B mit m Punkten erstellt, so dass:

Alle Punkte in A sind in B enthalten
3 <= m <n
B ist das Polygon in der Menge aller Bs mit der kleinsten Fläche
B muss ein einfaches Polygon sein (dh keine Selbstüberschneidungen).
Die Eingabe in den Algorithmus ist Polygon A und "m".
Das Zusammentreffen von Segmenten in B mit Segmenten in A ist zulässig.

Einige Beispieleingaben und erwartete Ausgaben:

Wenn A ein Quadrat und m 3 ist, wäre B das Dreieck mit der kleinsten Oberfläche, die A enthält.
Wenn A ein Sechseck und m 4 ist, wäre B ein Viereck mit der kleinsten Oberfläche, die A enthält.

Viel Glück an alle, die dieses Problem ausprobieren. Ich kann Ihnen versprechen, dass dies besonders jetzt sehr schwierig sein wird, da die Lösung optimal sein muss.

ds.algorithms cg.comp-geom polygon Thirlan
quelle

@Joe: Nicht wahr: Wenn A ein Quadrat ist, fragt Thirian nach dem Dreieck mit der minimalen Fläche, das A enthält. Wenn A dagegen ein Dreieck ist ( ), gibt es tatsächlich keine gültige Lösung.

n = 3

$n=3$

Jeffs

Füge 17 zu meinem ersten Kommentar hinzu, denke ich. Warum 20?

Jeffs

Ist FFT nicht eine niedrige Schwelle für "kompliziert"?

Sasho Nikolov

Ich denke nicht, dass es völlig richtig ist, dass sich das Problem überhaupt nicht ändert, wenn Sie (sagen wir) m = 3 setzen. Das Problem ist, dass Sie möglicherweise eine exponentielle Zeit in m benötigen, und das ist in Ordnung, wenn m auf eine bestimmte Zahl festgelegt ist. ist aber nicht in Ordnung, wenn m Teil der Eingabe ist.

Suresh Venkat

"Jeder weiß, was das Problem ist" ist nicht wahr. Wir fragen, weil die nicht angegebenen Entscheidungen einen Unterschied machen.

Suresh Venkat

Antworten:

Ich weiß nicht, wie Ihre Polygone aussehen, aber vielleicht reicht eine vereinfachte Version des Ramer-Douglas-Peucker-Algorithmus aus:

$A_j$ $P_i P_{i+1} P_{i+2}$
Berechnen Sie für jeden konkaven Teil die Fläche der beiden Dreiecke $B_k$ $P_i P'_i P_{i+1}$ $P_{i+1} P'_{i+2} P_{i+2}$ $P_i, P_{i+2}$ $P_{i+1}$
$min\{A_j,B_k\}$
$n-m$

Geben Sie hier die Bildbeschreibung ein
$A_j$ $B_k$

Für komplexere Algorithmen können Sie nach " Polygon-Generalisierungstechniken " suchen, obwohl Ihre erste Bedingung (Punkte in A sind in B enthalten) einige zusätzliche Skalierungsoperationen impliziert.

Marzio De Biasi
quelle

@ Suresh: Ich bin mir ziemlich sicher, dass die aktuellen 4 Upvotes für die Transparenz sind, nicht für den (fast trivialen) Algorithmus :)

Marzio De Biasi

Dies hat das gleiche Problem wie die Ramer-Douglas-Peucker-Algorithmen: Es wird nicht garantiert, dass die Ausgabe ein einfaches Polygon ist!

Jeffs

@ Jeffe: Sie haben Recht, aber (alles andere als optimal, wenn das Polygon komplex ist) kann man Vereinfachungen vermeiden, die zu einem Konflikt führen . Wenn am Ende andere Punkte entfernt werden müssen, aber ein nicht einfaches Polygon nicht vermieden werden kann, verwenden Sie eine Konfliktlösungsmethode (berechnen Sie beispielsweise Schnittpunkte und verwerfen Sie die "Löcher" vollständig). Ich würde jedoch gerne ein echtes Beispiel aus dem OP sehen.

Marzio De Biasi

@MarzioDeBiasi Das könnte funktionieren. Aber es könnte nicht. Ich denke, es ist möglich, dass jede von Ihnen beschriebene Vereinfachung eine Selbstüberschneidung verursacht. Und "Loops rauswerfen" kann die Dinge nicht besser, sondern schlimmer machen. Dies ist in der Praxis wahrscheinlich eine gute Lösung, aber denken Sie daran, wo wir sind!

Jeffs

Danke Marzio, ich weiß jetzt zumindest, wie diese Probleme jetzt heißen! Leider ist die von Ihnen angegebene Lösung die, die (3) und (4) in meinen Lösungsvorschlägen enthalten, und (4) hat ein Problem damit. Elipsen, die sehr gedehnt sind und daher scharfe Spitzen mit Winkeln von ungefähr 30 Grad und weniger haben, verstoßen leicht gegen die Anforderungen (1).

Thirlan

Ich habe vor langer Zeit einen Artikel geschrieben, in dem ein linearer Zeitalgorithmus zum Finden des kleinsten Flächendreiecks mit einer Punktmenge (oder einem Polygon) beschrieben wurde:

J. O'Rourke, Alok Aggarwal, Sanjeev Maddila, Michael Baldwin, "Ein optimaler Algorithmus zum Auffinden minimaler umschließender Dreiecke", J. Algorithms , 1986, 7 : 258-269. Link .

Unsere Arbeit wurde von einem allgemeinen Algorithmus gefolgt:

"Minimale Fläche, die Polygone umschreibt", Alok Aggarwal, JS Chang und Chee K. Yap, The Visual Computer , Band 1, Nummer 2 (1985), 112-117. Link .

Sie können Google Scholar verwenden, um die späteren Artikel zu verfolgen, in denen diese zitiert werden, um Verbesserungen und verwandte Arbeiten zu finden.

Joseph O'Rourke
quelle