MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

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
> >
> >
> >
>
>




  • Prev by Date: Intersection of polygons and more
  • Next by Date: Re: Point order
  • Previous by thread: Re: Point order
  • Next by thread: Re: Point order