CODEWITHSUNDEEP
algorithmgeometry
Izumi Kawashima
Izumi Kawashima

Reputation: 1227

How to detect order of parallel line segments?

Suppose more than two (nearly) line segments are given. How can I calculate the position order of them?

Example:enter image description here

The result I expect from the input

(x_0a,y_0a), (x_0b,y_0b), (x_1a,y_1a), (x_1b,y_1b), ... , (x_4a,y_4a), (x_4b,y_4b)

is

L_0 -> L_4 -> L_2 -> L_1 -> L_3

Upvotes: 1

Views: 162

Answers (2)

MBo
MBo

Reputation: 80325

Choose arbitrary segment end as base point. For example, (x0a, y0a).

Make vector for this segment (normalization is not needed)

v = (x0b,y0b) - (x0a,y0a)

Make perpendicular vector

n = (-v.y, v.x)

Calculate projection value of arbitrary end of every segment on the line, perpendicular to v (this value is the same for both ends of segment)

d(i) = (xia-x0a, yia-y0a)
p(i) = Dot(d(i), n)

Sort p(i)

Upvotes: 5

DAle
DAle

Reputation: 9127

Build linear equation for every segment:

Ai*x + Bi*y + Ci = 0, where  
    Ai = y_ib - y_ia
    Bi = x_ia - x_ib
    Ci = -A * x_ia - B * y_ia

For every equation substitute x with 0, and find y

Bi*y + Ci = 0
y = - Ci / Bi

Then sort segments by the resultant y.

This works when segments are not parallel to the y-axis. If they are parallel to the y-axis, then substitute y with 0, find x, and sort by x.

Upvotes: 1

Related Questions