Path: news.mathworks.com!not-for-mail From: <HIDDEN> Newsgroups: comp.soft-sys.matlab Subject: Re: Extract points (on a sphere) inside polygon. HELP!!! Date: Tue, 23 Aug 2011 14:12:14 +0000 (UTC) Organization: The MathWorks, Inc. Lines: 87 Message-ID: <j30cfu$bu3$1@newscl01ah.mathworks.com> References: <5525763.1178619749040.JavaMail.jakarta@nitrogen.mathforum.org> <ellieandrogerxyzzy-0805071153420001@dialup-4.232.228.18.dial1.losangeles1.level3.net> Reply-To: <HIDDEN> NNTP-Posting-Host: www-05-blr.mathworks.com Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: newscl01ah.mathworks.com 1314108734 12227 172.30.248.37 (23 Aug 2011 14:12:14 GMT) X-Complaints-To: news@mathworks.com NNTP-Posting-Date: Tue, 23 Aug 2011 14:12:14 +0000 (UTC) X-Newsreader: MATLAB Central Newsreader 2996139 Xref: news.mathworks.com comp.soft-sys.matlab:740969 ellieandrogerxyzzy@mindspring.com.invalid (Roger Stafford) wrote in message <ellieandrogerxyzzy-0805071153420001@dialup-4.232.228.18.dial1.losangeles1.level3.net>... > In article > <5525763.1178619749040.JavaMail.jakarta@nitrogen.mathforum.org>, General > <mammasis82@hotmail.com> wrote: > > > Hi everyone, > > > > I have created a sphere in Matlab and drawn some points on it. I am > trying to extract some points directly from the sphere by drawing a > polygon around those points. Unfortunately I cannot understand how to > this. Can anybody help me? > > > > Many Thanks > > Regards > > Alex > -------------------- > You haven't stated what coordinate system you are using to locate your > various points and the vertices of the "polygon". Whatever it is, > presumably you can convert it to Cartesian coordinates with origin at the > center of the sphere. I will assume that the polygon vertices are > connected by great circle arcs (face angles) which are less than than pi > in arc angle. I will assume moreover that the polygon is "convex" in the > sense that all interior spherical angles (dihedral angles) of the polygon > are less than pi. > > Let P1 = (x1,y1,z1) and P2 = (x2,y2,z2) be two successive vertices of > the polygon and ordered so that the polygon interior lies to the left of > the vector pointing from P1 to P2. If P = (x,y,z) is an arbitrary point, > then > > dot(P,cross(P1,P2)) >= 0 > > if P lies on the side of the plane through P1, P2, and the origin, which > contains the interior of the polygon. So this gives you the algorithm. > Test a point P = (x,y,z) to see if it satisfies the above inequality for > each pair of adjacent vertices in the polygon assuming they are ordered in > the above "right hand" sense. > > That can be done in the following way. Let A be an n x 3 array in which > successive rows give the x, y, and z coordinates of successive vertices > ordered as above. Define a shifted version of A: > > B = A([2:n,1],:); > > Then the row vector P = [x,y,z] represents a point (x,y,z) in the interior > of the polygon if and only if: > > all(dot(P,cross(A,B,2),2)) >= 0 > > is true. > > Roger Stafford Hi Roger I wanted to find out if a point is inside a polygon on earth or not and tried to use your amazing technique http://www.mathworks.com.au/matlabcentral/newsreader/view_thread/147669 I computed p1=cross_product(edge_sp_4,edge_sp_3) p2=cross_product(edge_sp_3,edge_sp_2) p3=cross_product(edge_sp_2,edge_sp_1) p4=cross_product(edge_sp_1,edge_sp_4) if(dot_product(P,p1) >= 0 .AND. & dot_product(P,p2) >= 0 .AND. & dot_product(P,p3) >= 0 .AND. & dot_product(P,p4) >= 0 ) then checks=.true. endif Here edge_sp_1 ,edge_sp_2,edge_sp_3,edge_sp_4 are actually verticies of the polygon that have been converted to x y z using . P1,P2,P3,P4 are points arranged in counter clockwise direction p(1) = R*cos(p_lon)*cos(p_lat) p(2) = R*sin(p_lon)*cos(p_lat) p(3) = R*sin(p_lat) P is the point to be tested. It does not work always. Am i missing something. To be true I give it a set of points that I know are inside/outside the polygon. It shows that some of the points that are detected inside are actually outside the polygon.