Re: Point order
- To: mathgroup at smc.vnet.net
- Subject: [mg30379] Re: Point order
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Tue, 14 Aug 2001 03:45:30 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Thanks to Allan's message I noticed an emarassing elementary
mathematical error that ruined my clockwiseQ code. The point is very
simple. If we think of a permutation of Range[n] representing an
arrangement of points on a circle, than it is not true that signature is
an invariant of the "rotation along a circle", unless n is odd. For
example:
In[1]:=
Signature/@NestList[(RotateRight[#])&,Range[4],3]
Out[1]=
{1,-1,1,-1}
In[2]:=
Signature/@NestList[(RotateRight[#])&,Range[5],4]
Out[2]=
{1,1,1,1,1}
Also, Signature[Reverse[l]]==-1 is not true for all n, e.g.:
In[9]:=
Signature[Reverse[Range[4]]]
Out[9]=
1
On the other hand, if n==3 then everything works as I had assumed (the
reason for this mistake was my habit of dealing with simplexes, i.e. in
this case triangles):
In[10]:=
Signature/@NestList[(RotateRight[#])&,Range[3],2]
Out[10]=
{1,1,1}
In[11]:=
Signature[Reverse[Range[3]]]
Out[11]=
-1
However, when comparing the orientation of polygon and its convex hull
it is enough to compare the orientation of just three common points. So
the following version of my code should now be correct:
<< DiscreteMath`ComputationalGeometry`
clockwiseQ[l_List] := Module[{ch = l[[Take[ConvexHull[l, AllPoints ->
False], 3]]]}, Signature[Flatten[Position[Select[l,
MemberQ[ch, #] &], #] & /@ ch]] == -1]
Now with:
In[3]:=
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]//Timing
Out[4]=
{0.03 Second,True}
This now agrees with the answer given by SweptArea. Of course Allan's
SweptArea is much more efficient because the best ConvexHull algorithms
are O[n log[n] (I think), and Mathematica's implementation seems even
slower.
Andrzej
On Sunday, August 12, 2001, at 10:32 PM, Allan Hayes wrote:
> 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
>>>
>>>
>>>
>>
>>
>
>
>
>