メッシュの2つのグループ間の高速ブール演算

Question

これは、this questionというトリミングされた質問です。基本的に私は質問の第1位について尋ねています。

（C＃構文）を次のようにメッシュクラスの定義がある、のは、私がmeshesの2つのグループを持っているとしましょう：

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; 
} 

は、ブール演算の結果として得を見つけるための任意の効率的な方法/実装があります（中私の場合ポリゴンスタイルの交差点）が2つのMeshの間にありますか？

素朴な方法は、Meshオブジェクト内のすべてのElement Sをループにすることが別のMesh目的で他のElementに対してチェックし、その結果を得ることができます。

しかし、これを行うためのより効率的なアルゴリズムがあると思います。utilizing plane sweeping algorithm。

このようなアルゴリズムが.Net、C++、またはmatlabのいずれかで既に実装されている場合は、もっと大きくなります。

Answer 1

C++では、メッシュを並べ替えたままにしておく（または操作の前に並べ替える）と、std :: set_intersectionを使用すると、はるかに効率的に行うことができます。これを行うには、何らかの並べ替えの関係をPointに追加する必要があります。 （この言語は、C++でListが標準コンテナであると仮定すると、他のクラスの順序演算子を自動的に生成します;おそらくベクトルまたはデキュール）。

Answer 2

ブール演算を行うだけのメッシュでは不十分です。その追加情報の後

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

、ブール演算は簡単です：

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; 
}; 

しかし、その構造の外にメッシュを得ることはかなり困難です。あなたはそれから何か役に立つものを得るつもりはありません。最善の解決策は、行進立方体のようなもので、あなたが得たメッシュはそれほど良く見えません。

Answer 3

メッシュブール演算が正しくなるのは難しく、既存のコードを使用しようとするのは正しいです。

あなたのニーズに合う既存のC++ライブラリは、CGALです。

manualをご覧ください。