Solved

I'm looking for samples/references for routing polylines - ie as visio/MSSQL query designer does?

Posted on 2004-04-06
6
383 Views
Last Modified: 2012-05-04
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.

0
Comment
Question by:AArnie
6 Comments
 
LVL 10

Accepted Solution

by:
Kavar earned 168 total points
Comment Utility
using math to determine if 2 lines intersect?

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,line1x2,line1y1,line1y2,line2x1,line2x2,line2y1,line2y2)
dim line1Lowy,line2lowy
dim lineax1,lineax2,lineay1,lineay2
dim linebx1,linebx2,lineby1,lineby2
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)/(line1x2-line1x1)) *endpointx)
line2yend=line2y1+( ((line2y2-line2y1)/(line2x2-line2x1)) *endpointx)
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

0
 
LVL 22

Assisted Solution

by:NovaDenizen
NovaDenizen earned 166 total points
Comment Utility
If you're talking about what I think you're talking about (user moves nodes around, and you want the lines between nodes to adjust accordingly, while satisfying some non-collision requirements and optimizing an aesthetic heuristic) you might want to google PC board layout and routing optimization.  

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.  
0
 
LVL 12

Assisted Solution

by:farsight
farsight earned 166 total points
Comment Utility
See some of the links I posted for this question.  Many apply to you, some do not.
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

 
0
 
LVL 3

Expert Comment

by:hans_larson
Comment Utility
Kavar,

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

You may be able to help.

Thanks.
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

RIA (Rich Internet Application) tools are interactive internet applications which have many of the characteristics of desktop applications. The RIA tools typically deliver output either by the way of a site-specific browser or via browser plug-in. T…
I know it’s not a new topic to discuss and it has lots of online contents already available over the net. But Then I thought it would be useful to this site’s visitors and can have online repository on vim most commonly used commands. This post h…
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

762 members asked questions and received personalized solutions in the past 7 days.

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

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now