C#でドロネーグラフから三角形分割を取得したい

Question

目的

Unityにおいてメッシュを切断するためドロネー三角形分割を実装しました。
ドロネーグラフ(ドロネー木)の実装のため以下の情報を参考にして非巡回有効グラフ(DAG)を実装しました。
An Extensive Examination of Data Structures Using C# 2.0 Part3
An Extensive Examination of Data Structures Using C# 2.0 Part5

ドロネーグラフの接続先が無いノードを重複無しで取り出すことができれば三角形分割を取り出すことができます。

#対応
そこでグラフの全要素を重複無しで取り出すために以下のような実装をしました。

• グラフに全ノードを格納するリストを作る。
• ノード追加(AddDirectedEdge)時に全ノードリストにあるノードと重複するか確認する。
• 重複していなければ全ノードリストに格納、そうでない場合は何もしない。

#問題
前述の方法ではノード追加時の重複チェックにO(n)の計算量を必要とします。(nはグラフのノード数)
ノード追加は頻繁に行うため、できれば定数時間に落としたいです。
また、O(n)程度でDAGの重複無し全要素を取得するアルゴリズムがあればお教えいただきたいです。

#実装
この実装は以下の実装から重みを省いて前述の対応を追加したものです。
An Extensive Examination of Data Structures Using C# 2.0 Part3
An Extensive Examination of Data Structures Using C# 2.0 Part5

using System.Collections;
using System.Collections.Generic;
public class Graph<T> : IEnumerable<T>
{
	private NodeList<T> nodeSet;
	public NodeList<T> allNode = new NodeList<T>();

	public Graph() : this(null) { }
	public Graph(NodeList<T> nodeSet)
	{
		if (nodeSet == null)
			this.nodeSet = new NodeList<T>();
		else
			this.nodeSet = nodeSet;
	}
	public void AddNode(GraphNode<T> node)
	{
		nodeSet.Add(node);
		allNode.Add(node);
	}
	public void AddNode(T value)
	{
		nodeSet.Add(new GraphNode<T>(value));
	}
	public void AddDirectedEdge(GraphNode<T> from, GraphNode<T> to)
	{
		from.Neighbors.Add(to);
		if (!allNode.Contains(to))
			allNode.Add(to);
	}
	public bool Contains(T value)
	{
		return nodeSet.FindByValue(value) != null;
	}
	public bool Remove(T value)
	{
		GraphNode<T> nodeToRemove = (GraphNode<T>)nodeSet.FindByValue(value);
		if (nodeToRemove == null)
			return false;

		nodeSet.Remove(nodeToRemove);

		foreach (GraphNode<T> gnode in nodeSet)
		{
			int index = gnode.Neighbors.IndexOf(nodeToRemove);
			if (index != -1)
				gnode.Neighbors.RemoveAt(index);
		}

		return true;
	}
	public IEnumerator<T> GetEnumerator()
	{
		return (IEnumerator<T>)allNode.GetEnumerator();
	}
	IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
	public NodeList<T> NodeList
	{
		get { return nodeSet; }
	}
}

public class GraphNode<T> : Node<T>
{
	public GraphNode() : base() { }
	public GraphNode(T value) : base(value) { }
	public GraphNode(T value, NodeList<T> neighbors) : base(value, neighbors) { }

	new public NodeList<T> Neighbors
	{
		get
		{
			if (base.Neighbors == null)
				base.Neighbors = new NodeList<T>();
			return base.Neighbors;
		}
	}
}

public class Node<T>
{
	private T data;
	private NodeList<T> neighbors = null;

	public Node() { }
	public Node(T data) : this(data, null) { }
	public Node(T data, NodeList<T> neighbors)
	{
		this.data = data;
		this.neighbors = neighbors;
	}
	public T Value
	{
		get
		{
			return data;
		}
		set
		{
			data = value;
		}
	}
	protected NodeList<T> Neighbors
	{
		get
		{
			return neighbors;
		}
		set
		{
			neighbors = value;
		}
	}
}

using System.Collections.ObjectModel;

public class NodeList<T> : Collection<Node<T>>
{
	public NodeList() : base() { }
	public NodeList(int initialSize)
	{
		for (int i = 0; i < initialSize; i++)
			base.Items.Add(default(Node<T>));
	}
	public Node<T> FindByValue(T value)
	{
		foreach (Node<T> node in Items)
			if (node.Value.Equals(value))
				return node;

		return null;
	}
}

Answer 1

認識が誤っていたらご指摘いただきたいのですが、ご質問者さんのおっしゃるドロネーグラフというのは、三角形にドロネー点を追加して分割したり、あるいはエッジフリップで三角形ペアを組み替えたりして新しい三角形が生成された際にそれらをグラフに追加していく、いわば三角形集合の操作履歴みたいなものを指すのでしょうか。
そしてドロネー分割が終わった後でグラフの末端に位置する三角形をかき集めると、それがドロネー分割結果になっている...といったプランでしょうか。

でしたら、別途用意しておくノードコレクションを「全ノードを格納するリスト」ではなく「現在生きているノードのコレクション」としてやるのはどうでしょう。
三角形が分割されたり組み替えられたタイミングでコレクションから古い三角形を削除し、新しい三角形を追加してやることにすれば、コレクション内には常にすべての末端ノードが収集された状態にできるだろうと思います。

ノードが重複することはないでしょうし、ノードの順序づけも不要でしょうから、コレクションとしてはおそらくHashSetがうってつけのような気がします。リファレンスによればAddもRemoveも計算コストはO(1)だそうですので、効率面でも有利じゃないかと思いますが、いかがでしょうかね?

Comments

[KEEL]

ありがとうございます
その認識で恐らく正しいかと...幾何学に詳しいわけではないので断言できず申し訳ないです。
非常に参考になりました。HashSetでの実装もできたのでベストアンサーとさせて頂きます。