Re: Point order
- To: mathgroup at smc.vnet.net
- Subject: [mg30376] Re: Point order
- From: "Allan Hayes" <hay at haystack.demon.co.uk>
- Date: Tue, 14 Aug 2001 03:45:28 -0400 (EDT)
- References: <9l583p$5ac$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Here is a faster method than Andrzej's posting ( Andrzej - it looks from the tests below that your code is giving the answer the wrong way round) It based on the following USAGE: SweptArea::usage = "SweptArea[{p,q,...}, o] for 2D points p,q,...,, o,gives the signed area swept out by the radius vector {o,x} as x follows the polygonal line p,q ... .\n SweptArea[{p,q,...}] gives the signed area of the polygon p,q,... (the polygon is closed by returning to p at the end). " SweptAngle::usage = "SweptAngle[{p,q,...}, o] for 2D points p,q,...,, o (o not ont the polygonal line p, q,....)gives the signed angle swept out by the radius vector {o,x} as x follows the polygonal line p, q ... ." CODE: SweptArea[pts_] := (#1.RotateLeft[#2] - RotateLeft[#1].#2)&@@Thread[pts]/2 SweptArea[pts_, o_] :=SweptArea[Prepend[pts,o]] SweptAngle[pts_, p_]:=Plus@@(Arg[Drop[#,1]/Drop[#,-1]]&[ Complex@@@pts-Complex@@p]) Using Andrzej's test poly={{4.4,14},{6.7,15.25},{6.9,12.8},{9.5,14.9},{13.2,11.9},{10.3,12.3},{6. 8, 9.5},{13.3,7.7},{0.6,1.1},{1.3,2.4},{2.45,4.7}}; I get SweptArea[poly]//Timing {0. Second,-72.3525} Since this is negative the rotation is clockwise. This is supported by SweptAngle[Append[poly, First[poly]], {6,7}]//Timing {0. Second,-6.28319} and by the picture. Show[Graphics[{Line[poly], PointSize[.02],Point[poly[[1]]]}]] But it does not agree with Andrzej's function ClockwiseQ << DiscreteMath`ComputationalGeometry` clockwiseQ[l_List] := Module[{ch = l[[ConvexHull[l]]]}, Signature[ Flatten[Position[Select[l, MemberQ[ch, #] &], #] & /@ ch]] == -1] clockwiseQ[poly] file://Timing {0.16 Second,False} -- Allan --------------------- Allan Hayes Mathematica Training and Consulting Leicester UK www.haystack.demon.co.uk hay at haystack.demon.co.uk Voice: +44 (0)116 271 4198 Fax: +44 (0)870 164 0565 "Andrzej Kozlowski" <andrzej at tuins.ac.jp> wrote in message news:9l583p$5ac$1 at smc.vnet.net... > I assume that you what you man is this. You are given an ordered set of > points (in two dimensions) which describe a simple polygon, that is one > without self intersections (otherwise the question does not make sense). > You want to know whether your ordering corresponds to moving clockwise > or counter-clockwise along the polygon. > > One way to do this (which may not be the fastest) is to make use of the > function ConvexHull of the ComputationslGeometry package. Given a set > of coordinates of points in 2 dimensions it returns a sublist of those > points which generate the convex hull of the original set, arranged in > counterclockwise order. So all we need to check is if these points > appear in the original list in the same order. The following function > should do this: > > << DiscreteMath`ComputationalGeometry` > > clockwiseQ[l_List] := > Module[{ch = l[[ConvexHull[l]]]}, > Signature[ > Flatten[Position[Select[l, MemberQ[ch, #] &], #] & /@ ch]] == -1] > > for example: > > poly = {{4.4, 14}, {6.7, 15.25}, {6.9, 12.8}, {9.5, 14.9}, {13.2, > 11.9}, {10.3, 12.3}, {6.8, 9.5}, {13.3, 7.7}, {0.6, 1.1}, {1.3, > 2.4}, {2.45, 4.7}}; > > In[4]:= > clockwiseQ[poly] > > Out[4]= > False > > In[5]:= > clockwiseQ[Reverse[poly]] > > Out[5]= > True > > Andrzej Kozlowski > Toyama International University > JAPAN > http://platon.c.u-tokyo.ac.jp/andrzej/ > > On Saturday, August 11, 2001, at 04:40 PM, Rafael Sanchez wrote: > > > Hello all, > > If I draw a polygone of n sides, how do I know if the points are drawn > > in clockwise order or not? > > Thanks > > Rafael > > > > > > > >