[Algorithm] Self Crossing

Self Crossing

Problem Statement:

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south, x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.

Solution: Polygon pattern, O(n) solution

At first glance it may seem to be very difficult to solve. I initially wanted to keep track of the points and use bounding box to determine the crossing but still cannot get it right.

Now the solution for this is not very easy to come up with, I read someone's post on how to solve this and I'm just trying to explain that solution here.

Basically since we are only allowed to go straight left, right, up and down and in a counter-clockwise order, the shape of the points movement forms polygons, muck like tetrix blocks really.

These blocks indeed are just two kinds, one is rectangle the other is L-shape pentagon. The rectangle shape would have two different sub types, one is made up by 4 lines, the other is made up by 5 lines.

For three types there are constraints:

Type 1: x[n-2] <= x[n] && x[n-1] <= x[n-3]

Type 2: x[n] + x[n-4] >= x[n-2] && x[n-1] == x[n-3]

Type 3: x[n] + x[n-4] >= x[n-2] && x[n-1] + x[n-5] >= x[n-3] && x[n-1] <= x[n-3] && x[n-2] >= x[n-4]

Those shapes are orientation-less, meaning orientation doesn't matter for these three patterns, one can rotate them and those conditions still hold. This means that for any point in the given sequence we just need to check those 3 different constraints, if any one of them breaks there must be a crossing. No previous states need to be memorized.

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: bool isSelfCrossing(vector<int>& x) { int ret = check(x); return ret != 0; } inline int check(const vector<int>& x) { int n = x.size(); for (int i=0; i<n; i++) { if (i >= 3 && x[i-2] <= x[i] && x[i-1] <= x[i-3]) return 1; if (i >= 4 && x[i] + x[i-4] >= x[i-2] && x[i-1] == x[i-3]) return 2; if (i >= 5 && x[i] + x[i-4] >= x[i-2] && x[i-1] + x[i-5] >= x[i-3] && x[i-1] <= x[i-3] && x[i-2] >= x[i-4]) return 3; } return 0; } };