Быстрая логическая операция между двумя группами сеток

Question

Это урезанный вопрос этот вопрос . В основном я просто спрашиваю о № 1 в вопросе.

Допустим, у меня есть две группы мешей . Определение класса меша следующее (синтаксис C #):

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

Есть ли какой-нибудь эффективный способ / реализация для нахождения результата логических операций (в моем случае я хотел бы найти пересечение полигонального стиля ) между двумя Mesh с?

Наивным способом было бы перебрать все Element внутри объекта Mesh, проверить другие Element в другом объекте Mesh и получить результаты.

Но я полагаю, что для этого есть более эффективный алгоритм - , использующий алгоритм плоской развертки .

Было бы лучше, если бы такой алгоритм уже был реализован в другом месте, либо в .Net, C ++ или в Matlab.

Answer 1

Только сеток недостаточно для логических операций над ним.

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 2

Булевские операции с сеткой трудно понять правильно, вы вправе попытаться использовать какой-то существующий код.

Одна из существующих библиотек C ++, которая может удовлетворить ваши потребности, - CGAL. ​​

Вы можетевзгляните на руководство .

Answer 3

В C ++ это может быть сделано намного эффективнее, если вы сохраняете отсортированную сетку (или сортируете их перед операциями) и используете std :: set_intersection. Чтобы сделать это, вам нужно добавить в Point какое-то отношение порядка. (Язык автоматически генерирует операторы упорядочения для других классов, предполагая, что в C ++ List является стандартным контейнером; возможно, вектор или deque).