Thread Subject: find in which triangle algorithm

Hello,

I have a matrix of points, and a simple patch of triangles. I have the indices of those triangles and the coordenates of the vertices. I need to find in which of the triangle, is each point.

p is the matrix with the points
tri are the indices of the triangles in the form [12 13 14, 21 2 3, etc]
face_triangulos are the coordinates of the points which formed the triangles

I am assinging for each point the form [x y z T], where T is the triangle in which the point is contained. z is always zero ..

p = [p, zeros(size(p,1),1)];

for I=1:size(tri,1)
    for J=1:size(p,1)

        if(p(J,4) ~= 0)
            break;
        end

        A = face_triangulos(tri(I,:),1)';
        B = face_triangulos(tri(I,:),2)';
        C = face_triangulos(tri(I,:),3)';
        
        if(isInsideTriangle([p(J,1),p(J,2)], A, B, C) == 1)
            p(J,4) = I; % se p estiver contido em T, p fica com indice do triangulo
        
        else
           break;
        end
    end
end

But this keeps returning zero :( i don't know why.
Any help,

Thanks in advance

regards

I've never heard of isInsideTriangle and it's not in my help.
Presumably it's something you wrote. So I don't know why it never
returns 1. Why don't you try the built-in MATLAB function inpolygon()
instead?

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <03d5db68-2214-400a-b5ad-e4c248095902@l13g2000yqb.googlegroups.com>...
> I've never heard of isInsideTriangle and it's not in my help.
> Presumably it's something you wrote. So I don't know why it never
> returns 1. Why don't you try the built-in MATLAB function inpolygon()
> instead?

I've tried with inpolygon but the results are the same .. p is always giving [x y z 0] ...
Thanks for th advice... i didn't know about inpolygon

"Joe Nunes" <vazdepaivanunes@gmail.com> wrote in message <hejkg8$lr0$1@fred.mathworks.com>...
> ImageAnalyst <imageanalyst@mailinator.com> wrote in message <03d5db68-2214-400a-b5ad-e4c248095902@l13g2000yqb.googlegroups.com>...
> > I've never heard of isInsideTriangle and it's not in my help.
> > Presumably it's something you wrote. So I don't know why it never
> > returns 1. Why don't you try the built-in MATLAB function inpolygon()
> > instead?
>
> I've tried with inpolygon but the results are the same .. p is always giving [x y z 0] ...
> Thanks for th advice... i didn't know about inpolygon

============

It might also be worth considering vert2con.m from the FileExchange.
VERT2CON assume a priori that the polygon is convex and so has a lot less pre-checking overhead than inpolygon (I'd imagine).

"Matt " <xys@whatever.com> wrote in message <hejmr9$kh7$1@fred.mathworks.com>...
>
> It might also be worth considering vert2con.m from the FileExchange.
> VERT2CON assume a priori that the polygon is convex and so has a lot less pre-checking overhead than inpolygon (I'd imagine).
====================================

In a previous and similar thread, I also cooked up the following slimmed-down version of VERT2CON for 2D polygons. An example is given in the help block of how to use it to detect whether points are inside a triangle.


function [A,b]=vert2con_special(a)
%Finds the expression of a 2D polygon as a set of linear inequalities from
%a set of vertices
%
% [A,b]=vert2con_special(a)
%
%in:
%
% a: Nx2 matrix whos rows are polygon vertex coordinates. The rows must
% must be ordered so that adjacent rows correspond to adjacent vertices
% (which will trivially be the case for triangles).
%
%out:
%
% [A,b]: Nx1 vector and Nx2 matrix such that A*x<=b if and only if x is a point
% inside the polygon
%
%
%Example: Detect whether a point is in a triangle
%
% %%%data
% Vertices=[0 0; 1 0; 0 1]; %vertices of a triangle
% p1=[.5;.25]; %a point inside the triangle
% p2=[.5;-.25];%a point outside the triangle
%
% [A,b]=vert2con_special(Vertices);
%
% >>all(A*p1<=b)
%
% ans =
%
% 1
%
% >>all(A*p2<=b)
%
% ans =
%
% 0



centroid=mean(a).';
R=[0 1; -1 0];

A=diff([a;a(1,:)])*R;

b=sum(A.*a,2);

ii=(A*centroid>=b);

b(ii)=-b(ii);
A(ii,:)=-A(ii,:);

"Joe Nunes" <vazdepaivanunes@gmail.com> wrote in message <hejhig$ecg$1@fred.mathworks.com>...
> Hello,
>
> I have a matrix of points, and a simple patch of triangles. I have the indices of those triangles and the coordenates of the vertices. I need to find in which of the triangle, is each point.
>
> p is the matrix with the points
> tri are the indices of the triangles in the form [12 13 14, 21 2 3, etc]
> face_triangulos are the coordinates of the points which formed the triangles
>
> I am assinging for each point the form [x y z T], where T is the triangle in which the point is contained. z is always zero ..

Take a look at function TSEARCH or method DelaunayTri.pointLocation

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hejumg$17j$1@fred.mathworks.com>...
> "Joe Nunes" <vazdepaivanunes@gmail.com> wrote in message <hejhig$ecg$1@fred.mathworks.com>...
> > Hello,
> >
> > I have a matrix of points, and a simple patch of triangles. I have the indices of those triangles and the coordenates of the vertices. I need to find in which of the triangle, is each point.
> >
> > p is the matrix with the points
> > tri are the indices of the triangles in the form [12 13 14, 21 2 3, etc]
> > face_triangulos are the coordinates of the points which formed the triangles
> >
> > I am assinging for each point the form [x y z T], where T is the triangle in which the point is contained. z is always zero ..
>
> Take a look at function TSEARCH or method DelaunayTri.pointLocation
>
> Bruno

Thank you all for your replies. I'll go have a look at those issues.

Regards

"Joe Nunes" <vazdepaivanunes@gmail.com> wrote in message <hek06n$400$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hejumg$17j$1@fred.mathworks.com>...
> > "Joe Nunes" <vazdepaivanunes@gmail.com> wrote in message <hejhig$ecg$1@fred.mathworks.com>...
> > > Hello,
> > >
> > > I have a matrix of points, and a simple patch of triangles. I have the indices of those triangles and the coordenates of the vertices. I need to find in which of the triangle, is each point.
> > >
> > > p is the matrix with the points
> > > tri are the indices of the triangles in the form [12 13 14, 21 2 3, etc]
> > > face_triangulos are the coordinates of the points which formed the triangles
> > >
> > > I am assinging for each point the form [x y z T], where T is the triangle in which the point is contained. z is always zero ..
> >
> > Take a look at function TSEARCH or method DelaunayTri.pointLocation
> >
> > Bruno
>
> Thank you all for your replies. I'll go have a look at those issues.
>
> Regards

It works fine with inpolygon.

        v1 = [face_triangulos(tri(I,1),1) face_triangulos(tri(I,1),2)];
        v2 = [face_triangulos(tri(I,2),1) face_triangulos(tri(I,2),2)];
        v3 = [face_triangulos(tri(I,3),1) face_triangulos(tri(I,3),2)];
        
        VX = [v1(1) v2(1) v3(1)]';
        VY = [v1(2) v2(2) v3(2)]';
      
        if(inpolygon(p(J,1), p(J,2), VX, VY) == [1] )

thank you!
regards