Anzahl der Dreiecke mit N Punkten innerhalb

Question

Gegeben einige Punkte in der Ebene (bis zu 500 Punkte), keine 3 kollinear. Wir müssen die Anzahl der Dreiecke bestimmen, deren Ecken aus den gegebenen Punkten stammen und die genau N Punkte in ihnen enthalten. Wie man dieses Problem effizient löst? Der naive O (n^4) -Algorithmus ist zu langsam. Jeder bessere Ansatz?

Answer 1

Sie könnten versuchen, das Dreieck als Schnittpunkt von drei Halbräumen zu denken. Um die Anzahl der Punkte innerhalb eines Dreiecks A, B, C zu ermitteln, betrachten Sie zuerst die Menge der Punkte auf einer Seite der unendlichen Linie in Richtung AB. Lassen Sie diese setzen L (AB) und R (AB) für Punkte von links und rechts. Ähnlich verhält es sich mit anderen zwei Kanten und Build-Sets L (AC) und R (AC) und setzt L (BC) und R (BC).

Also die Anzahl der Punkte in ABC wird die Anzahl der Punkte im Schnittpunkt von L (AB), L (AC) und L (BC) sein. (Sie könnten R (AB) stattdessen in Abhängigkeit von der Ausrichtung des Dreiecks betrachten).

Nun, wenn wir den vollen Satz von 500 Punkten betrachten wollen. Nimm zuerst alle Paare von Punkten AB und konstruiere die Mengen L (AB) und R (AB). Dies wird O (n^3) Operationen benötigen.

Als nächstes testen wir alle Dreiecke und finden die Schnittpunkte der drei Sätze. Wenn wir eine Hash-Tabellenstruktur für die Sätze verwenden, dann ist das Auffinden der Schnittpunkte wie eine Hashtabellen-Suche. Wenn L (AB) 1 Elemente hat, hat L (AC) m Elemente und L (BC) n Elemente. Sag l> m> n. Für jeden Punkt in L (BC) müssen wir einen Suchvorgang in L (AC) und L (BC) durchführen, so dass maximal 2n Hashtable-Lookups möglich sind.

Es könnte schneller sein, eine geometrische Lookup-Tabelle zu berücksichtigen. Teilen Sie Ihre gesamte Domäne in ein grobes Gitter, sagen Sie ein 10 mal 10 Raster. Wir können dann jeden Punkt in eine Menge G (i, j) setzen. Wir können dann die Mengen L (AB) in jede Rasterzelle aufteilen. Sagen Sie, rufen Sie diese Sätze L (AB, i, j) und R (AB, i, j). Beim Testen auf Kreuzungen wird zuerst trainiert, welche Gitterzellen in der Kreuzung liegen. Dies reduziert den Suchraum drastisch und da jede Menge L (AB, i, j) weniger Mitglieder enthält, wird es weniger Hashtabellen-Suchvorgänge geben.

Answer 2

Eigentlich stieß ich kürzlich auf ein ähnliches Problem, aber der einzige Unterschied war, dass es rund 300 Punkte gab und ich löste es mit Bitset (C++ STL). Für jedes Punktepaar, sagen wir (x [i], y [i]) und (x [j], y [j]), habe ich einen Bitsatz gebildet < 302> B [i] [j] und B [i] [j] [k] speichert 1, wenn der k-te Punkt über dem Liniensegment von Punkt i zu Punkt j liegt, sonst würde ich 0 speichern.

Jetzt in einer brutalen Art und Weise bekomme ich drei Punkte, um ein Dreieck zu bilden, Nehmen wir an (x [i], y [i]), (x [j], y [j]) und (x [k], y [k]), dann wäre ein Punkt, ein z-ter Punkt innerhalb des Dreiecks, wenn B [i] [j] [z] == B [i] [j] [k] & & B [j] [k] [z] == B [j] [k] [i] & & B [k] [i] [z] == B [k] [i] [j] weil ein Punkt innerhalb des Dreiecks ein ähnliches Zeichen zeigt eine Seite des Dreiecks als dritter Punkt des Dreiecks (eines, das nicht auf dieser Seite ist). Also bekomme ich drei Bitset-Variablen P = B [i] [j], Q = B [j] [k] und R = B [k] [i] und dort dort bitweise UND dann anwenden count() -Funktion zu geben mir die aktive Anzahl der Bits und damit die Anzahl der Punkte innerhalb des Dreiecks. Aber vergewissere dich, dass du die Variable P so änderst, dass sie B [i] [j] [k] = 1 ergibt, wenn du dann nicht bitweise (~) von dieser Variablen nimmst.

Obwohl die obige Lösung problemspezifisch ist, hoffe ich, dass es hilft. Dies ist das Problem Link: http://usaco.org/current/index.php?page=viewproblem&cpid=660