l*******G
发帖数: 1191 | 1 Here is a quick question on triangular meshes.
Lets say I have a 2D triangular mesh like this
or
How do I undo the triangulation and identify all the polygons that make up
the boundary (including the holes?)
Note that holes may "touch" other holes (sharing a vertex, but not edge)
or the outer boundary.
There could also be rings ( holes in another hole) | x*****w
发帖数: 8 | 2 line()=0
foreach Mesh
for i=1,3
line(node1,node2)++
endfor
endfor
if(line<2) line is boundary
connect all line seg | l*******G
发帖数: 1191 | 3 what's node1 node2 and what does i have to do with line()?
When collecting, how to prove the collected segments are in clockwise order
of the polygon points? | l*******G
发帖数: 1191 | 4 I see line() is NNxNN matrix, NN is number of nodes, Wow, that is huge if
NN>1million. But thanks, I think possible to walk through all edges
without using such a large 2D array. Still tough to ensure order of edges. | x*****w
发帖数: 8 | 5 the max number of nodes connect is small, less than 20. Try use dynamic
array like list. one line only check the smaller node, otherwise you
duplicate each line.
clockwise is easy just search online. | x*****w
发帖数: 8 | 6 What line (i,j) store is the node connected to node i.
line(1,1) is the first node connected to node 1. line(1,2) is
second node connected node 1. line(2,1) is first node for node 2.
Say you has a new line, search the node connect to the small node. if found,
remove it, since it is the second time, other wise add it. If you are using
list, line(i).size() is the number connect to node i. If not, you need
another array to store the number. | l*******n
发帖数: 344 | 7 second Majia:
Final result: the nodes belong to boundary have one and only one connect to
it. so you start from any boundary node say s1, n1=line(s1,1) will be next
node, go n2=line(n1,1),go line(n2,1)...until come back to s1.
This is a very interesting problem. Actually, it is used by me as a
interviews question. Nobody could give a good answer. If you understand
boundary means one side have something, another side is empty, solution is
obvious. | l*******G
发帖数: 1191 | 8 Thanks, sounds cool, walk through all edges, any edge that ever bounds two
or more element is an interior edge, then remove that edge. Rest of edges
make up the boundary . Start from any one of the remaining edge and walk
along to original point to find one polygon. Continue if still have edges
not identified. There is a problem if two polygons kiss each other by
sharing a node. The way to walk back to original point is not unique. In
that case, one finds the shared point will be walked twice or there will be
incomplete polygons. Find the shared point first and start from the shared
point. There will be more problems if two polygons share two or more nodes
but not any edge! Such as the hand drawn pentagon star shape.
not sure how to do it in 3d, i e find the faces that make up the boundary of
a polyhedral 3d grid with holes in it. | x*****w
发帖数: 8 | 9 My situation is finding outline of a model ,no holes. For your problem, I
only can give you some advice:
1. find shared point: a point has more than 1 point connect it. May need a
flag array, size=number of boundary nodes.
2. start from any share point,when a line hits another share point, stop.
3. Your have some line segments after searching. Try using some methods to
find best combination, such as two segments share same points. I don't
believe it is possible that all polygons connect more than 2 polygons.
3D is same thing, instead of line, you use face. a face shared by two
elements, it is interior edge. I need make it clear, a line or face cannot
shared by more than two elements, only two situations: 1 or 2. | l*******G
发帖数: 1191 | 10 Here is a quick question on triangular meshes.
Lets say I have a 2D triangular mesh like this
or
How do I undo the triangulation and identify all the polygons that make up
the boundary (including the holes?)
Note that holes may "touch" other holes (sharing a vertex, but not edge)
or the outer boundary.
There could also be rings ( holes in another hole) | | | x*****w
发帖数: 8 | 11 line()=0
foreach Mesh
for i=1,3
line(node1,node2)++
endfor
endfor
if(line<2) line is boundary
connect all line seg | l*******G
发帖数: 1191 | 12 what's node1 node2 and what does i have to do with line()?
When collecting, how to prove the collected segments are in clockwise order
of the polygon points? | l*******G
发帖数: 1191 | 13 I see line() is NNxNN matrix, NN is number of nodes, Wow, that is huge if
NN>1million. But thanks, I think possible to walk through all edges
without using such a large 2D array. Still tough to ensure order of edges. | x*****w
发帖数: 8 | 14 the max number of nodes connect is small, less than 20. Try use dynamic
array like list. one line only check the smaller node, otherwise you
duplicate each line.
clockwise is easy just search online. | x*****w
发帖数: 8 | 15 What line (i,j) store is the node connected to node i.
line(1,1) is the first node connected to node 1. line(1,2) is
second node connected node 1. line(2,1) is first node for node 2.
Say you has a new line, search the node connect to the small node. if found,
remove it, since it is the second time, other wise add it. If you are using
list, line(i).size() is the number connect to node i. If not, you need
another array to store the number. | l*******n
发帖数: 344 | 16 second Majia:
Final result: the nodes belong to boundary have one and only one connect to
it. so you start from any boundary node say s1, n1=line(s1,1) will be next
node, go n2=line(n1,1),go line(n2,1)...until come back to s1.
This is a very interesting problem. Actually, it is used by me as a
interviews question. Nobody could give a good answer. If you understand
boundary means one side have something, another side is empty, solution is
obvious. | l*******G
发帖数: 1191 | 17 Thanks, sounds cool, walk through all edges, any edge that ever bounds two
or more element is an interior edge, then remove that edge. Rest of edges
make up the boundary . Start from any one of the remaining edge and walk
along to original point to find one polygon. Continue if still have edges
not identified. There is a problem if two polygons kiss each other by
sharing a node. The way to walk back to original point is not unique. In
that case, one finds the shared point will be walked twice or there will be
incomplete polygons. Find the shared point first and start from the shared
point. There will be more problems if two polygons share two or more nodes
but not any edge! Such as the hand drawn pentagon star shape.
not sure how to do it in 3d, i e find the faces that make up the boundary of
a polyhedral 3d grid with holes in it. | x*****w
发帖数: 8 | 18 My situation is finding outline of a model ,no holes. For your problem, I
only can give you some advice:
1. find shared point: a point has more than 1 point connect it. May need a
flag array, size=number of boundary nodes.
2. start from any share point,when a line hits another share point, stop.
3. Your have some line segments after searching. Try using some methods to
find best combination, such as two segments share same points. I don't
believe it is possible that all polygons connect more than 2 polygons.
3D is same thing, instead of line, you use face. a face shared by two
elements, it is interior edge. I need make it clear, a line or face cannot
shared by more than two elements, only two situations: 1 or 2. | a**a
发帖数: 63 | 19 This is an interesting problem, and very practical when working with meshes.
I suggest that you construct a matrix of internal edges or faces when
dealing higher dimensions. Then use
Unique with 'rows' option to find the unique ones.
If program properly you can get the boundar edges/faces with less than 5/6
lines of code.
Now really interesting is you cast the matrix into a hash function and agan
use "unique", you can gain quite some speed with large meshes. |
|
