Search code examples
algorithmvectorpolar-coordinates

algorithm to select a pair of vectors for the best "zigzag" profile

I have a set of distinct 2D vectors (over real numbers), pointing in different directions. We are allowed to pick a pair of vectors and construct their linear combination, such that the coefficients are positive and their sum is 1. In simple words we are allowed to take a "weighted average" of any two vectors.

My goal is for an arbitrary direction to pick a pair of vectors whose "weighted average" is in this direction and is maximized. Speaking algebraically given vectors a and b and a direction vector n we are interested in maximizing this value:

[ a cross b ] / [ (a - b) cross n ]

i.e. pick a and b which maximize this value.

To be concrete the application of this problem is for sailing boats. For every apparent wind direction the boat will have a velocity given by a polar diagram. Here's an example of such a diagram: Velocity diagram

(Each line in this diagram corresponds to a specific wind magnitude). Note the "impossible" front sector of about 30 degrees in each direction.

So that in some direction the velocity will be high, for some - low, and for some directions it's impossible to sail directly (for instance in the direction strictly opposite to the wind).

If we need to advance in a direction in which we can't sail directly (or the velocity isn't optimal) - it's possible to advance in zigzags. This is called tacking.

Now, my goal is to recalculate a new diagram which denotes the average advance velocity in any direction, either directly or indirectly. For instance for the above diagram the corrected diagram would be this:

Corrected velocity diagram

Note that there are no more "impossible" directions. For some directions the diagram resembles the original one, where it's best to advance directly, and no maneuver is required. For others - it shows the maximum average advance velocity in this direction assuming the most optimal maneuver is periodically performed.

What would be the most optimal algorithm to calculate this? Assume the diagram is given as a discrete set of azimuth-velocity pairs, from which we can calculate the vectors.

So far I just check all the vector pairs to select the best. Well, there're cut-off criterias, such as picking only vectors with positive projection on the advance direction, and opposite perpendicular projections, but still the complexity is O(N^2). I wonder if there's a more efficient algorithm.

EDIT

Many thanks to @mcdowella. For both computer-science and sailor answers!

I too thought in terms of convex polygon, figured out that it's only worth probing vectors on that hull (i.e. if you take a superposition of 2 vectors on this hull, and try to replace one of them by a vector which isn't on this hull, the result would be worse since new vector's projection on the needed direction is worse than of both source vectors).

However I didn't realize that any "weighted average" of 2 vectors is actually a straight line segment connecting those vectors, hence the final diagram is indeed this convex hull! And, as we can see, this is also in agreement with what I calculated by "brute-force" algorithm.

Solution

  • Now the computer science answer

    A tacking strategy gives you the convex combination of the vectors from the legs that make up the tacks.

    So consider the outline made by just one contour in your diagram. The set of all possible best speeds and directions is the convex polygon formed by taking all convex combinations of the vectors to the contour. So what you want to do is form the convex hull of your contour (https://en.wikipedia.org/wiki/Convex_hull). To find out how to go fast in any particular direction, intersect that vector with the convex hull, and use tacks with legs that correspond to the corners on either side of the edge of the convex hull that you intersect with.

    Looking at your diagram, the contour is concave straight upwind and straight downwind, which is what you would expect. However there is also another concave section, somewhere between 4 and 5 O'Clock and also symmetrically between 7 and 8 O'Clock, which appears as a straight line in your corrected diagram - so I guess there is a third direction to tack in, using two reaches on the same side of the wind which I don't recognise from traditional sailing.