Verlängern 2d Polygon durch Vektor

Question

I konvexen Polygonen, und ich möchte, dass sie verlängern, indem wie so entlang eines Vektors Projizieren: (. Ursprüngliche Polygon und der Vektor auf der linken Seite, gewünschte Ergebnis auf der rechten Seite)

Meine Polygone werden als eine Reihe von Punkten mit Linkslauf gespeichert. Was ich finden möchte, ist der "Start" - und "Stop" -Punkt, von dem ich projizieren muss, wie in den eingekreisten Ecken unten.

(Die grünen Pfeile sind die Polygon-Wicklung, um anzuzeigen, die „Richtung“ jeder Kante zu geben.)

My ursprünglichen Plan zu bestimmen war, welche durch Projizieren eines Strahls mit dem Vectors Richtung zu verwenden, um Punkte aus jeden Punkt und den ersten und letzten Punkt zu finden, dessen Strahl eine Kante nicht schneidet. Das scheint jedoch teuer.

Gibt es eine Möglichkeit, die Kantenrichtungen gegen die Vektorrichtung oder einen ähnlichen Trick zu verwenden, um zu bestimmen, von welchen Punkten aus zu erweitern?

Answer 1

n.m. answered die Frage, wie ich gefragt und abgebildet, aber nach der Programmierung bemerkte ich bald, dass es einen gemeinsamen Fall gab, wo alle Ecken "außerhalb" Ecken wären (dies kann leicht auf Dreiecken gesehen werden und kann auch für andere Polygone auftreten).

Die Text Erklärung.

Die Lösung, die ich verwendete, war, die normalen Vektoren der Kanten zu betrachten, die in jeden Eckpunkt hinein und aus ihm heraus führen. Die Scheitelpunkte, die wir erweitern möchten, sind Scheitelpunkte, die mindestens eine Kantennormale mit einem minimalen Winkel von weniger als 90 Grad zu dem Delta-Vektor, um den wir uns erstrecken, haben.

normal = (currentVertex.y - nextVertex.y, nextVertex.x - currentVertex.x)

Beachten Sie, dass, da uns über die genauen Winkel nicht kümmern, wissen wir nicht normalisieren müssen:

Die nach außen gerichteten Rand Normale auf einem gegen den Uhrzeigersinn gewickelten Polygon kann durch gefunden werden (Machen Sie einen Einheitsvektor von) die Normale, die eine Quadratwurzel speichert.

Um es den Deltavektor zu vergleichen, verwenden wir das Produkt dot:

dot = edgeNormal.dot(deltaVector)

Wenn das Ergebnis größer als Null ist, der minimale Winkel spitz ist (weniger als 90). Wenn das Ergebnis genau Null ist, sind die Vektoren senkrecht. Wenn das Ergebnis kleiner als Null ist, ist der minimale Winkel stumpf. Es ist erwähnenswert, wenn die Vektoren senkrecht sind, da wir vermeiden können, dem erweiterten Polygon zusätzliche Ecken hinzuzufügen.

Wenn Sie sehen möchten, wie der Winkel mit dem Skalarprodukt funktioniert, wie ich es getan habe, sehen Sie sich einfach ein Diagramm von Arc Cosinus an (normalerweise erhalten Sie den Winkel über acos (Punkt)).

Jetzt können wir die Scheitelpunkte finden, die zwischen ihrer Randnormalen und dem Delta-Vektor einen spitzen und einen nicht-spitzen minimalen Winkel haben. Alles auf der "scharfen Seite" dieser Ecken hat den Delta-Vektor hinzugefügt, und alles auf der "stumpfen Seite" bleibt gleich. Die beiden Boarder-Scheitelpunkte selbst sind doppelt vorhanden, wobei einer verlängert und einer gleich bleibt, , es sei denn, ist die "stumpfe Seite" genau senkrecht zum Delta-Vektor (in diesem Fall brauchen wir nur den Scheitelpunkt zu verlängern, da wir sonst zwei hätten Scheitelpunkte auf derselben Linie).

Hier ist der C++ - Code für diese Lösung.

Es mag ein wenig lang aussehen, aber es ist eigentlich ziemlich einfach und hat viele Kommentare, so dass es hoffentlich nicht schwer sein sollte, zu folgen.

Es ist ein Teil meiner Polygon-Klasse, die einen std :: Vektor von gegen den Uhrzeigersinn gewundenen Vertices hat. units :: Coordinate sind floats und units :: Coordinate2D ist eine Vektorklasse, die meiner Meinung nach selbsterklärend sein sollte.

// Compute the normal of an edge of a polygon with counterclockwise winding, without normalizing it to a unit vector. 
inline units::Coordinate2D _get_non_normalized_normal(units::Coordinate2D first, units::Coordinate2D second) { 
    return units::Coordinate2D(first.y - second.y, second.x - first.x); 
} 
enum AngleResult { 
    ACUTE, 
    PERPENDICULAR, 
    OBTUSE 
}; 
// Avoid accumulative floating point errors. 
// Choosing a good epsilon is extra important, since we don't normalize our vectors (so it is scale dependent). 
const units::Coordinate eps = 0.001; 
// Check what kind of angle the minimum angle between two vectors is. 
inline AngleResult _check_min_angle(units::Coordinate2D vec1, units::Coordinate2D vec2) { 
    const units::Coordinate dot = vec1.dot(vec2); 
    if (std::abs(dot) <= eps) 
     return PERPENDICULAR; 
    if ((dot + eps) > 0) 
     return ACUTE; 
    return OBTUSE; 
} 
Polygon Polygon::extend(units::Coordinate2D delta) const { 
    if (delta.isZero()) { // Isn't being moved. Just return the current polygon. 
     return Polygon(*this); 
    } 
    const std::size_t numVerts = vertices_.size(); 
    if (numVerts < 3) { 
     std::cerr << "Error: Cannot extend polygon (polygon invalid; must have at least three vertices).\n"; 
     return Polygon(); 
    } 
    // We are interested in extending from vertices that have at least one edge normal with a minimum angle acute to the delta. 
    // With a convex polygon, there will form a single contiguous range of such vertices. 
    // The first and last vertex in that range may need to be duplicated, and then the vertices within the range 
    // are projected along the delta to form the new polygon. 
    // The first and last vertices are defined by the vertices that have only one acute edge normal. 

    // Whether the minimum angle of the normal of the edge made from the last and first vertices is acute with delta. 
    const AngleResult firstEdge = _check_min_angle(_get_non_normalized_normal(vertices_[numVerts-1], vertices_[0]), delta); 
    const bool isFirstEdgeAcute = firstEdge == ACUTE; 

    AngleResult prevEdge = firstEdge; 
    AngleResult currEdge; 
    bool found = false; 
    std::size_t vertexInRegion; 
    for (std::size_t i = 0; i < numVerts - 1; ++i) { 
     currEdge = _check_min_angle(_get_non_normalized_normal(vertices_[i], vertices_[i+1]), delta); 
     if (isFirstEdgeAcute != (currEdge == ACUTE)) { 
      // Either crossed from inside to outside the region, or vice versa. 
      // (One side of the vertex has an edge normal that is acute, the other side obtuse.) 
      found = true; 
      vertexInRegion = i; 
      break; 
     } 
     prevEdge = currEdge; 
    } 
    if (!found) { 
     // A valid polygon has two points that define where the region starts and ends. 
     // If we didn't find one in the loop, the polygon is invalid. 
     std::cerr << "Error: Polygon can not be extended (invalid polygon).\n"; 
     return Polygon(); 
    } 
    found = false; 
    std::size_t first, last; 
    // If an edge being extended is perpendicular to the delta, there is no need to duplicate that vertex. 
    bool shouldDuplicateFirst, shouldDuplicateLast; 
    // We found either the first or last vertex for the region. 
    if (isFirstEdgeAcute) { 
     // It is the last vertex in the region. 
     last = vertexInRegion; 
     shouldDuplicateLast = currEdge != PERPENDICULAR; // currEdge is either perpendicular or obtuse. 
     // Loop backwards from the end to find the first vertex. 
     for (std::size_t i = numVerts - 1; i > 0; --i) { 
      currEdge = _check_min_angle(_get_non_normalized_normal(vertices_[i-1], vertices_[i]), delta); 
      if (currEdge != ACUTE) { 
       first = i; 
       shouldDuplicateFirst = currEdge != PERPENDICULAR; 
       found = true; 
       break; 
      } 
     } 
     if (!found) { 
      std::cerr << "Error: Polygon can not be extended (invalid polygon).\n"; 
      return Polygon(); 
     } 
    } else { 
     // It is the first vertex in the region. 
     first = vertexInRegion; 
     shouldDuplicateFirst = prevEdge != PERPENDICULAR; // prevEdge is either perpendicular or obtuse. 
     // Loop forwards from the first vertex to find where it ends. 
     for (std::size_t i = vertexInRegion + 1; i < numVerts - 1; ++i) { 
      currEdge = _check_min_angle(_get_non_normalized_normal(vertices_[i], vertices_[i+1]), delta); 
      if (currEdge != ACUTE) { 
       last = i; 
       shouldDuplicateLast = currEdge != PERPENDICULAR; 
       found = true; 
       break; 
      } 
     } 
     if (!found) { 
      // The edge normal between the last and first vertex is the only non-acute edge normal. 
      last = numVerts - 1; 
      shouldDuplicateLast = firstEdge != PERPENDICULAR; 
     } 
    } 

    // Create the new polygon. 
    std::vector<units::Coordinate2D> newVertices; 
    newVertices.reserve(numVerts + (shouldDuplicateFirst ? 1 : 0) + (shouldDuplicateLast ? 1 : 0)); 
    for (std::size_t i = 0; i < numVerts; ++i) { 
     // Extend vertices in the region first-to-last inclusive. Duplicate first/last vertices if required. 
     if (i == first && shouldDuplicateFirst) { 
      newVertices.push_back(vertices_[i]); 
      newVertices.push_back(vertices_[i] + delta); 
     } else if (i == last && shouldDuplicateLast) { 
      newVertices.push_back(vertices_[i] + delta); 
      newVertices.push_back(vertices_[i]); 
     } else { 
      newVertices.push_back(isFirstEdgeAcute ? // Determine which range to use. 
       ((i <= last || i >= first) ? vertices_[i] + delta : vertices_[i]) : // Range overlaps start/end of the array. 
       ((i <= last && i >= first) ? vertices_[i] + delta : vertices_[i])); // Range is somewhere in the middle of the array. 
     } 
    } 
    return Polygon(newVertices); 
} 

bisher getestet ich diesen Code mit Dreiecken, Rechtecke, Kreise angenähert, und beliebigen konvexen Polygone hergestellt, indem die angenäherte Kreise sequentiell durch viele verschiedene Deltavektoren erstrecken.

Bitte beachten Sie, dass diese Lösung nur für konvexe Polygone gültig ist.

Answer 2

Ja, Sie können. Sie möchten entlang x, y projizieren. Also ist die Normale y, -x. Jetzt rotiere damit (atan2, oder du kannst es dir direkt, wenn du Rotationsmatrizen verstehst). Die zu projizierenden Punkte und jetzt das Minimum und Maximum x, Sie können die Projektion auch beschleunigen, indem Sie sie immer entlang einer Achse ausführen und dann zurück drehen.

Answer 3

Suchen Sie nach Punkten, an denen die Richtung des Vektors zwischen den Richtungen der Kanten liegt.

Mit anderen Worten, nehmen drei Vektoren:

• der Kante aus dem Scheitelpunkt
• des Translationsvektors
• gegenüber der Kante bis zum Scheitel führenden führenden

Wenn sie in dieser Reihenfolge sind, wenn CCW gehen, dh wenn th Der zweite Vektor ist zwischen dem ersten und dem dritten, das ist ein "innerer" Punkt.

Um zu bestimmen, ob ein Vektor zwischen zwei anderen Vektoren liegt, verwende ein Kreuzprodukt wie z. here.