find in which triangle algorithm
in [Matlab]
|
From: Joe Nunes on 25 Nov 2009 10:13 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
From: ImageAnalyst on 25 Nov 2009 10:22 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?
From: Joe Nunes on 25 Nov 2009 11:03 ImageAnalyst <imageanalyst(a)mailinator.com> wrote in message <03d5db68-2214-400a-b5ad-e4c248095902(a)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
From: Matt on 25 Nov 2009 11:43 "Joe Nunes" <vazdepaivanunes(a)gmail.com> wrote in message <hejkg8$lr0$1(a)fred.mathworks.com>... > ImageAnalyst <imageanalyst(a)mailinator.com> wrote in message <03d5db68-2214-400a-b5ad-e4c248095902(a)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).
From: Matt on 25 Nov 2009 12:10
"Matt " <xys(a)whatever.com> wrote in message <hejmr9$kh7$1(a)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,:); |