Algorithms – How to Determine if Ordered Coordinates Form a Simple Curve

algorithmsgeometry

I hope it is the right place to ask this. I wasn't sure if it belongs to Stack Overflow or Computer Science.
Eventually this seemed more suitable.

Anyway, some background first:
A closed curve, is a curve with no endpoints and which completely encloses an area.
A simple curve, is a curve that does not cross itself.

Example:

enter image description here

Now, given n ordered (x,y) coordinates that represents mouse movement, it is easy to determine if they form a closed curve (given an upper bound on the allowed distance between two points, of-course), but is there an algorithm that will determine whether or not the coordinates form a simple curve?

I tried to look online for an answer, but couldn't find relevant solutions.

Best Answer

You could argue that a curve is simple if there are no two line segments between points such that the lines intersect, meaning you could check if a curve is simple by verifying the absence of this condition.

The algorithm would look something like:

for each p1, p2 in pointlist
  for each p3, p4 in pointlist
     if line_segment(p1, p2) intersects line_segment(p3, p4)
        return false
return true

Note that p2 would be the successive point after p1 and similarly, p4 would be the successive point after p3. In order to avoid redundancy, points p3 and p4 could start after points p1 and p2. This should be easily done in O(n^2) time. Be careful in your check for intersection since at least once the lines will be the same (no dividing by zero).

If you have many such points, you could skip every other point and this algorithm will run 4 times faster at the small risk that a truly intersecting line may not be detected should the curve approach a tangent.

Related Solutions

How to Permute Pairs Across a Set in C#

I don't speak C#, but here's the general idea in C-like pseudocode:

items = {A, B, C, D, E}
for (i = 0; i < items.count-1; i++)
    for (j = i+1; j < items.count; j++) {
        doSomethingWithPair(items[i], items[j])
    }
}

In English, pick the first item and combine it with all the subsequent items. Then pick the next item and combine it with all subsequent items, and so on until you've combined the penultimate item with the ultimate item.

If order were important, i.e. you wanted permutations instead of combinations, pick both members of each pair from the full range of items. Change the outer loop so that it goes all the way to the end and the inner loop so that it starts from the beginning. Remember to check that i != j if you don't want permutations with replacement:

for (i = 0; i < items.count; i++) {
    for (j = 0; j < items.count; j++) {
        if (i == j) continue;        // avoid AA, BB, etc.
        doSomethingWithPair(items[i], items[j]);
    }
}

VLSI Chips – How to Determine Which Chips Are Good

I think this is a clustering problem: you have two clusters - the good chips and the bad chips. Your test tells you if two chips belong in the same cluster or not - at least under my interpetation of the question you have asked. The reference provided in the answer by Woot4Moo suggests a different question to this.

For the first part of the test, pick one chip and test every other chip against it. You get two clusters of chips - those that are of the same kind as the first chip, and those that are different. The good chips are in the larger cluster, so pick one at random.

For the second part, use n chips for testing, so that for each chip you have an n-bit pattern, saying whether it was in the same cluster as each of the n test chips. Expect to see mostly two sorts of patterns, each the inverse of the other. You can use this to sort the chips into two clusters as before, and hope that the larger cluster is composed of good chips.

Best Answer

Related Solutions

How to Permute Pairs Across a Set in C#

VLSI Chips – How to Determine Which Chips Are Good

Related Topic