Bereich Schnittpunkt in Python

Question

Ich habe einen Code, der eine Bedingung C als Eingabe verwendet, und berechnet die Lösung für mein Problem als eine 'zulässige Fläche' A auf dem (x, y) Raum. Dieser Bereich besteht aus mehreren "Röhren", die durch 2 Linien definiert sind, die niemals kreuzen können.

Das Endergebnis, das ich suche, muss k Bedingungen {C1, .., Ck} erfüllen, und ist daher ein Schnittpunkt S zwischen k Bereichen {A1, .., Ak}.

Hier ist ein Beispiel mit 2 Bedingungen (A1: grün, 3 Röhren. A2: lila, 1 Röhre); Die Lösung S ist rot.

Wie kann ich S finden, wenn ich mit 4 Bereichen von etwa 10 Rohre zu tun habe jeder? (Die letzte Handlung ist schrecklich!)

ich brauchen würde, um es zu zeichnen, und die mittleren Koordinate und die Varianz der Punkte in S (Varianz jeden Koordinate) zu finden. [Wenn es einen effizienten Weg gibt zu wissen, ob ein Punkt P zu S gehört oder nicht, verwende ich einfach eine Monte-Carlo-Methode].

Idealerweise würde ich auch gerne "verbotene Röhren" einbauen, die ich von S entfernen würde [es könnte etwas komplizierter sein, als S mit der Außenseite meines verbotenen Bereichs zu schneiden, da zwei Röhren aus der Derselbe Bereich kann sich kreuzen (auch wenn die Linien, die eine Röhre definieren, niemals kreuzen)].

---

Hinweis:

• Der Code speichert auch die Bogenlänge der Linien.

• Die Linien werden als Punktarrays gespeichert (ca. 1000 Punkte pro Linie). Die zwei Linien, die eine Röhre definieren, haben nicht unbedingt die gleiche Anzahl von Punkten, aber Python kann ALLE als eine Funktion ihrer Bogenlänge in 1 Sekunde interpolieren.

• Die Zeilen sind parametrische Funktionen (d. H., Wir können y = f (x) nicht schreiben, da die Zeilen vertikal sein dürfen).

• Die Handlung wurde mit Farbe bearbeitet, um das Ergebnis auf der rechten Seite zu bekommen ... Nicht sehr effizient!

---

Edit:

• Ich weiß nicht, wie ich plt.fill_between für einen Mehrfachschnitt verwenden kann (ich kann es für zwei Bedingungen hier tun, aber ich brauche den Code um es automatisch zu tun, wenn es zu viele Linien für das Augenurteil gibt).

• Für jetzt erzeuge ich nur die Zeilen. Ich habe nichts geschrieben, um die endgültige Lösung zu finden, da ich absolut nicht weiß, welche Struktur dafür am besten geeignet ist. [Eine frühere Version des Codes war jedoch in der Lage, die Schnittpunkte zwischen den Linien von 2 verschiedenen Rohren zu finden, und ich plante, sie als Polygone formschön zu übergeben, aber dies implizierte mehrere andere Probleme.]

• Ich glaube nicht, dass ich es mit sets tun kann: das Scannen des gesamten (x, y) -Bereichs mit der erforderlichen Genauigkeit entspricht etwa 6e8 Punkten ...[Die Linien haben nur 1e3 Punkte dank einer variablen Schrittgröße (passt sich an die Krümmung), aber das ganze Problem ist recht groß]

Answer 1

Problem Shapely gelöst!

Ich definierte jedes Rohr als Polygon, und ein Bereich A ist ein MultiPolygon Objekt als die Union seiner Rohre gebaut.

Die intersection Methode berechnet dann die Lösung, die ich gesucht habe (die Überlappung zwischen allen Bereichen).

Das Ganze ist fast augenblicklich. Ich wusste nicht, dass formschön mit großen Objekten so gut war [ca. 2000 Punkte pro Röhre, 10 Röhren pro Fläche, 4 Bereiche].

Vielen Dank für Ihre Hilfe! :)

Edit:

Ein Arbeitsbeispiel.

import matplotlib.pyplot as plt 
import shapely 
from shapely.geometry import Polygon 
from descartes import PolygonPatch 
import numpy as np 

def create_tube(a,height): 
    x_tube_up = np.linspace(-4,4,300) 
    y_tube_up = a*x_tube_up**2 + height 
    x_tube_down = np.flipud(x_tube_up)   #flip for correct definition of polygon 
    y_tube_down = np.flipud(y_tube_up - 2) 

    points_x = list(x_tube_up) + list(x_tube_down) 
    points_y = list(y_tube_up) + list(y_tube_down) 

    return Polygon([(points_x[i], points_y[i]) for i in range(600)]) 

def plot_coords(ax, ob): 
    x, y = ob.xy 
    ax.plot(x, y, '+', color='grey') 


area_1 = Polygon()   #First area, a MultiPolygon object 
for h in [-5, 0, 5]: 
    area_1 = area_1.union(create_tube(2, h)) 

area_2 = Polygon() 
for h in [8, 13, 18]: 
    area_2 = area_2.union(create_tube(-1, h)) 

solution = area_1.intersection(area_2)  #What I was looking for 

########## PLOT ########## 

fig = plt.figure() 
ax = fig.add_subplot(111) 

for tube in area_1: 
    plot_coords(ax, tube.exterior) 
    patch = PolygonPatch(tube, facecolor='g', edgecolor='g', alpha=0.25) 
    ax.add_patch(patch) 

for tube in area_2: 
    plot_coords(ax, tube.exterior) 
    patch = PolygonPatch(tube, facecolor='m', edgecolor='m', alpha=0.25) 
    ax.add_patch(patch) 

for sol in solution: 
    plot_coords(ax, sol.exterior) 
    patch = PolygonPatch(sol, facecolor='r', edgecolor='r') 
    ax.add_patch(patch) 

plt.show() 

Und die Handlung: