Algorithms – Detection of Overlapping Between Vectors

algorithms

I am currently developing a math-physics program and I need to calculate if two vectors overlap one another, the one is vertical and the other is horizontral. Is there any fast algorithm to do this because what I came up so far, has a lot of repeats. Eg lets say we have vector V1((0,1),(2,1)) and a V2((1,0),(1,2)) where the first parenthesis is the coordinates starting and the second coordinates that the vector reaches. I want as a result to take that they overlap at (1,1)

So far the only idea I came up is to ''expand'' each vector to a list of points and then compare the lists e.g for V1 its list would be (0,1) (1,1) (2,1)

Best Answer

Terminology nitpick: those aren't vectors: vectors have a direction and size, but there is no “starting point” in a vector space. instead, you're defining a line segment via the starting and ending point of this line segment.

Given these two points A and B on the line, we can calculate the direction D = B - A of the line. The line segment we are interested in consist of all points P that fulfill the following equation:

P = A + k·D,

where k is some scalar value in [0, 1]. When you have transformed all your inputs into this form, it's fairly straightforward to find solutions where the lines overlap:

           P1 = P2
=> A1 + k1·D1 = A2 + k2·D2
=>         0 = (A2 - A1) + (-k1·D1 ) + k2·D2

This is essentially a system of linear equations, which can be solved if we have two or more dimensions. (We have to solve for the two variables k1 and k2). There are three possible outcomes:

no solutions exist (remember also the 0 <= k <= 1 constraint), i.e. the line segments do not overlap.
exactly one solution exists, i.e. the lines touch in one point (e.g. by intersecting each other)
there is an infinite number of solutions. This means that the lines are parallel and lie in each other for more than one point.

Related Solutions

Algorithm for Finding Overlapping Times

Include all the start and end points (in time) of the Jobs in an array (this creates 2*N elements (1 for start 1 for end))
sort the array ordering by the timestamp of the event,

then iterate over the (2*N) elements as follows:

for each element X 
do 
  if(X.type == start)
    counter++
  else
    counter--
  ans=max(ans, counter);
end

Complexity: O(n.log(n)) for initial build of the sorted structure + O(n) for the iteration through its elements.

Edit: It has been suggested by Giorgio that an array is used, which is a better option. (The suggestion originally was to use a red/black tree, but no task removing capability seems to be needed, so maintaining order is trivial).

Algorithm Development – Algorithm for Flattening Overlapping Ranges

Walk from left to right, using a stack to keep track of what color you're on. Instead of a discrete map, use the 10 numbers in your dataset as the break-points.

Starting with an empty stack, and setting start to 0, loop until we reach the end:

If stack is empty:
- Look for the first color starting at or after start, and push it and all lower-ranked colors onto the stack. In your flattened list, mark the beginning of that color.
else (If not empty):
- Find next beginning point for any higher-ranked color at or after start, and find the end of the current color
  - If the next color starts first, push it and anything else on the way to it onto the stack. Update the end of the current color as the beginning of this one, and add the start of this color to the flattened list.
  - If there are none and the current color ends first, set start to the end of this color, pop it off of the stack, and check the next-highest ranked color
    - If start is within the next color's range, add this color to the flattened list, starting at start.
    - If the stack empties, just continue the loop (go back to the first bullet point).

This is a mental run-through given your example data:

# Initial data.
flattened = []
stack = []
start = 0
# Stack is empty.  Look for the next starting point at 0 or later: "b", 0 - Push it and all lower levels onto stack
flattened = [ (b, 0, ?) ]
stack = [ r, b ]
start = 0
# End of "b" is 5.4, next higher-colored start is "g" at 2 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, ?) ]
stack = [ r, b, g ]
start = 2
# End of "g" is 12, next higher-colored start is "y" at 3.5 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, ?) ]
stack = [ r, b, g, y ]
start = 3.5
# End of "y" is 6.7, next higher-colored start is "o" at 6.7 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, ?) ]
stack = [ r, b, g, y, o ]
start = 6.7
# End of "o" is 10, and there is nothing starting at 12 or later in a higher color.  Next off stack, "y", has already ended.  Next off stack, "g", has not ended.  Delimit and continue.
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, ?) ]
stack = [ r, b, g ]
start = 10
# End of "g" is 12, there is nothing starting at 12 or later in a higher color.  Next off stack, "b", is out of range (already ended).  Next off stack, "r", is out of range (not started).  Mark end of current color:
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12) ]
stack = []
start = 12
# Stack is empty.  Look for the next starting point at 12 or later: "r", 12.5 - Push onto stack
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12), (r, 12.5, ?) ]
stack = [ r ]
start = 12
# End of "r" is 13.8, and there is nothing starting at 12 or higher in a higher color.  Mark end and pop off stack.
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12), (r, 12.5, 13.8) ]
stack = []
start = 13.8
# Stack is empty and nothing is past 13.8 - We're done.

Best Answer

Related Solutions

Algorithm for Finding Overlapping Times

Algorithm Development – Algorithm for Flattening Overlapping Ranges

Related Topic