Re: Point order
- To: mathgroup at smc.vnet.net
- Subject: [mg30362] Re: [mg30347] Point order
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Sun, 12 Aug 2001 02:29:51 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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
>
>
>