s**p
发帖数: 207 | 1 我只有点，线，面，也就是mesh. 我想最快的知道这个mesh是不是连通的，有好办法没有 | s**p
发帖数: 207 | 2 而且这个mesh不一定是封闭的，
如果是封闭的，可能可以用euler poincare
如果不封闭呢？
多谢
没有
【在 s**p 的大作中提到】
: 我只有点，线，面，也就是mesh. 我想最快的知道这个mesh是不是连通的，有好办法没有
| N***l
发帖数: 52 | 3 从一个节点开始breadth first搜索
【在 s**p 的大作中提到】
: 而且这个mesh不一定是封闭的，
: 如果是封闭的，可能可以用euler poincare
: 如果不封闭呢？
: 多谢
:
: 没有
| n*e
发帖数: 50 | 4 图伦里面只有点和线吧？
这个是拓扑学问题？
没有
【在 s**p 的大作中提到】
: 我只有点，线，面，也就是mesh. 我想最快的知道这个mesh是不是连通的，有好办法没有
| s**p
发帖数: 207 | 5 不是拓扑学学问题
就是我有一个mesh,我想做一个sanity check,保证这个mesh是连通的。
这个breadth first search好像complexity 很高，我想最好就是O(N)或者O(1)的
complexity.
如果这个net是在一个平面上，我好像可以做出来，O(1), 但是很可能也错了
V+(F+1)-E=2, 如果成立，就是连通的，如果不，就不是联通。
其实就是一个变形的euler poincare。我加上一个虚拟的polygon把边界给连起来，把
这个2维平面变成一个genus=0的三维封闭体.
不过如果这个区域不是单联通的，似乎这个就不对了。
anyway,没学过图论拓扑的东西，我是做boundary element的
问题现在是一个三维的surface mesh. anyway, if it costs too much, it does not
worth it. i will let the code run until it crashs :( | N***l
发帖数: 52 | 6 其实breadth first search复杂度不高，才
O(|V|*max_deg)就是一个线性复杂度。
【在 s**p 的大作中提到】
: 不是拓扑学学问题
: 就是我有一个mesh,我想做一个sanity check,保证这个mesh是连通的。
: 这个breadth first search好像complexity 很高，我想最好就是O(N)或者O(1)的
: complexity.
: 如果这个net是在一个平面上，我好像可以做出来，O(1), 但是很可能也错了
: V+(F+1)-E=2, 如果成立，就是连通的，如果不，就不是联通。
: 其实就是一个变形的euler poincare。我加上一个虚拟的polygon把边界给连起来，把
: 这个2维平面变成一个genus=0的三维封闭体.
: 不过如果这个区域不是单联通的，似乎这个就不对了。
: anyway,没学过图论拓扑的东西，我是做boundary element的
|
|
