How can I determine which one of two segments is lowest on the y axis?

user_10985269 0
Viewed 38

Here's an explanation of what I'm looking to do

I have a list of segments and I need to sort them on the y axis.

Now I don't know if it really is possible with a simple solution because there are many situations in which the segments can be placed.

The image illustrates it but basically, if two walls are intersecting on the y axis, I want to know which one is the lowest between the two. I've tried thinking of the different positions I've tried thinking of the different positions and thinking about how it would work in terms of one of the points being bigger or smaller. However, I feel that there are way too many possibilities and I would easily miss some use cases. Would there be some kind of way to compare two segments and tell which one is lower? Maybe with vector calculation? I'm out of ideas.

I'm using JavaScript and it's array.sort() function with a custom compare function but my question is more of a geometry/math problem.

vector math sorting geometry javascript
1 Answers

I'll assume that the segments are internally ordered by their x-coordinate. I.e., that A1.x is smaller than A2.x. Same goes for B1 and B2. If this is not the case, you can simply swap the two points.

First, find the interval on the x-axis on which the two segments overlap:

xLo = max(A1.x, B1.x)
xHi = min(A2.x, B2.x)

Now we need to find the y-coordinate corresponding to the x-coordinates. For segments that are not parallel to the y-axis, this is pretty straight-forward:

y[A|B](x) = (x - [A|B]1.x) * ([A|B]2.y - [A|B]1.y) / ([A|B]2.x - [A|B]1.x)  + [A|B]1.y

Then simply check

if yA[xLo] < yB[xLo] && yA[xHi] < yB[xHi]
    A is lower than B
else if yA[xLo] > yB[xLo] && yA[xHi] > yB[xHi]
    A is higher than B
else
    the segments intersect

For segments parallel to the y-axis, the check needs to be a bit different. If both are parallel and have the same x-coordinate, simply check if the intervals on the y-axis overlap. If only one segment is parallel, replace the yA[x] < yB[x] check with an interval check (is the interval completely below or above the other y-coordinate).

user_12100530
Related