Drawing lines

[joonas]

Anyone got any good input on how to implement an algorithm like this:

* Draw a line between two points - I suppose click the mouse on two points.

So far so good.

Then:

* Click two new points and draw a line between those two points. DO NOT let the lines cross. - here I guess I must make a polyline to avoid crossing the existing line.

Any input is very much appreciated :)

[cilu]

I suppose you must check if the second segment intersects the first segment.

The first step is to get the math equations (y = mx + b) of the two lines (on which the two segmet resides). It's very easy because you have 2 points for each line.

Then resolve the system of the two equations and get the intersection line.

Once you have the intersection point (X, Y) it's easy to see if it belongs or not to a segment. The X and Y coordinates of the point must be in the intervals [X1, X2] and [Y1, Y2], where (X1, Y1) and (X2, Y2) are the delimiting points of the segment.

[joonas]

Yes but it doesn't help me as I have to draw the d*mn line :)

But I figured as much the problem is a shortest-path problem. And the lines already drawn are the walls.

thanks anyway :)

Jonas

[RoboTact]

I suppose you must check if the second segment intersects the first segment.

The first step is to get the math equations (y = mx + b) of the two lines (on which the two segmet resides). It's very easy because you have 2 points for each line.

Then resolve the system of the two equations and get the intersection line.

Once you have the intersection point (X, Y) it's easy to see if it belongs or not to a segment. The X and Y coordinates of the point must be in the intervals [X1, X2] and [Y1, Y2], where (X1, Y1) and (X2, Y2) are the delimiting points of the segment.Simplier test on intersection: segments intersect iff ends of each segment are on different sides of other segment's line. This can be tested using cross product. Say, first segment is (a1,b1), second is (a2,b2) (a1, etc. are points). Then first test is if a1 and b1 are on different sides of line defined by (a2,b2). It's so if sign((a2-a1)*(b2-a1))!=sign((a2-b1)*(b2-b1)), where * is cross product, sign(z) takes z-component of (3D) vertor.

[mehdi62b]

in its general way,in a 3D cordiantes system,firstly we can check the lenght of the common right line(the line which has the shortest distance between two lines),if its zero,that means they are in one page

L1=[a1,b1]
L2=[a2,b2]

L=L1*L2 (the extension of the common right line, * is cross product)

lenght=|(a1-a2) . L| / |L| ( . is dot product)

if lenght=0 then the both lines are in a one page and we can check,
sign((a2-a1)*(b2-a1))!=sign((a2-b1)*(b2-b1)).