MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

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

Title | # Comments | Views | Activity |
---|---|---|---|

how to use laptop or pad camera in vb.net windows application | 2 | 86 | |

VbScript to countdown to New Year's Day | 6 | 65 | |

How to get time difference in minutes and seconds only between 2 dates | 2 | 46 | |

Output in PHP throwing alignment of data off issue | 12 | 43 |

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