Для эффективного построения структур данных с половинным ребром вам нужна структура ускорения для HE_vert (назовем это HE_vert_acc ... но вы можете просто сделать это непосредственно в HE_vert), которая сохраняет все HE_edges, указывающие на это HE_vert. В противном случае вы получите очень плохую сложность при попытке определить «пару HE_edge *» (которая является противоположно ориентированной смежной половиной), например, с помощью сравнения грубой силы.
Таким образом, создание структуры данных с половинным краем для одной грани может быть легко выполнено с помощью метода связывания, поскольку в любом случае пар (вероятно) нет. Но если вы добавите сложность структуры ускорения для эффективного выбора этих пар, то это станет немного сложнее, поскольку вам нужно обновить одинаковый HE_vert_acc на разных гранях, а затем обновить HE_edges, чтобы он содержал действительная пара. Это на самом деле несколько шагов. То, как вы склеите их все вместе с помощью связывания, гораздо сложнее, чем создание кругового двусвязного списка, и не совсем очевидно.
Из-за этого ... я бы не стал особо волноваться по поводу вопроса "как мне построить эту структуру данных в идиоматическом хаскеле".
Я думаю, что здесь разумно использовать более императивные подходы, пытаясь сохранить функционал API. Я бы, наверное, пошел за массивами и госададами.
Не говорю, что это невозможно, связывая узел, но я еще не видел такой реализации. На мой взгляд, это нелегкая проблема.
РЕДАКТИРОВАТЬ: поэтому я не мог отпустить и реализовал это, предполагая, что входной файл является сеткой .obj.
Мой подход основан на методе, описанном здесь https://wiki.haskell.org/Tying_the_Knot#Migrated_from_the_old_wiki,, но на примере Эндрю Бромейджа, где он объясняет, как связывать узлы для DFA, не зная узлов во время компиляции.
К сожалению, структура данных с половиной ребра еще более сложна, поскольку фактически состоит из 3 структур данных.
Итак, я начал с того, что на самом деле хочу:
data HeVert a = HeVert {
vcoord :: a -- the coordinates of the vertex
, emedge :: HeEdge a -- one of the half-edges emanating from the vertex
}
data HeFace a = HeFace {
bordedge :: HeEdge a -- one of the half-edges bordering the face
}
data HeEdge a = HeEdge {
startvert :: HeVert a -- start-vertex of the half-edge
, oppedge :: Maybe (HeEdge a) -- oppositely oriented adjacent half-edge
, edgeface :: HeFace a -- face the half-edge borders
, nextedge :: HeEdge a -- next half-edge around the face
}
Проблема заключается в том, что при эффективном построении мы сталкиваемся здесь со множеством проблем, поэтому для всех этих структур данных мы будем использовать «косвенную», которая в основном просто сохраняет простую информацию, полученную из файла сетки .obj.
Итак, я придумал это:
data IndirectHeEdge = IndirectHeEdge {
edgeindex :: Int -- edge index
, svindex :: Int -- index of start-vertice
, nvindex :: Int -- index of next-vertice
, indexf :: Int -- index of face
, offsetedge :: Int -- offset to get the next edge
}
data IndirectHeVert = IndirectHeVert {
emedgeindex :: Int -- emanating edge index (starts at 1)
, edgelist :: [Int] -- index of edge that points to this vertice
}
data IndirectHeFace =
IndirectHeFace (Int, [Int]) -- (faceIndex, [verticeindex])
Некоторые вещи, вероятно, не интуитивны и могут быть сделаны лучше, например, вещь "offsetedge".
Посмотрите, как я нигде не сохранил настоящие вершины. Это просто много индексных вещей, которые имитируют указатели Си.
Нам понадобится «список краев», чтобы потом эффективно находить противоположно ориентированные соседние полужизни.
Я не буду вдаваться в подробности того, как я заполняю эти косвенные структуры данных, потому что это действительно специфично для формата файла .obj. Я просто приведу пример того, как все происходит.
Предположим, у нас есть следующий файл сетки:
v 50.0 50.0
v 250.0 50.0
v 50.0 250.0
v 250.0 250.0
v 50.0 500.0
v 250.0 500.0
f 1 2 4 3
f 3 4 6 5
Косвенные лица теперь будут выглядеть так:
[IndirectHeFace (0,[1,2,4,3]),IndirectHeFace (1,[3,4,6,5])]
Косвенные ребра:
[IndirectHeEdge {edgeindex = 0, svindex = 1, nvindex = 2, indexf = 0, offsetedge = 1},
IndirectHeEdge {1, 2, 4, 0, 1},
IndirectHeEdge {2, 4, 3, 0, 1},
IndirectHeEdge {3, 3, 1, 0, -3},
IndirectHeEdge {0, 3, 4, 1, 1},
IndirectHeEdge {1, 4, 6, 1, 1},
IndirectHeEdge {2, 6, 5, 1, 1},
IndirectHeEdge {3, 5, 3, 1, -3}]
И косвенные вершины:
[(1,IndirectHeVert {emedgeindex = 0, edgelist = [3]}),
(2,IndirectHeVert {1, [0]}),
(3,IndirectHeVert {4, [7,2]}),
(4,IndirectHeVert {5, [4,1]}),
(5,IndirectHeVert {7, [6]}),
(6,IndirectHeVert {6, [5]})]
Теперь действительно интересная часть состоит в том, как мы можем превратить эти косвенные структуры данных в «прямую», которую мы определили в самом начале. Это немного сложно, но в основном это просто поиск по индексу и работает из-за лени.
Вот псевдокод (фактическая реализация использует не только списки и имеет дополнительные издержки для обеспечения безопасности функции):
indirectToDirect :: [a] -- parsed vertices, e.g. 2d points (Double, Double)
-> [IndirectHeEdge]
-> [IndirectHeFace]
-> [IndirectHeVert]
-> HeEdge a
indirectToDirect points edges faces vertices
= thisEdge (head edges)
where
thisEdge edge
= HeEdge (thisVert (vertices !! svindex edge) $ svindex edge)
(thisOppEdge (svindex edge) $ indexf edge)
(thisFace $ faces !! indexf edge)
(thisEdge $ edges !! (edgeindex edge + offsetedge edge))
thisFace face = HeFace $ thisEdge (edges !! (head . snd $ face))
thisVert vertice coordindex
= HeVert (points !! (coordindex - 1))
(thisEdge $ points !! (emedgeindex vertice - 1))
thisOppEdge startverticeindex faceindex
= thisEdge
<$>
(headMay
. filter ((/=) faceindex . indexf)
. fmap (edges !!)
. edgelist -- getter
$ vertices !! startverticeindex)
Имейте в виду, что мы не можем на самом деле сделать это возвращение «Возможно (HeEdge a)», потому что оно будет пытаться оценить все (что является бесконечным), чтобы узнать, какой конструктор использовать.
Мне пришлось добавить конструктор NoVert / NoEdge / NoFace для каждого из них, чтобы избежать «Возможно».
Другим недостатком является то, что это сильно зависит от входных данных и не является общей библиотечной вещью. Я также не совсем уверен, пересмотрит ли он (который все еще очень дешев) уже посещенные края.
Использование Data.IntMap.Lazy, похоже, повышает производительность (по крайней мере, для списка IndirectHeVert). Data.Vector на самом деле мало что для меня сделал здесь.
Нет необходимости использовать монаду состояний где-либо, если только вы не хотите использовать массивы или векторы.