Schnelle boolesche Operation zwischen zwei Mesh-Gruppen

Question

Dies ist eine abgespeckte Frage von this question. Im Grunde frage ich nur nach der Nummer 1 in der Frage.

Lassen Sie uns sagen, ich habe zwei Gruppen von meshes, Die Definition der Mesh-Klasse ist wie folgt (C# Syntax):

public class Mesh 
{ 
public List<Element> elements; 
public List<Point> points; 
} 

public class Element 
{ 
    public List<int> PointIndex; 
} 

public class Point 
{ 
    public double X; 
    public double Y; 
} 

Gibt es eine effiziente Art und Weise/Umsetzung der resultierenden von Boolesche Operationen zu finden (in mein Fall würde ich gerne die polygonalen Schnittpunkt) zwischen zwei Mesh s finden?

Die naive Weise eine Schleife durch alle Element s innerhalb des Mesh Objekt sein würde, gilt das andere in einem anderen ElementMesh Objekt, und die Ergebnisse zu erhalten.

Aber ich glaube, es gibt effizientere Algorithmus, dies zu tun - utilizing plane sweeping algorithm.

Es wäre größer, wenn ein solcher Algorithmus bereits anderweitig implementiert wurde, entweder in .Net, C++ oder Matlab.

Answer 1

In C++ kann dies viel effizienter durchgeführt werden, wenn Sie das Mesh sortiert halten (oder vor den Operationen sortieren) und std :: set_intersection verwenden. Um dies zu tun, müssen Sie Point eine Art von Bestellbeziehung hinzufügen. (Die Sprache generiert automatisch die Sortieroperatoren für die anderen Klassen, vorausgesetzt, in C++ ist List ein Standardcontainer; wahrscheinlich Vektor oder Deque).

Answer 2

Nur Meshes reichen nicht aus, um boolesche Operationen auszuführen.

class B 
{ 
public: 
    virtual bool Inside(Point p) const=0; 
}; 

Nach diesen zusätzlichen Informationen, Boolesche Operationen sind trivial:

class Intersect : public B 
{ 
public: 
    Intersect(B &b1, B &b2) : b1(b1), b2(b2) { } 
    bool Inside(Point p) const { return b1.Inside(p) && b2.Inside(p); } 
private: 
    B &b1; 
    B &b2; 
}; 

Aber immer ein Netz aus dieser Struktur erheblich erschwert ist. Du wirst nichts Nützliches daraus bekommen. Die beste Lösung ist so etwas wie marschierende Würfel und die Maschen, von denen du kommst, werden nicht gut aussehen.

Answer 3

Boolesche Operationen im Mesh-Bereich sind schwer zu bekommen, Sie haben recht, wenn Sie versuchen, vorhandenen Code zu verwenden.

Eine vorhandene C++ - Bibliothek, die Ihren Anforderungen entsprechen könnte, ist CGAL.

Sie könnten einen Blick auf die manual werfen.