Bestimmen Sie, was Oktanten ein Liniensegment durchläuft

Question

Es ist mehr als 20 Jahre her, dass ich irgendeinen Mathe-Kurs belegt habe, also bin ich super eingerostet. Ich verwende den folgenden Code, um zu bestimmen, welche Oktanten ein Punkt, an relativ zum versehenen Zentrum:

public static int GetOctant(Vector2 center, Vector2 target) 
{ 
    var adjusted = target - center; 
    int oct = 0; 

    if (adjusted.Y < 0) 
    { 
     adjusted *= -1; // rotate 180 
     oct += 4; 
    } 
    if (adjusted.X < 0) 
    { 
     adjusted = new Vector2(adjusted.Y, -adjusted.X); // rotate cw 90 
     oct += 2; 
    } 
    if (adjusted.X < adjusted.Y) 
     oct++; 

    return oct; 
} 

ich dies tue für beiden Seiten meiner Linie, die mir die Start- und End-Oktanten gibt. Wenn sie mehr als 1 Oktant auseinander liegen, dann muss ich auch wissen, welche anderen Oktanten die Linie durchläuft. Aber ich kann nicht herausfinden, wie das geht.

ich für ein Verfahren wie dieses bin der Hoffnung:

private static int[] InOctants(Vector2 relativeCenter, Vector2 startPoint, Vector2 endPoint) 

private static bool IsInOctant(int oct, Vector2 center, Vector2 startPoint, Vector2 endPoint) 

Mein Code (was sehr Nicht-mathmatical ist) sieht wie folgt aus (a Segment nur 2 Vectors2):

private static List<Segment>[] PlaceInOctants(Vector2 center, IEnumerable<Segment> segments) 
{ 
    // We are creating lists of segments, 1 for each octant. 
    // Each list will contain any segment that touches that octant 
    var octants = new List<Segment>[8]; 
    for (int i = 0; i < octants.Length; i++) 
     octants[i] = new List<Segment>(); 

    foreach (Segment s in segments) 
    { 
     // Get the octant for the start/end points of the segments 
     var octantA = GetOctant(center, s.PointA); 
     var octantB = GetOctant(center, s.PointB); 
     if (octantA > octantB) 
     { 
      var tempOct = octantA; 
      octantA = octantB; 
      octantB = tempOct; 
     } 

     // Add the first segment to the first octants list 
     if (!octants[octantA].Contains(s)) 
      octants[octantA].Add(s); 

     // If octA & octB are different 
     if (octantA != octantB) 
     { 
      // We add the segment to the other list 
      if (!octants[octantB].Contains(s)) 
       octants[octantB].Add(s); 

      var diff = octantA - octantB; 
      if (diff < 0) 
       diff += 8; 
      if (diff > 4) 
       diff = 8 - diff; 
      // If A & B are 4 spaces apart (very rare) it's difficult to get 
      // the octants they pass through so we just add the segment 
      // to all the octants (it's going to pass through 5 out of 8 anyway) 
      // !!!! I'd like to do this right though !!!! 
      if (diff == 4) 
       for (int i = 0; i < octants.Length; i++) 
       { 
        if (octantA != i && octantB != i && !octants[i].Contains(s)) 
         octants[i].Add(s); 
       } 
      else 
      { 
       if (diff >= 2) 
       { 
        var oct = Math.Abs(diff) < 4 
         ? octantA < 7 ? octantA + 1 : 0 
         : octantA > 0 ? octantA - 1 : 7; 

        octants[oct].Add(s); 
       } 
       if (diff == 3) 
       { 
         var oct = Math.Abs(diff) > 4 
          ? octantB < 7 ? octantB + 1 : 0 
          : octantB > 0 ? octantB - 1 : 7; 
         octants[oct].Add(s); 
       } 
      } 
     } 
    } 
    return octants; 
} 

Ich benutze C# im Moment, kann aber von fast allem konvertieren.

Jemand hat gewählt, um das zu schließen, weil es nicht klar war, was ich fragte ... Um es klar zu machen. Ich benutze einen Hack, um zu bestimmen, welche Oktanten ein Liniensegment durchläuft, und in einigen Fällen ignoriere ich es einfach und füge das Segment all meinen Listen hinzu. Ich möchte diesen Code straffen und es richtig machen (mit Geometrie) wenn möglich. Ich möchte auch vermeiden, atan2 zu verwenden, weil es langsam ist.

Answer 1

Die Oktanten sind durch die Linien x = 0, y = 0, x = y, x = -y begrenzt. Sie können die Schnittpunkte mit einer gegebenen Linie wie a.x + b.y + c = 0 finden, indem Sie die entsprechenden Systeme lösen.

Zum Beispiel

a.x + b.y + c = 0 
x = y 

gibt x = y = - c/(a + b).

Im Allgemeinen gibt es vier Schnittpunkte, die fünf Oktanten begrenzen, die gekreuzt sind. Sie können erkennen, zu welchem ​​Oktanten die Kreuzungen gehören, indem Sie die Zeichen x, y, x + y, x - y betrachten.

Die vollständige Diskussion erfordert einige Mühe, aber ich bin sicher, dass Sie es schaffen werden.