Konkavrumpf Alle Punkte des Polygons an der Grenze nehmen

Question

In meiner Arbeit muss ich eine zufällige Gruppe von Punkten in einer Grenze einschließen. Konvexer Rumpf nahm mehr Platz und war nicht engste Form, also modifizierte ich ihn, um die Kanten auf folgende Weise zu entspannen:

i) Zeichnen konvexe Hülle für die angegebene Anzahl von Punkten.

ii) Jetzt für jeden Punkt nicht auf der konvexen Rumpegrenze überprüfen, ob es an der Grenze hinzugefügt werden kann (natürlich, die Grenzformgebung ändert), während sicherstellen, dass keiner der angegebenen Punkte außerhalb des neuen liegt Polygonform. (Punkt im Polygonalgorithmus)

iii) Wenn alle Punkte innerhalb des Polygons liegen, wiederholen Sie Schritt 2 für einen anderen Punkt.

iv) Wenn kein weiterer Punkt in die Begrenzung eingefügt werden kann, stoppen Sie.

Jetzt ist das Problem bei jeder Probe Test-Set, alle Punkte werden in der Grenze enthalten. Meine Zweifel sind:

i) Ist das eine konkave Hülle?

ii) Worin unterscheidet sich das, wenn ich einfach die gegebenen Punkte entgegen dem Uhrzeigersinn anordne und alle Polygone zeichne und mehne, anstatt zuerst eine konvexe Hülle zu zeichnen?

iii) Stimmt es, dass ich für jede gegebene Anzahl von Punkten ein Polygon ohne Selbstschnitt durch sie zeichnen kann, so dass alle Punkte auf der Grenze des Polygons liegen?

Answer 1

Vorausgesetzt, dass Sie in einem 2D-Polytop interessiert sind (es kann nD sein;! Es ist nur einfacher zu erklären und 2D-Visualisierung), Sie müssen die vier einer Reihe von Punkten, die in der 'nicht-dominierten' Rumpf, die Sie suchen, ergeben. Warum vier Grenzen? Betrachten Sie das folgende Beispiel

Hinweis, dass Sie die vier Grenzen müssen (max vs. max, min vs. max, max vs. min und min vs. min), um voll und ganz die Polytop der Kanten zu definieren. Beachten Sie außerdem, ob der Rumpf konvex ist oder nicht, hängt von Ihren Punkten ab. Das obige Beispiel zeigt eine Grenze, die nicht konvex und nicht kontinuierlich ist, daher ist das Polytop auch nicht konvex und nicht kontinuierlich. Die Menge der vier Pareto-Grenzen umfasst die vollständige Polytopform.

Wenn Sie dies selbst implementieren möchten, ist es nicht so schlecht und erfordert nur den Vergleich jedes Punktes mit jedem Punkt, um ihre Achsen zu vergleichen und zu bestimmen, welcher Punkt beide Achsen in eine günstige Richtung vorschiebt. Dies wird als paarweiser Vergleich bezeichnet.

Für eine bereits codierte Lösung in C++, ist dies ein guter Ort https://github.com/kevinduh/pareto