Dtyjlui

I have a list of 100 vectors 2D (x,y) defined by RandomReal[1.0, {100, 2}] and a given forward vector such as {1, 1}. My ultimate objective is to find the vector on the most right hand side of the forward vector. If there is non such a vector, then pick up the first vector on the left of the forward vector.

I can do this by firstly classifying the initial list of vectors into 2 lists: 1 list contains all vectors on the right hand side of the forward vector. The second contains all vectors on its left hand side. The criterion to define whether a vector on the right hand side of the forward vector is that its cross product between the considered vector with the forward vector is positive. A negative result would mean it is on the left of the forward vector.

The next step would be to check if the list of the vectors on the right hand side of the forward vector is empty. If not, check the relative position of the first 2 vectors in that list, only keep the vector on the right hand side, and then check the relative position between the kept vector and the third vector in the list and continue to do so until the end of the list.

If the list of the vectors on the right hand side of the forward vector is empty, do the above process on this list instead.

My questions here are:
1. This algorithm contains a lot of "if" statements, is it that we should try to stay away from that sort of thing in Mathematica? If that's the case, how can I do it without "if" ?
2. If "if" cannot be avoided, how can I implement the above algorithm in a nice way in Mathematica.

(For more info: I've done this in VB.net but got I stuck in Mathematica. This is the task that I have to find a cycle in a graph. The vertices are defined by its 2D coordinates. It requires the cycle to start at the most left vertex and the keep "turn right" at every vertex until the path comes back to the initial vertex.)

You can define a function that returns the positive angle between two vectors:

positiveAngle[{u1_, u2_}, {v1_, v2_}] := 

 N@Mod[ArcTan[u2, u1] - ArcTan[v2, v1], 2 π]

Then, if your input is pts and vec:

pts = RandomReal[1.0, {10, 2}];

vec = {1, 1};

You can simply use:

min = First[MinimalBy[pts, positiveAngle[#, vec] &]]

to get the first vector with the smallest positive angle to vec

If we order the points by positiveAngle, we can see the order in which they would be picked:

Graphics[{

  {Dashed, Line[{{0, 0}, vec}]},

  {LightGray, Line[{{0, 0}, #}] & /@ pts},

  {Red, Arrow[{{0, 0}, min}]},

  MapIndexed[

   Text[#2[[1]], #1] &, SortBy[pts, positiveAngle[#, vec] &]]

  }]

If your points are in all 4 quadrants, they would be ordered like this:

pts = CirclePoints[.9, 24];    

Graphics[{{Dashed, Line[{{0, 0}, vec}]}, {LightGray, 

   Line[{{0, 0}, #}] & /@ pts}, {Red, Arrow[{{0, 0}, min}]}, 

  MapIndexed[Text[#2[[1]], #1] &, 

   SortBy[pts, positiveAngle[#, vec] &]]}]

Different orderings should be easy to achieved using e.g. Piecewise functions

pts = RandomReal[1.0, {100, 2}];

vec = {1, 1};

Rotate the elements of pts such that you want the one with small positive first coordinate (or maximal negative first coordinate if no one has positive first coordinate):

rotated = Transpose[RotationMatrix[{vec, {0, 1}}].Transpose[pts]];

Add the vector {0, 0} at position 1 and make a list with the vector indices ordering the points from left to right:

order = Ordering[Prepend[rotated, {0, 0}]]

Now Ordering[order, 1] yields the position of {0, 0}

pts[[Extract[Append[order, order[[-2]]], Ordering[order, 1] + 1] - 1]]

Here is an implementation of the algorithm that you describe:

pts = RandomReal[2, {50, 2}];

vec = {1, 1};



rhsQ[vec_, pt_] := Sign@Last@Cross[Append[vec, 0], Append[pt, 0]] == -1



onRHS = rhsQ[vec, #] & /@ pts;



rhs = Pick[pts, onRHS];

lhs = Pick[pts, onRHS];



rightmost[v1_, v2_] := If[rhsQ[v2, v1], v2, v1]

findRightmost[vecs_] := Fold[rightmost, vecs]



res = If[

   rhs === {},

   findRightmost[lhs],

   findRightmost[rhs]

   ];



Graphics[{

  Line[{{0, 0}, Normalize[#]}] & /@ pts,

  Red, Line[{{0, 0}, 1.1 Normalize[vec]}],

  Green, Line[{{0, 0}, 1.1 Normalize[res]}]

  }]

There are two ifs in there, but I don't see it as a problem. I do however favor the type of solution that Coolwater posted.

Another alternative using VectorAngle and Cross...

vec = {1, 1};

pts = RandomReal[1.0, {50, 2}];



vectorAngles[v1_?VectorQ, v2 : {__?VectorQ}] :=

With[{f = {#, Sign[Last@Cross[PadRight[v1, 3], PadRight[#, 3]]] VectorAngle[v1, #]} &}, f /@ v2]



pickVector[pa : {{_?VectorQ, _?NumberQ} ..}] :=

TakeSmallestBy[TakeSmallestBy[pa, Abs[Last[#]] &, 2], Last, 1]



pickVector[vectorAngles[vec, pts]]



Graphics[{LightBrown, Arrow[{{0, 0}, #}]& /@ pts, Blue, Arrow[{{0, 0}, vec}], 

Text["Forward Vector", vec], Darker[Green], Arrow[{{0, 0},

pickVector[vecAngle][[1, 1]]}]}, Axes -> True]