Betrachten Sie ein sich möglicherweise selbst schneidendes Polygon, das durch eine Liste von Scheitelpunkten im 2D-Raum definiert wird. Z.B
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
Es gibt mehrere Möglichkeiten, die Fläche eines solchen Polygons zu definieren, aber die interessanteste ist die Gerade-Ungerade-Regel. Zeichnen Sie für einen beliebigen Punkt in der Ebene eine Linie vom Punkt bis ins Unendliche (in eine beliebige Richtung). Wenn diese Linie das Polygon ungerade oft schneidet, ist der Punkt Teil der Fläche des Polygons. Wenn sie das Polygon gerade oft schneidet, ist der Punkt nicht Teil des Polygons. Für das obige Beispielpolygon sind hier sowohl der Umriss als auch der gerade und ungerade Bereich:
Das Polygon ist im Allgemeinen nicht orthogonal. Ich habe nur ein so einfaches Beispiel gewählt, um das Zählen der Fläche zu erleichtern.
Die Fläche in diesem Beispiel ist 17
(nicht 24
oder 33
wie andere Definitionen oder Flächen ergeben könnten).
Beachten Sie, dass unter dieser Definition die Fläche des Polygons unabhängig von seiner Wicklungsreihenfolge ist.
Die Herausforderung
Bestimmen Sie anhand einer Liste von Eckpunkten mit ganzzahligen Koordinaten, die ein Polygon definieren, dessen Fläche nach der Gerade-Ungerade-Regel.
Sie können eine Funktion oder ein Programm schreiben, Eingaben über STDIN oder die nächstgelegene Alternative, ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis entweder zurückgeben oder an STDOUT oder die nächstgelegene Alternative ausgeben.
Sie können Eingaben in beliebigen Listen- oder Zeichenfolgenformaten vornehmen, sofern diese nicht vorverarbeitet wurden.
Das Ergebnis sollte entweder eine Gleitkommazahl sein, die auf 6 signifikante (Dezimal-) Stellen genau ist, oder ein rationales Ergebnis, dessen Gleitkommadarstellung auf 6 signifikante Stellen genau ist. (Wenn Sie rationale Ergebnisse erzielen, sind diese wahrscheinlich genau, aber ich kann dies nicht verlangen, da ich keine genauen Ergebnisse als Referenz habe.)
Sie müssen in der Lage sein, jeden der folgenden Testfälle innerhalb von 10 Sekunden auf einem vernünftigen Desktop-Computer zu lösen. (In dieser Regel gibt es einen gewissen Spielraum. Wenn es auf meinem Laptop 20 Sekunden dauert, gebe ich Ihnen den Vorteil des Zweifels, wenn es eine Minute dauert, werde ich es nicht tun.) Ich denke, diese Grenze sollte sehr großzügig sein, aber es soll Ansätze ausschließen, bei denen Sie das Polygon nur auf einem ausreichend feinen Raster diskretisieren und zählen, oder probabilistische Ansätze wie Monte Carlo verwenden. Seien Sie ein guter Sportler und versuchen Sie nicht, diese Ansätze so zu optimieren, dass Sie das Zeitlimit trotzdem einhalten können. ;)
Sie dürfen keine vorhandenen Funktionen verwenden, die sich direkt auf Polygone beziehen.
Dies ist Codegolf, daher gewinnt die kürzeste Übermittlung (in Bytes).
Annahmen
- Alle Koordinaten sind ganze Zahlen im Bereich
0 ≤ x ≤ 100
,0 ≤ y ≤ 100
. - Es wird mindestens
3
und höchstens50
Eckpunkte geben. - Es wird keine wiederholten Eckpunkte geben. Auch werden keine Eckpunkte auf einer anderen Kante liegen. (Es kann jedoch kollineare Punkte in der Liste geben.)
Testfälle
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
17.0000
{{22, 87}, {6, 3}, {98, 77}, {20, 56}, {96, 52}, {79, 34}, {46, 78}, {52, 73}, {81, 85}, {90, 43}}
2788.39
{{90, 43}, {81, 85}, {52, 73}, {46, 78}, {79, 34}, {96, 52}, {20, 56}, {98, 77}, {6, 3}, {22, 87}}
2788.39
{{70, 33}, {53, 89}, {76, 35}, {14, 56}, {14, 47}, {59, 49}, {12, 32}, {22, 66}, {85, 2}, {2, 81},
{61, 39}, {1, 49}, {91, 62}, {67, 7}, {19, 55}, {47, 44}, {8, 24}, {46, 18}, {63, 64}, {23, 30}}
2037.98
{{42, 65}, {14, 59}, {97, 10}, {13, 1}, {2, 8}, {88, 80}, {24, 36}, {95, 94}, {18, 9}, {66, 64},
{91, 5}, {99, 25}, {6, 66}, {48, 55}, {83, 54}, {15, 65}, {10, 60}, {35, 86}, {44, 19}, {48, 43},
{47, 86}, {29, 5}, {15, 45}, {75, 41}, {9, 9}, {23, 100}, {22, 82}, {34, 21}, {7, 34}, {54, 83}}
3382.46
{{68, 35}, {43, 63}, {66, 98}, {60, 56}, {57, 44}, {90, 52}, {36, 26}, {23, 55}, {66, 1}, {25, 6},
{84, 65}, {38, 16}, {47, 31}, {44, 90}, {2, 30}, {87, 40}, {19, 51}, {75, 5}, {31, 94}, {85, 56},
{95, 81}, {79, 80}, {82, 45}, {95, 10}, {27, 15}, {18, 70}, {24, 6}, {12, 73}, {10, 31}, {4, 29},
{79, 93}, {45, 85}, {12, 10}, {89, 70}, {46, 5}, {56, 67}, {58, 59}, {92, 19}, {83, 49}, {22,77}}
3337.62
{{15, 22}, {71, 65}, {12, 35}, {30, 92}, {12, 92}, {97, 31}, {4, 32}, {39, 43}, {11, 40},
{20, 15}, {71, 100}, {84, 76}, {51, 98}, {35, 94}, {46, 54}, {89, 49}, {28, 35}, {65, 42},
{31, 41}, {48, 34}, {57, 46}, {14, 20}, {45, 28}, {82, 65}, {88, 78}, {55, 30}, {30, 27},
{26, 47}, {51, 93}, {9, 95}, {56, 82}, {86, 56}, {46, 28}, {62, 70}, {98, 10}, {3, 39},
{11, 34}, {17, 64}, {36, 42}, {52, 100}, {38, 11}, {83, 14}, {5, 17}, {72, 70}, {3, 97},
{8, 94}, {64, 60}, {47, 25}, {99, 26}, {99, 69}}
3514.46
quelle
upath
Operator analysieren kann . (Es ist eigentlich eine extrem einfache 1: 1-Konvertierung zwischen den Trennzeichen. Wird}, {
einfach entferntlineto
und das Komma zwischen x und y wird entfernt und die öffnenden und schließenden Klammern werden durch eine statische Kopf- und Fußzeile ersetzt ...)upath
undlineto
klingt es, als würden Sie die Eingabe tatsächlich vorverarbeiten. Dh Sie nehmen keine Koordinatenliste, sondern ein tatsächliches Polygon.CrossingPolygon
.Antworten:
Mathematica,
247,225,222Fügen Sie zuerst die Schnittpunkte zum Polygon hinzu und kehren Sie dann einige der Kanten um. Anschließend kann die Fläche genau wie bei einem einfachen Polygon berechnet werden.
Beispiel:
quelle
{1,2},{4,4},{4,2},{2,4},{2,1},{5,3}
? Sie sollten mit 3.433333333333309 herauskommen. Ich habe nach einer ähnlichen Logik gesucht.103/30
, und der numerische Wert ist3.43333
.Python 2,
323319 BytesNimmt eine Liste von Eckpunkten durch STDIN als komplexe Zahlen in der folgenden Form
und schreibt das Ergebnis nach STDOUT.
Gleicher Code nach dem Ersetzen der Zeichenfolge und etwas Abstand:
Erläuterung
Führen Sie für jeden Schnittpunkt zweier Seiten des Eingabepolygons (einschließlich der Scheitelpunkte) eine vertikale Linie durch diesen Punkt.
(Tatsächlich übergibt das Programm aufgrund des Golfspiels ein paar Zeilen mehr; es spielt keine Rolle, solange mindestens diese Zeilen übergeben werden.) Der Körper des Polygons zwischen zwei aufeinanderfolgenden Zeilen besteht aus vertikalen Trapezoiden ( und Dreiecke und Liniensegmente, als Sonderfälle davon). Es muss der Fall sein, da, wenn eine dieser Formen einen zusätzlichen Scheitelpunkt zwischen den beiden Basen hätte, es eine weitere vertikale Linie durch diesen Punkt zwischen den beiden fraglichen Linien geben würde. Die Summe der Flächen aller solcher Trapezoide ist die Fläche des Polygons.
So finden wir diese Trapezoide: Für jedes Paar aufeinanderfolgender vertikaler Linien finden wir die Segmente jeder Seite des Polygons, die (ordnungsgemäß) zwischen diesen beiden Linien liegen (die für einige der Seiten möglicherweise nicht vorhanden sind). In der obigen Abbildung sind dies die sechs roten Segmente unter Berücksichtigung der beiden roten vertikalen Linien. Beachten Sie, dass sich diese Segmente nicht richtig kreuzen (dh sie treffen sich möglicherweise nur an ihren Endpunkten, fallen vollständig zusammen oder kreuzen sich überhaupt nicht, da, wenn sie sich richtig kreuzen, eine weitere vertikale Linie dazwischen liegen würde;) und so ist es sinnvoll darüber zu sprechen, sie von oben nach unten zu ordnen, was wir tun. Nach der Gerade-Ungerade-Regel befinden wir uns innerhalb des Polygons, sobald wir das erste Segment überquert haben. Sobald wir den zweiten überqueren, sind wir raus; der dritte ist wieder da; der vierte raus; und so weiter...
Insgesamt ist dies ein O ( n 3 log n ) -Algorithmus.
quelle
Haskell, 549
Es sieht nicht so aus, als könnte ich dieses Spiel weit genug runter spielen, aber das Konzept war anders als die beiden anderen Antworten, also dachte ich, ich würde es trotzdem teilen. Es führt rationale O (N ^ 2) -Operationen durch, um die Fläche zu berechnen.
Beispiel:
Die Idee ist, das Polygon an jeder Kreuzung neu zu verdrahten, was zu einer Vereinigung von Polygonen ohne sich überschneidende Kanten führt. Wir können dann den (vorzeichenbehafteten) Bereich jedes der Polygone unter Verwendung der Gauss-Formel für Schnürsenkel berechnen ( http://en.wikipedia.org/wiki/Shoelace_formula ). Die Gerade-Ungerade-Regel verlangt, dass beim Konvertieren einer Kreuzung die Fläche des neuen Polygons im Verhältnis zum alten Polygon negativ gezählt wird.
Betrachten Sie beispielsweise das Polygon in der ursprünglichen Frage. Die Kreuzung oben links wird in zwei Pfade umgewandelt, die sich nur an einem Punkt treffen. Die beiden Pfade sind beide im Uhrzeigersinn ausgerichtet, sodass die Bereiche jedes Pfads positiv wären, wenn wir nicht deklarieren, dass der innere Pfad gegenüber dem äußeren Pfad mit -1 gewichtet ist. Dies entspricht der Pfadumkehr von alphaalpha.
Als weiteres Beispiel betrachten wir das Polygon aus MickyTs Kommentar:
Hier sind einige der Polygone im Uhrzeigersinn und einige gegen den Uhrzeigersinn ausgerichtet. Die Vorzeichen-Kipp-Kreuzungsregel stellt sicher, dass die im Uhrzeigersinn ausgerichteten Bereiche einen zusätzlichen Faktor von -1 aufnehmen, wodurch sie einen positiven Beitrag zur Fläche leisten.
So funktioniert das Programm:
quelle