Erstellen Sie 2d Dreiecke von 2d Punkten

8

Ich muss 2d Dreiecke aus einer Liste von 2d Punkten mit einer Bedingung machen: Länge jeder Kante kann nicht länger sein als eine vordefinierte Konstante.

In etwa so:

Kennst du einen Algorithmus, der das kann? Oder irgendeine Beratung?

Danke!

    
Mart 24.08.2010, 10:05
quelle

3 Antworten

7

Probieren Sie Delaunay-Triangulation aus und entfernen Sie alle Kanten, die zu lang sind.

Aus dem obigen Artikel sehen Sie einen Link zu CGALs 2D-Triangulationsseite .

    
Andre Holzner 24.08.2010, 10:18
quelle
2

Erzeuge zuerst alle möglichen Kanten (d.h. verbinde ein Paar von Ecken, die näher als die Konstante sind). Dann, wenn zwei von ihnen sich schneiden, entfernen Sie einen von ihnen. Wiederholen Sie diesen Schritt, bis keine Überschneidungen mehr vorhanden sind.

Diese Lösung ist ziemlich primitiv, es ist wahrscheinlich möglich, es schneller zu machen.

    
svick 24.08.2010 10:16
quelle
1

Ich mag svicks Antwort -

bei der Implementierung würde ich Folgendes tun

  1. Berechnen Sie die Linien zwischen jedem Punktpaar
  2. Sortiere die Liste nach Länge
  3. Entfernen Sie alle Zeilen, die länger als Ihr Schwellenwert sind
  4. Fahren Sie die Liste (am längsten bis zum kürzesten) fort, wenn sie eine andere Linie überquert, und entfernen Sie sie dann.
pondulus 24.10.2016 15:35
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Platzieren einer Plakettenblase auf der linken oberen Seite einer Schaltfläche