I have a master line segment, against which I am comparing 64 other child line segments. I have other criteria and have filtered out most of the child line segments (I have maybe 10 left).

I now need to find the longest child segment on each side of the master line segment. I can't just take the two longest child segments overall, because they might both be on the same side of the master segment.

To further confuse matters, all line segments can have virtually any orientation, including perfectly vertical or horizontal, or anywhere between.

Is there a reliable way to determine which 'side'of the master line segment each child segment is located? I'd especially appreciate answers suggested in the format of an equation that I can convert directly into code.

My first thought was to just add up the x and y coordinates of both endpoints of the child line and compare to the parent line, and determine which is larger... but I can envision situations where those totals for the two lines could be the same... so maybe simple addition isn't the way to go.

Any help is greatly appreciated!


Your master line segment $[AB]$ lies on a line $D$. First we find the equation of that line. Let $(a,a')$ be the coordinates of A and $(b,b')$ of B.

$$(b'-a')x+ (a-b)y + (a'-b')a + (b-a)a' = 0$$ is an equation of $D$. [ask if you need a proof for that]

Given a point $(x,y)$, you can substitute $x$ and $y$ in the equation above, and if you get a positive, you're on one side of $D$, if given a negative you're on the other side. If you have 0, guess what ? You're on the line !

For each segment, you find the side of both its endpoints. If they coincide, you've found the side of the segment, if they don't, then the segment crosses the D line, which is a case you've not talked about in your question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.