Locating all elements between starting and ending points, given by value (not index)

The problem is as follows,

I would be given a set of x and y coordinates(an coordinate array of around 30 t开发者_Go百科o 40 thousand) of a long rope. The rope is lying on the ground and can be in any shape.

Now I would be given a start point(essentially x and y coordinate) and an ending point.

What is the efficient way to determine the set of x and y coordinates from the above mentioned coordinate array lie between the start and end points.

Exhaustive searching ie looping 40k times is not an acceptable solution (mentioned on the question paper)

A little bit margin for error is acceptable

---

We need to find the start point in the array, then the end point. For each, we can think of the rope as describing a function of distance from that point, and we're looking for the lowest point on that distance graph. If one point is a long way away and another is pretty close, we can do some kind of interpolation guess of where to search next.

distance
    |  /---\
    |--     \  /\       -
    |        --  ------- --   ------     ----------    -
    |                      \ /      \---/          \--/
    +-----------------------X--------------------------- array index

In the representation above, we want to find "X"... we look at the distances at a few points, get an impression of the slope of the distance curve, possibly even the rate of change of that slope, to help guide our next bit of probing....

To refine the basic approach of doing binary- or interpolated- searches in areas where we know the distance values are low, we may be able to use the following:

• if we happen to be given the rope length and know the coordinate samples are equidistant along the rope, then we can calculate a maximum change in distance from our target point per sample.
• if we know the rope has a stiffness ensuring it can't loop in a trivially small diameter, then
  • there's a known limit to how fast the slope of the curve can change
  • distance curve converges to vertical on both sides of the 0 point
• you could potentially cross-reference/combine distance with, or use instead, the direction of each point from the target: only at the target would the direction instantly change ~180 degrees (how well the data points capture this still depends on the distance between adjacent samples and any stiffness of the rope).

Otherwise, there's always risk the target point may weirdly be encased by two very distance points, frustrating our whole searching algorithm (that must be what they mean about some margin for error - every now and then this search would have to revert to a O(N) brute-force search because any trend analysis fails).

---

For a one-time search, sometimes linear traversal is the simplest, fastest solution. Maybe that's the case for this problem.

Iterate through the ordered list of points until finding the start or end, and then collect points until hitting the other endpoint.

Now, if we expected to repeat the search, we could build an index to the points.

Edit: This presumes no additional constraints beyond those mentioned by @koool. Constraining the distance between the points would allow the hill-climbing approach described in @Tony's answer.

---

I don't think you can solve it accurately using anything other than exhaustive search. Say for cases where the rope is folded into half and the resulting double rope forms a spiral with the two ends on the centre.

However if we assume that long portions of the rope are in straight line, then we can eliminate a lot of points based on the slope check:

if (abs(slope(x[i],y[i],x[i+1],y[i+1])
        -slope(x[i+1],y[i+1],x[i+2],y[i+2]))<tolerance)
    eliminate (x[i+1],y[i+1]);

This will reduce the search time significantly if large portions of the rope are in straight line. But will be linear WRT number of remaining points.

---

So basically, you've got a sorted list of the points that comprise the entire rope and you're given two arbitrary points from within that list, and tasked with returning the sublist that exists between those two points.

I'm going to make the assumption that the start and end points that are provided are guaranteed to coincide exactly with points within the sorted list (otherwise it introduces a host of issues, particularly if the rope may be arbitrarily thin and passes by the start/end points multiple times).

That means all you're really looking for are the indices of the two provided coordinates. Or the index of one, and the answer to "is the second coordinate to the right or to the left?".

A simple O(n) solution to that would be:

For each index in array
    coord = array[index]
    if (coord == point1)
        startIndex = index
    if (coord == point2) 
        endIndex = index

if (endIndex < startIndex)
    swap(startIndex, endIndex)

return array.sublist(startIndex, endIndex)

Or, if you wanted to optimize for repeated queries, I'd suggest a hashing based approach where you map each cooordinate to its index in the array. Something like:

//build the map (do this once, at init)
map = {}
For each index in array
    coord = array[index]
    map[coord] = index

//find a sublist (do this for each set of start/end points)
startIndex = map[point1]
endIndex = map[point2]

if (endIndex < startIndex)
    swap(startIndex, endIndex)

return array.sublist(startIndex, endIndex)

That's O(n) to build the map, but once it's built you can determine the sublist between any two points in O(1). Assuming an efficient hashmap, of course.

Note that if my assumption doesn't hold, then the same solutions are still usable, provided that as a first step you take the provided start and end points and locate the points in the array that best correspond to each one. As noted, unless you are given some constraints regarding the thickness of the rope then interpolating from an arbitrary coordinate to one that's actually part of the rope can only be guesswork at best.