Есть нерегулярная сетка с линейными ячейками представляющими произвольные многогранники.
Дан массив граней ячеек, в котором номер элемента соответствует номеру грани.
Массив содержит для каждой грани: номера 1 и 2 ячейки которые пересекаются по данной грани (если грань на границе области — номер 1 ячейки равен 0), номера и координаты узлов грани в порядке обхода против часовой если смотреть с 1 ячейки на 2, номер некой двумерной граничной области которой принадлежит грань ( если грань находится на границе геометрической фигуры которая образуется по границам сетки ).
Нужно: оптимально по скорости выработать алгоритм нумерации ребер (неповторяющаяся нумерация) и определить для каждого ребра номера соседствующих по нему граней.
Подскажите оптимальный алгоритм.

Здравствуйте, MacId, Вы писали:

MI>Есть нерегулярная сетка с линейными ячейками представляющими произвольные многогранники.
MI>Дан массив граней ячеек, в котором номер элемента соответствует номеру грани.
MI>Массив содержит для каждой грани: номера 1 и 2 ячейки которые пересекаются по данной грани (если грань на границе области — номер 1 ячейки равен 0), номера и координаты узлов грани в порядке обхода против часовой если смотреть с 1 ячейки на 2, номер некой двумерной граничной области которой принадлежит грань ( если грань находится на границе геометрической фигуры которая образуется по границам сетки ).
MI>Нужно: оптимально по скорости выработать алгоритм нумерации ребер (неповторяющаяся нумерация) и определить для каждого ребра номера соседствующих по нему граней.
MI>Подскажите оптимальный алгоритм.
Массив получен из диаграммы вороного?

Здравствуйте, denisko, Вы писали:

D>Массив получен из диаграммы вороного?

Нет. Я про эту диаграмму первый раз слышу.

P.S. Других данных нет кроме описанных в корневом посте.

Здравствуйте, MacId, Вы писали:

MI>Дан массив граней ячеек, в котором номер элемента соответствует номеру грани.
MI>Массив содержит для каждой грани: номера 1 и 2 ячейки которые пересекаются по данной грани (если грань на границе области — номер 1 ячейки равен 0), номера и координаты узлов грани в порядке обхода против часовой если смотреть с 1 ячейки на 2, номер некой двумерной граничной области которой принадлежит грань ( если грань находится на границе геометрической фигуры которая образуется по границам сетки ).
MI>Нужно: оптимально по скорости выработать алгоритм нумерации ребер (неповторяющаяся нумерация) и определить для каждого ребра номера соседствующих по нему граней.

Пронумеруем грани в исходном порядке, как они даны в массиве. Или отсортируем по парам номеров ячеек.
Создадим массив пар (координаты вершины, грань); естественно, каждая грань войдёт в массив дважды.
Сгруппируем (произвольным способом отсортируем) по координатам. Так мы получим множества стыкующихся граней.
Пронумеруем эти множества (вершины). Заведём ещё один — индексный — массив вершин.
Припишем каждой грани два номера вершин.
Не будем выбрасывать эти массивы. Теперь поиск стыкующихся граней данной грани выполняется за единичное время!

Пока не все мне удалось понять. Давайте попробуем разобраться.
Предположу, что это предположительно так (параллельно задам несколько вопросов):

Кодт> Пронумеруем грани в исходном порядке, как они даны в массиве. Или отсортируем по парам номеров ячеек.
Я> Грани уже пронумерованы о чем я указывал ранее.

Кодт> Создадим массив пар (координаты вершины, РЕБРО); естественно, каждое РЕБРО войдёт в массив дважды.
Я> Ок, для этого нужно пробежаться по граням и запихать в этот массив все координаты для пар вершин.
Как я понимаю, номер элемента в массиве соответствует номеру ребра, а в паре 1 элемент — коорд. 1 вершины,
а 2 элемент — координаты 2 вершины.

Кодт> Сгруппируем (произвольным способом отсортируем) по координатам. Так мы получим множества стыкующихся РЕБЕР.
Я> Тут я не понял следующее. Наприме в массиве описаны 2 раза по 2 вершины: 1 элемент массива,вершина А — X=10,
Y=20,Z=10, вершина B — X=20,Y=30,Z=15; 2 элемент описывает те же вершины , но наоборот (заход к ребру был с
обратной стороны) вершина С — X=20,Y=30,Z=15,
вершина D — X=10,Y=20,Z=10. Что тогда даст сортировка? Ведь предложение сортировать в порядке сначала по X,внутри
по Y, и далее по Z, так я понимаю?

Кодт> Пронумеруем эти множества (вершины). Заведём ещё один — индексный — массив вершин.
Припишем каждому РЕБРУ два номера вершин.
Не будем выбрасывать эти массивы. Теперь поиск стыкующихся граней данного РЕБРА выполняется за единичное время!

Я> Хорошо, только неясно где сохранилась связь ребра с гранями. Ведь для каждого ребра мы получили только пары вершин и все. Бегать по всем граням и искать где есть такие вершины? А как без связи ребер и граней искать стыкующиеся грани?

P.S. К сожалению суть алгоритма до конца я не уловил. Возможно где-то , что-то я недопонял.

Сорри, отвечал, не залогинившись.

Здравствуйте, Аноним, Вы писали:

А>Пока не все мне удалось понять. Давайте попробуем разобраться.

Ай, извини, я жёстко протупил. Почему-то стал думать, что мы находимся на поверхности одного многогранника.

Но, вообще говоря, нам неинтересна нумерация ячеек.
Ребро идентифицируется парой вершин, правильно?

Для каждой грани берём последовательность вершин и получаем множество рёбер: (вершина1,вершина2,грань).
Поскольку рёбра ненаправленные, то, для определённости, вводим отношение "<" над вершинами (например, лексикографический порядок по компонентам x,y,z) и полагаем, что вершина1<вершина2.

Склеиваем множества рёбер от всех вершин в одно большое множество.
Каждое ребро входит туда несколько раз, с разными номерами вершин.

Далее, группируем это множество по эквивалентным рёбрам (то есть, таким, которые соединяют одну и ту же пару вершин).
Для этого вводим порядок над парой вершин (опять таки, проще всего — лексикографический) и сортируем множество.

Наконец, нумеруем каждую группу. И сопоставляем паре вершин множество граней.

---

Если воспользоваться ассоциативными контейнерами, то получится ещё проще.

На питоне

class Point :
  ''' точка '''
  x,y,z = 0,0,0 # координаты
  def __init__(self,x,y,z) : # конструктор
    self.x,self.y,self.z = x,y,z
  def __cmp__(self,other) : # компаратор
    return cmp( (self.x,self.y,self.z), (other.x,other.y,other.z) )

def Edge :
  ''' ребро '''
  points = (None,None) # вершины
  def __init__(self,p1,p2) :
    self.points = min(p1,p2),max(p1,p2)
  def __cmp__(self,other) :
    return cmp( (self.points), (other.points) )

class Facet :
  ''' грань '''
  n = 0 # идентификатор
  cells = (0,0) # 
  points = [] # точки многоугольника
  def edges(self) :
    ''' список рёбер '''
    return [Edge(points[i-1],points[i]) for i in range(length(points))] # points[-1] - последняя точка

def edgesToFacets(facets) :
  ''' для списка граней - возвращаем отображение : ребро - список его граней '''
  map = {} # Edge => [Facet,Facet,....]
  for facet in facets :
    for edge in facet.edges() :
      if not map[edge] :
        map[edge] = [facet] # новое ребро
      else :
        map[edge] += [facet] # добавляем новую грань
  return map

На С++

struct Point { int x,y,z; };
bool operator < (Point const& p1, Point const& p2) { return memcmp(&p1,&p2,sizeof(Point)); }

typedef std::pair<Point,Point> Edge;
// конструктор и компаратор определены

Edge makeEdge(Point p1, Point p2) // конструируем упорядоченное ребро
{
  if(p1<p2) return Edge(p1,p2);
  else      return Edge(p2,p1);
}

struct Facet
{
  int cell1, cell2;
  std::vector<Point> points;
};
typedef std::vector<Facet> Facets;
typedef int FacetIndex;

typedef std::map<Edge, std::set<FacetIndex> > EdgesToFacets;

void makeEdgesToFacets(const Facets& facets, EdgesToFacets& /*out*/ etf)
{
  etf.clear();

  for(FacetIndex fi=0; fi!=facets.size(); ++fi)
  {
    const Facet& facet = facets[fi];
    for(int pi=0; pi!=facet.points.size(); ++pi)
    {
      int pi1 = pi==0 ? facet.points.size()-1 : pi-1;
      etf[makeEdge(facet.points[pi1],facet.points[pi])].insert(fi);
    }
  }
}

Здравствуйте, Кодт, Вы писали:


Этот вариант весьма интересный. Попробую в понедельник применить "в ход" на работе. Большое спасибо в любом случае.

P.S.: Попутно, если можно еще 1 вопрос: например граней в сетке порядка 200 — 300 миллионов — как тогда обеспечить работу подобного алгоритма (за адекватное время для пользователя) на допустим слабой машине с оперативной памятью 512 — 1024 мегабайтов?

Здравствуйте, MacId, Вы писали:

MI>P.S.: Попутно, если можно еще 1 вопрос: например граней в сетке порядка 200 — 300 миллионов — как тогда обеспечить работу подобного алгоритма (за адекватное время для пользователя) на допустим слабой машине с оперативной памятью 512 — 1024 мегабайтов?

... 200-300 миллионов граней, ну а рёбер там ещё раза в три-четыре больше. То есть миллиард-полтора.
Да, такое количество данных попросту не влезет не то что в оперативную, но и в виртуальную память.

Значит, нужно использовать внешнюю сортировку. Может быть, какую-нибудь быструю базу данных (не реляционную, а ключ-значение, такую как беркли).

Либо, нарубить пространство на кубики — и отдельно обработать рёбра, входящие своей "меньшей" (для определённости) вершиной в один кубик, затем в следующий кубик, и т.д.
Чем больше кубики, тем больше нагрузка на память. Чем больше кубиков, тем больше количество забегов по исходному массиву. (Вот здесь можно прибегнуть к внешней сортировке, кстати говоря. Раскидать по файлам).

Да я тоже вижу только подобные варианты. Нарезка на "кубики" не уверен что прокатит, тк для данного алгоритма все же видно пока решение через общий массив. Спасибо еще раз за помощь.

Здравствуйте, MacId, Вы писали:

MI>Да я тоже вижу только подобные варианты. Нарезка на "кубики" не уверен что прокатит, тк для данного алгоритма все же видно пока решение через общий массив. Спасибо еще раз за помощь.

Но, если массив не влезает в память — как через него может быть решение?

Здравствуйте, Кодт, Вы писали:

К>Но, если массив не влезает в память — как через него может быть решение?

Я имел ввиду лишь то, что не вижу решения данной задачи пока с вариантом в памяти, но с нарезкой на "кубики".
А с остальным согласен.
Еще хотел заметить: в приведенном варианте решения алгоритма есть небольшой недостаток — нет связи номеров узлов (причем нужно против часовой стрелки если смотреть с 1 пересекающейся грани на 2) с ребрами. Но это я не пояснил сразу этот момент — так что вину беру на себя.

Добавлю, что узлы нужно было пронумеровать для всей указанной граничной области (как и ребра) представляющей собой некоторый набор граней. Т.е. в начальных данных (все что указано в корневом посте) — вся нумерация и связи (грани,номера узлов,ячейки) была глобальной для всей сетки геометрической фигуры.

Здравствуйте, Аноним, Вы писали:

К>>Но, если массив не влезает в память — как через него может быть решение?
А>Я имел ввиду лишь то, что не вижу решения данной задачи пока с вариантом в памяти, но с нарезкой на "кубики".
А>А с остальным согласен.

С нарезкой на кубики — мы можем неоднократно читать файл с диска, оставляя в памяти только то, что относится к одному кубику.
Сбрасываем результат кубика на диск, переходим к следующему кубику, повторяем...

А>Еще хотел заметить: в приведенном варианте решения алгоритма есть небольшой недостаток — нет связи номеров узлов (причем нужно против часовой стрелки если смотреть с 1 пересекающейся грани на 2) с ребрами. Но это я не пояснил сразу этот момент — так что вину беру на себя.

То есть, каждому ребру (вершина-начало,вершина-конец) соответствует множество пар {(номер грани, номер ребра на данной грани)}. Это принципиально не отличается от составления множества {(номер грани)}.

Здравствуйте, Кодт, Вы писали:



К>С нарезкой на кубики — мы можем неоднократно читать файл с диска, оставляя в памяти только то, что относится к одному кубику.
К>Сбрасываем результат кубика на диск, переходим к следующему кубику, повторяем...

С таким вариантом да, то полностью соглашусь.


К>То есть, каждому ребру (вершина-начало,вершина-конец) соответствует множество пар {(номер грани, номер ребра на данной грани)}. Это принципиально не отличается от составления множества {(номер грани)}.

Впринципе да.

Здравствуйте, Аноним, Вы писали:

К>>С нарезкой на кубики — мы можем неоднократно читать файл с диска, оставляя в памяти только то, что относится к одному кубику.
К>>Сбрасываем результат кубика на диск, переходим к следующему кубику, повторяем...

А>С таким вариантом да, то полностью соглашусь.

А можем за один проход прочитать файл, раскидать на файлы кубиков (неотсортированные); затем каждый файл кубика отсортировать; и склеить результат.