5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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:

enter image description here

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:

enter image description here

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

$\endgroup$
  • $\begingroup$ Why don't you use VectorAngle? $\endgroup$ – Henrik Schumacher Jan 2 at 8:47
  • $\begingroup$ @HenrikSchumacher: I tried that first, but the returned angle isn't signed - vectors "left" and "right" of vec both get positive angles. $\endgroup$ – Niki Estner Jan 2 at 9:40
  • $\begingroup$ Ah, now I get what you mean by positiveAngle. ^^ I suggest to call it orientedAngle. Nevermind; you already have my upvote. $\endgroup$ – Henrik Schumacher Jan 2 at 9:42
  • 1
    $\begingroup$ @HenrikSchumacher: I see your point. My idea was that the angle should never be negative, or MinimalBy will choose a negative angle if there is one. So I use a positive angle, in the range from 0..2 π. $\endgroup$ – Niki Estner Jan 2 at 9:55
  • $\begingroup$ I am wondering if this method would still work if there is a change in the initial condition that the random point (x,y) has each component x or y now falls in range [-1,1], i.e. the vectors can point in all directions, not just 1 quarter of the plane like you've plotted? $\endgroup$ – N.T.C Jan 2 at 11:43
9
$\begingroup$
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]]
$\endgroup$
3
$\begingroup$

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

Mathematica graphics

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.

$\endgroup$
2
$\begingroup$

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]

Vector Example

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.