How to find opposing triangle pairs in triangulated objects?

Hi,

I want to find opposing triangle pairs in triangulated objects like shown in the example picture. The example data is attached with variables F and V for faces and vertices.

The interesting areas are marked in the pictures.

The requirements for a match of my choice would be:

1. distance of triangles lower than threshold, e.g. 3mm
2. triangles should be close to parallel. This could be set by a threshold of the "degree of parallelism". However a good measurement could be defined.
3. "correct" spatial orientation would be great, but is a bonus.

How I started:

• calculate center of gravity of all triagles
• calculate each of the distances (pdist2)
• remove triangle pairs with too high distances
• calculate normal vectors of remaining triangles
• check "parallelism" of triangles by dot product of normal vectors (dot product >0.9)
• remove adjacent triangle pairs that are "parallel" according to above definition

This is not very robust and leads to following issue:

• second neighbors are still found (neighbors of the adjacent triangles)

Is there a smart way to remove 2nd or 3rd neighbors or neighbors in general (neighborhood matrix/tree?!?)

Is there in general a smarter and more robust way to do that? It seems I ran into a direction where I have to exclude a lot of undesired cases....

Any help is welcome :-)

[darova]

Is the area of interest always vertical?

[Andre Lutz]

mostly yes, but not in general :-/

Answer 1

[darova]

Here is an idea or finding neigbour points;

    % some data
x0 = rand(40,1);
y0 = rand(40,1);
s1 = max(max(x0)-min(x0),max(y0)-min(y0));      % scale factor (max value)
    % scale the data
x1 = round((x0-min(x0))/s1*39)+5;      
y1 = round((y0-min(y0))/s1*39)+5;      
A = zeros(50);
ind = sub2ind(size(A),y1,x1);                   % indices
A(ind) = 1:40;                                  % write into matrix numbers of points
A1 = A*0;
A1(y1(5)-4:y1(5)+4,x1(5)-4:x1(5)+4) = 1;        % region around 5th point
A1 = A.*A1;                                     % select points in region
imshow([A A(:,1)+1 A1])

• Is there a smart way to remove 2nd or 3rd neighbors or neighbors in general (neighborhood matrix/tree?!?)

I don't understand. Why can't you just select max value of dot product?

[Andre Lutz]

2 neighboring triangles might be fully parallel. Therefore the dot product of there normal vectors might be 1 (or -1).

If I just check the dot product of the normal vectors, I'll also find the neighboring triangles. Therefore I want to find a way to exclude them. The direct neighbors are easy to exclude as the share nodes with my triangle. The second and third neigbors are not so easy to find.