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