Die Triangulation von Geometrien war früher ein "Ding".
Das kann man machen, wenn man die 3D Analyst-Erweiterung hat, aber wenn nicht und man die Prinzipien verstehen will und mit NumPy und Python arbeiten kann... hier geht's los.
1 Erstelle ein Array aus der Geometrie (FeatureClassToNumPyArray ist ein Anfang. Ich habe schon Code veröffentlicht, wie man das macht
2 trianguliere es (ich benutze scipy)
3 bestimme den Schwerpunkt jedes Dreiecks. (auch dafür habe ich Code veröffentlicht.)
4 prüfe, ob die Schwerpunkte innerhalb der ursprünglichen Form liegen.
Um das zu verkomplizieren: Polygone sind entweder konvex oder konkav, mit oder ohne Löcher und können aus mehr als einem Teil bestehen. Manchmal muss man also die Geometrie auf ihre einfachste Form reduzieren und durchlaufen. Konvexe Formen sind langweilig, daher ignoriere ich sie.
Hier sind 3 Formen, C, D, A. C ist eine konkave Form ohne Löcher. D ist konvex, hat aber ein Loch. A ist konkav und hat ein Loch.
Ihre triangulierten Versionen.
Und die eingeschränkte Triangulation. Das heißt, die Triangulation mit den Dreiecken, die nicht im ursprünglichen äußeren Rand oder in einem Loch liegen.
Sieht so aus, als wäre alles in Ordnung.
Um die Triangulation durchzuführen, kannst du verwenden
from scipy.spatial import Delaunay
def triangulate_pnts(pnts):
"""Trianguliere die Punkte und gib die Dreiecke zurück.
Parameter
----------
pnts : array
Punkte für eine Form oder eine Gruppe von Punkten im Array-Format.
Entweder geo.shapes oder np.ndarray.
out : array
Ein Array von Dreieckspunkten.
.. Hinweis::
Die Simplexe sind gegen den Uhrzeigersinn geordnet, dies wird in dieser
Implementierung umgekehrt.
"""
pnts = np.unique(pnts, axis=0) # nur eindeutige Punkte erhalten
avg = np.mean(pnts, axis=0)
p = pnts - avg
tri = Delaunay(p)
simps = tri.simplices
# -- Indexhalter, fülle mit Indizes, wiederhole den ersten und rotiere gegen Uhrzeigersinn
# übersetze die Punkte zurück
z = np.zeros((len(simps), 4), dtype='int32')
z[:, :3] = simps
z[:, 3] = simps[:, 0]
tmp_ = p[z] + avg
new_pnts= []
for i in tmp_: # sortiere im Uhrzeigersinn neu
if _bit_area_(i) < 0.0: # -- 2025_10_27
i = i[::-1]
new_pnts.append(i)
return new_pnts
def _bit_area_(a):
"""Mini e_area, verwendet von `areas` und `centroids`.
Negative Flächen sind Löcher. Dies ist absichtlich umgekehrt zur
`shoelace`-Formel.
"""
a = _base_(a)
x0, y1 = (a.T)[:, 1:] # Kreuzprodukt wie folgt aufgebaut
x1, y0 = (a.T)[:, :-1]
e0 = np.einsum('...i,...i->...i', x0, y0) # 2024-03-28 modifiziert
e1 = np.einsum('...i,...i->...i', x1, y1)
return np.sum((e0 - e1) * 0.5)
def _area_centroid_(a):
r"""Berechne Fläche und Schwerpunkt für ein Einzelteilpolygon `a`.
Wird auch verwendet zur Berechnung von Fläche und Schwerpunkt für Teile eines Geo-Arrays.
Hinweise
-----
Für Mehrteilige Formen einfach diese Syntax verwenden:
>>> # Rechteck mit Loch
>>> a0 = np.array([[[0., 0.], [0., 10.], [10., 10.], [10., 0.], [0., 0.]],
[[2., 2.], [8., 2.], [8., 8.], [2., 8.], [2., 2.]]])
>>> [_area_centroid_(i) for i in a0]
>>> [(100.0, array([ 5.00, 5.00])), (-36.0, array([ 5.00, 5.00]))]
"""
a = _base_(a)
x0, y1 = (a.T)[:, 1:]
x1, y0 = (a.T)[:, :-1]
e0 = np.einsum('...i,...i->...i', x0, y0)
e1 = np.einsum('...i,...i->...i', x1, y1)
t = e1 - e0
area = np.sum((e0 - e1) * 0.5)
x_c = np.sum((x1 + x0) * t, axis=0) / (area * 6.0)
y_c = np.sum((y1 + y0) * t, axis=0) / (area * 6.0)
return area, np.asarray([-x_c, -y_c])
Hier ist C
C
array([[ 0.00, 0.00],
[ 0.00, 10.00],
[ 10.00, 10.00],
[ 10.00, 8.00],
[ 2.00, 8.00],
[ 2.00, 2.00],
[ 10.00, 2.00],
[ 10.00, 0.00],
[ 0.00, 0.00]])
Die Schwerpunkte und Flächen sowie Triangulationen können mit dem Obigen bestimmt werden.
Zu testen welche Dreiecke Teil der ursprünglichen Geometrie sind erfordert eine Punkt-in-Polygon-Suche. Das habe ich schon in meiner früheren Inkarnation gemacht.
'Point in Polygon ... Geometry Mysteries' - Esri Community
'Winding number'-Ansatz wird verwendet.
'Wenn du also eine eingeschränkte Delaunay-Triangulation deiner Geometrieobjekte brauchst... probier es aus.
'Hinweis:'
'Wenn du mehr Python-, NumPy- und ArcPy-Sachen sehen willst, schau auf meiner GitHub-Seite vorbei.'
'Dan Patterson auf github'
