**News Alert:**Experts Exchange Confirmed as Safe in Cloudbleed Leak Read More

Solved

Posted on 2004-04-06

Hi,

I am building an application that has some functionality similar to an organisation chart, and I am aiming to be able to move the 'nodes' & lines dynamically.

I'm looking for any references / samples that anyone may know of that relate to the routing of polylines - as you find in visio / MS SQL query desginer.

Drawing the the lines (using VML) and moving them is not a problem, and I have done this. What I need is to be able to update my current routing functions.They are crude, but need to find a better solution, perhaps with collision detection (checking the line does not route over an existing node etc.)

Perhaps some of you have a grasp of some mathematical method that could be employed?

Thanks,

All comments appreciated.

AArnie.

I am building an application that has some functionality similar to an organisation chart, and I am aiming to be able to move the 'nodes' & lines dynamically.

I'm looking for any references / samples that anyone may know of that relate to the routing of polylines - as you find in visio / MS SQL query desginer.

Drawing the the lines (using VML) and moving them is not a problem, and I have done this. What I need is to be able to update my current routing functions.They are crude, but need to find a better solution, perhaps with collision detection (checking the line does not route over an existing node etc.)

Perhaps some of you have a grasp of some mathematical method that could be employed?

Thanks,

All comments appreciated.

AArnie.

6 Comments

line a contains points{(x1,y1),(x2,y2)}

line b contains points{(x3,y3),(x4,y4)}

line a can be denoted as

x=x1+t*(x2-x1)

y=y1+t*(y2-y1)

line b can be denoted as

x=x3+s*(x4-x3)

y=y3+s*(y4-y3)

so logically, if there is a value for t and s that makes both

x1+t*(x2-x1)=x3+s*(x4-x3)

AND

y1+t*(y2-y1)=y3+s*(y4-y3)

given the points x1,x2,y1,y2 {3,4,1,5}

and the points x3,x4,y3,y4 {2,6,1,5}

these lines intersect when t and s=.333

however this is for unbounded lines...

a very easy way to determine if 2 bounded lines intersect is to first find the line with a coordinate closest to y=0. Then find whether or this line (we will call line a) has an y value at the end point <the end point is the lowest ending x value of either line> of line b greater than y value end point of line b.

Sorry if I am not very clear, I understand this stuff but I don't articulate it well.

function DoLinesInterect(line1x1,li

dim line1Lowy,line2lowy

dim lineax1,lineax2,lineay1,li

dim linebx1,linebx2,lineby1,li

if line1y1<line1y2 then

line1lowy=line1y1

else

line1lowy=line1y2

end if

if line2y1<line2y2 then

line2lowy=line2y1

else

line2lowy=line2y2

end if

if line1lowy<line2lowy then

lineax1=line1x1

lineax2=line1x2

lineay1=line1y1

lineay2=line1y2

linebx1=line2x1

linebx2=line2x2

lineby1=line2y1

lineby2=line2y2

else

linebx1=line1x1

linebx2=line1x2

lineby1=line1y1

lineby2=line1y2

lineax1=line2x1

lineax2=line2x2

lineay1=line2y1

lineay2=line2y2

end if

'now lets find the y value for line a when line is at its end point

dim endpointx

dim line1highx,line2highx

if line1x1>line1x2 then

line1highx=line1x1

else

line1highx=line1x2

end if

if line2x1>line2x2 then

line2highx=line2x1

else

line2highx=line2x2

end if

if line2highx>line1highx then

endpointx=line1highx

else

endpointx=line2highx

end if

'now we need the y values for each line at this point

'to do this we will describe the lines in terms of (y)=start y + (deltay/deltax)

dim line1yend

dim line2yend

line1yend=line1y1+( ((line1y2-line1y1)/(line1x

line2yend=line2y1+( ((line2y2-line2y1)/(line2x

if line1yend>line2yend then

DoLinesInterect=true

else

DoLinesInterect=false

end if

end function

'PHEW! I know there is a much more compact way of doing this, I just wanted to keep

'it so the logic was readible

Simply put, you should create an "route ugliness" heuristic function that evaluates how acceptable or ugly a particular route is (how many lines does it cross, how long is it, does it go behind another feature, does it run along the top of another line), and returns a numerical value based on the ugliness. Then you try a bunch of different routes, and use the one that has the smallest ugliness heuristic.

http://www.experts-exchange.com/Programming/Programming_Languages/Dot_Net/Q_20843405.html

Or, you can buy a component (if you're not fixed on implementing it yourself):

http://www.tomsawyer.com/get/get-windows.php (for .NET)

http://www.tomsawyer.com/lav/index.php (for use with Visio)

http://www.sofotex.com/Diagram-Studio-download_L762.html (maybe)

algorithms

Search on: graph layout algorithm

Could you please look at this: http://www.experts-exchange.com/Web/Web_Languages/Q_21284168.html

You may be able to help.

Thanks.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Join the community of 500,000 technology professionals and ask your questions.