Sechseck - Fläche reloaded

Guten Abend

Folgendes ist gegeben:
Man hat ein 2D-Gitternetz wo jedes Element eine Kooridnate hat.
Beginnen tut es bei (1,1) und ist irrelevant groß (n, m).
Nun wird ein Mittelpunkt auf dem Gitter erstellt.
Dieser liegt beispielsweiße auf M(45, 77) oder einfacher: M(100, 100).
Nun muss um den Mittelpunkt ein Sechseck gezeichnet werden:
m.X = 100;
m.Y = 100;
r = 33;
r_i = (r/2)*wurzel(3) - (hab leider gerade kein Taschenrechner).
Demnach sind die beiden Seiten, die parallel zur X Achse sind:
m.Y + 33 und m.Y - 33.
http://img97.imageshack.us/img97/3683/sechseck.jpg

Wie bestimme ich nun welche Elemente (mit X und Y Kooridnate) innerhalb des Sechsecks liegen?

Ich würde mich über jede Hilfe freuen.

SeppJ

Eine grobe Vorgehensweise die mir gerade einfällt:

-Außerhalb des Umkreises außerhalb des Sechsecks
-Innerhalb des Innkreises im Sechseck
-Dazwischen: Man stelle die Geradengleichungen der Kanten auf und prüfe auf welcher Seite der Punkt ist.

Klingt nicht gerade mathematisch elegant, dafür aber eher was für Rechenfaule. Es gibt aber bestimmt noch eine schönere Lösung.

volkard

-Dazwischen würde ich vielleicht mit atan2 schauen, welche Kante maßgeblich ist. Nur mit den Geradengleichungen zu hantieren, wäre mir zu schwierig.

Jan

Ich würde die Winkel zu den Kantenmitten bestimmen (falls das Sechseck mal nicht in der gezeigten Orientierung liegt) und dann prüfen, ob der Abstand des Punktes vom Mittelpunkt entlang dieser 6 Richtungen kleiner ist als der Kantenabstand zum Mittelpunkt.
Sollte eigentlich relativ einfach umzusetzen sein.

edit: Und wenn es nicht so früh am Morgen wäre, würde ich das sogar nur für 3 Richtungen prüfen, um mir Arbeit zu sparen....

-Dazwischen würde ich vielleicht mit atan2 schauen, welche Kante maßgeblich ist. Nur mit den Geradengleichungen zu hantieren, wäre mir zu schwierig.

Was macht atan2 genau?
Ich verstehe die Erklärung nicht bzw. kann es nicht auf meine Frage beziehen.

SeppJ

atan2 liefert dir zu einem Koordinatenpaar den Winkel zum Ursprung. Wenn du den Winkel kennst, brauchst du nur die dazugehörige Kante zu prüfen und nicht alle 6.

Um zu prüfen ob ein Punkt links oder rechts von einer Geraden ist, kann man beispielsweise das Kreuzprodukt zwischen Richtungsvektor der Gerade und dem Punkt (mit dem Stützvektor der Geraden als Ursprung) bilden und gucken, ob dieses in positive oder negative z-Richtung zeigt.

edit2: Falls das ganze nur eine theoretische Handlungsvorschrift sein soll, kann man sich dann auch gleich das Prüfen mit den Umkreisen sparen und mit dem passenden Winkel gleich auf rechts/links prüfen. Falls das Problem praktisch mit einem Computer gelöst werden soll, würde ich aber trotzdem erstmal die Abstände prüfen, da atan2 doch eine recht aufwändige Rechenoperation ist.

Seppel

Oder unterteilen in 6 dreiecke und jeweils testen, ob der punkt im dreieck liegt (siehe z.B. http://www.blackpawn.com/texts/pointinpoly/default.html).

den punkt immer im ersten quadranten betrachten, d.h. den punkt g.g.f. um ein vielfaches von 60 grad zurückdrehen, falls winkel > 90.
zwei gleichungen für den abstand vom mittelpunkt zur kontur in abhängikeit von phi und x aufstellen. die erste gleichung ist für winkel 0 <= phi <= 60, die zweite für winkel 60 < phi <= 90.
dann gucken wir uns den abstand des punktes an und vergleichen in in abhängigkeit von phi mit einer der beiden abstandsgleichungen.

knivil

Nur mit den Geradengleichungen zu hantieren, wäre mir zu schwierig.

Kann ich nicht bestaetigen. Left-of Vergleich an allen Geraden gegen den Uhrzeigersinn. Dabei wird die Richtung hier von P1 nach P2 genommen. Je nachdem ob der Punkt auf einer Kante als Innerhalb gezaehlt werden soll, verwendet man >= bzw. > . Jetzt nur noch ueber die 6 Eckpunkte iterieren und gut ist. Dieses vorgehen kann fuer alle konvexen Vielecke verwendet werden.

class Point
{
  private:
    double m_x,m_y;
  ...
  public:
    Point(const Point& p);
    Point operator-(const Point& p) const;

    // liegt dieser Punkt(this) links von Punkt p1 und p2
    bool leftOf(const Point& p1, const Point& p2) const;
  ...
};

bool Point::leftOf(const Point& p1, const Point& p2) const
{
  Point r(*this - p1);
  Point q(p2 - p1);
  return (q.m_x*r.m_y - q.m_y*r.m_x) > 0;
}