Is this algorithm a good way to determine if two arrays have same contents in same order?

Question

So I have two arrays that each represent a simple closed polygon as an in order traversed array of points. The last element is the same as the first element. I'm implementing an equals algorithm for any 2 simple closed polygons.

Array A would be like this [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6, pnt1]
Array B would be like this [pnt2, pnt3, pnt4, pnt5, pnt6, pnt1, pnt2]
Array C would be like this [pnt2, pnt1, pnt6, pnt5, pnt4, pnt3, pnt2]
Array D would be like this [pnt1, pnt2, pnt3, pnt5, pnt6, pnt4, pnt1]

Arrays A and B are equal because the points are in the same order and same points. Arrays A and C are equal because the points are in the same order (but reversed), and so are B and C for the same reason.

Array D is not equal to any of the other arrays, because the point traversal is out of order.

So my algorithm is as follows:

1) compare lengths of arrays, must contain same # of elements - constant time

2) find A[0] in B set as K - linear search, linear time

3) see if A[1] = B[K+1] and so on until A[n], linear time

naturally indices would wrap around the end of the array, perhaps via a mod operator.

is there an algorithm that can do better than this?

Answer 1

I assume that by "simple" you mean a polygon without holes or self-intersections, but that may touch itself only at vertices. For example, the following:

This sort of scenario might not matter in your case, but some polygon algorithms rely on such shapes to form the contours making up a complex polygon, so it's handy to be able to cope with them.

In this case, these two polygons should compare equal:

P = ABCADEAFGAHIAJKA
Q = FGAHIAJKABCADEAF

Some of the given algorithms might overlook this because the first (and lexicographically minimal) vertex A in P is repeated. However, so long as we know that no edge is repeated, we can adapt the algorithm without much trouble:

1. Search for P[0] in Q.
2. Upon finding a match at Q[i], compare P[1] to Q[i-1] and Q[i+1] (with appropriate wrapping).
3. If neither is a match return to 1 and continue searching for P[0] in Q, starting from Q[i+1].
4. Once a match is found in step 2, continue comparing by advancing forward through P and in the same direction through Q. Either a mismatch will be found, in which case the polygons are different and you can stop immediately (no need to continue searching for another match for P[0]), or you'll traverse all the way through, and they're identical.

As an aside, if you want to use an algorithm that needs to identify the lexicographically minimal vertex in a contour, but where vertices may be repeated, you can break ties by considering either the minimal neighbouring vertex or the clockwise (or counter-clockwise, so long as you're consistent) neighbouring vertex. Again, this depends on edges not being repeated.

Answer 2

If preprocessing is not allowed, this problem is worst case Omega(N) just because finding one vertex of one polygon among the vertices of the other can take N comparisons.

So there isn't much better than your algorithm, which runs in optimal time O(N). [Insert a step between 2 and 3 to determine the traversal order, though.]

If preprocessing is allowed, for every polygon you can identify the first vertex in the (X, Y) lexicographical order. Let us call it the main vertex. By doing this, you will make the step 1 of your algorithm useless because two equal polygons have the same main vertex, and spare a linear search.

Even better, you could associate a signature to the polygons by computing a CRC on the coordinates, starting from the main vertex. Then you would detect different polygons with a high probability in time O(1) just by comparing the signatures.

Answer 3

To make such a comparison, you can check if one array is a rotation of the other (except for the last elements).

First off, remove the repeated elements as ElKamino pointed out. Then basically, you want to know if A can be obtained by rotating the elements of B.

When A=[x1, x2, ..., xk], B will have the same contents in the same order as A if and only if B=[x3, x4, ..., xk, x1, x2] or something like that. In such a case, B can be called a rotation of A. However, that's not enough, since you also want to check if the order is the same but reversed. Then, you can apply the same procedure for the reverse of B, or the reverse of A.

Pseudocode

def isSamePolygon(A, B):
    remove the last element of A and last element of B
    return isRotation(A, B) or isRotation(A, reverse(B))

def isRotation(A, B): // returns true if A is a rotation of B
    // create an array which has two copies of A.
    // e.g [a1, a2, ..., ai, a1, a2, ..., ai]
    if (size(A) != size(B))
        return false
    temp_array = concat(A, A)
    return true if temp_array contains the elements of B in the exact same order,
        false otherwise

Analysis

The running time and space complexities of isRotation is linear in the size of max(size(A), size(B)). This is because creating the temp_array takes linear time and linear space in the size of A. Similarly, checking if B is contained in A also takes linear time to run.

Correct me if I'm wrong, but using this algorithm, you can't reduce asymptotic complexities. However though, you can optimize it to run faster. You might want to swap A and B if size(A)>size(B). Furthermore; you can check for the reverse at the same time, instead doing two calls.

Answer 4

Summary:

1. Remove the repeated point
2. Find the location i of the minimum value
3. If value at i-1 is lower than value at i+1 reverse the string (have to take of edge cases, i.e. i=0 or i=n-1)
4. Rotate the array so that minimum value is at the head

Total complexity: O(n)

NOTE: Step 3 and 4 are not absolutely necessary. From step 2 you can get location of the minimum and from step 3 get the orientation. While comparing two different arrays, just start with comparing from *location*s of the minimums and move according to the orientation .

Eg:

[pnt1, pnt2, pnt3, pnt4, pnt5, pnt6, pnt1] -> [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6] -> [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6]

[pnt2, pnt3, pnt4, pnt5, pnt6, pnt1, pnt2] -> [pnt2, pnt3, pnt4, pnt5, pnt6, pnt1] -> [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6]

[pnt2, pnt1, pnt6, pnt5, pnt4, pnt3, pnt2] -> [pnt2, pnt1, pnt6, pnt5, pnt4, pnt3] -> [pnt3, pnt4, pnt5, pnt6, pnt1, pnt2] -> [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6]

[pnt1, pnt2, pnt3, pnt5, pnt6, pnt4, pnt1] -> [pnt1, pnt2, pnt3, pnt5, pnt6, pnt4] -> [pnt1, pnt2, pnt3, pnt5, pnt6, pnt4]