Geek asks and answers

Search for all elements between the start and end points given by a value (not an index)

The task is as follows:

I would be given a set of x and y coordinates (a coordinate array of about 30-40 thousand) of a long rope. The rope lies on the ground and can be in any form.

Now I will be given the starting point (essentially the x and y coordinate) and the ending point.

What is an effective way to determine the set of x and y coordinates from the above coordinate array lies between the start and end points.

An exhaustive search, i.e. a loop 40k times, is not an acceptable solution (mentioned in the interrogative article)

Allowed value of permissible error is permissible

+3
source share
4 answers

, . , . , , , .

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

"X"... , , , ....

, , , :

  • , , .
  • , , , ,
    • ,
    • 0
  • / : 180 ( ).

, , ( , - O (N) , ).

+4

. , .

, , .

, , .

: , , @koool. , @Tony.

0

, -, . , , , .

, , , , :

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]);

, . WRT .

0

, , , , , .

, ( , / ).

, , , - . , "- ?".

O (n) :

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)

, , , , cooordinate . - :

//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)

O (n) , O (1). , hashmap, .

Please note that if my assumption is not fulfilled, then the same solutions are still suitable for use, provided that as the first step you take the provided start and end points and find the points in the array that best fit each of them. As already noted, if you are not given some restrictions regarding the thickness of the rope, then interpolation from an arbitrary coordinate to that which is actually part of the rope can only be a hunch at best.

0
source

More articles:


All Articles