Re: connection routing algorithm for connecting rectangles with lines ? [modified] - Algorithms Discussion Boards

I don't know of any good way to solve it.
The way I do know, you're not going to like.

Branch & bound, where every "step" represents "extending a line in one of 3 directions (except back) by 1 unit" and the "cost" is the number of intersections. Finished when all lines have reached their targets (or when the previous best cost is exceeded, obviously).
It only works if the lines can only change direction on integer coordinates.
Bonus: expand lines in "likely good" directions first (ie. not immediately intersecting, roughly towards their goal)

Pro: it will give the right result.
Con: it will take all eternity to run.

Bonus 2: first estimate an upper bound for the cost this way:
For every pair of things that need to be connected, use A* to find the shortest path among the possible ways to connect them (A* is trivially extended that way - put all starting points on the Open list, test for "done" at all end points). Add extra cost at intersections (since the cost is positive, that will not affect the optimality of A*).
The result will be bad, but it will give a better initial bound at very little cost and thus save time.

It will still take all eternity to run.

Thanks, David, for the response.

I think you are right to (wittily) imply that this problem leads to runaway-recursion ! But I do see a parallel to this problem in algorithms used in the photo-typesetting business that arrange a variable-sized number of page-rectangles in a way that optimizes use of the space in each printing-plate generated, and I think it must be similar to some spreadsheet financial solutions that use multiple recursive "solvers."

Here's my working pseudo-code for a more practical approach:

1. for all the pairs of rectangles-to-be-connected, generate the set of the shortest rectangle-connections.

2. generate the set of intersections of the possible connections, ordered by rectangle-pairs with the highest number of intersections.

3. evaluate the set of intersections for each rectangle-pair with intersections > #someLimit, and then re-evaluate the complete set of connection points, compile the new set of intersections, and see if the number of intersections has increased or decreased: if increased return to the original set, if decreased use the new set of intersections.

4. and so on ...

I notice my eternitys are getting shorter these days.

best, Bill

p.s. Jonathan Swift: "A flea hath fleas that on him prey, and so on 'til infinity."

"In the River of Delights, Panic has not failed me." Jorge Luis Borges

Hm.. is that optimal? It doesn't seem optimal, unless I'm missing something..

Hi,

Yes, it's not optimal: both the hypothetical plan, and the shortening of eternitys Smile | :)

If I clearly knew what was optimal in this case, I would be busy implementing the algorithm, instead of here, humbly seeking your advice, and opinion.

best, Bill

"In the River of Delights, Panic has not failed me." Jorge Luis Borges

For starting, I think you ignore the connection point issue, that's UI, and really a lot of Graph Theory isn't concerned with physical layout. Stick with points Smile | :)

Your issue is intersecting paths/edges.

I used Force-Based positioning for mine...which does seem to reduce the number of overlaps, but this is more by fluke rather than design, as no part of the algo cares about the route of the edge.

But maybe you could use it to get a layout, then find any intersects, and 'shove' the lesser connected node out (randomly). That's a first thought, and there is likely to be better math out there! You'd need to tell the force-based algo that some nodes are fixed, most I've seen don't consider that.

Your going to need some cyclic path checking I think as well, as there will be a relation between the number of cyclic paths and the ability to position the nodes with no overlap, more cycles must decrease that ability.

I've got this edge layout:

C#

public static GraphicsPath StraightPath(Point from, Point to, Rectangle fromRect, Rectangle toRect)
{
    GraphicsPath path = new GraphicsPath();
    //if short distance then just add a return a single line path
    if (PointDistance(from, to) < 40)
    {
        path.AddLine(from, to);
        return path;
    }
    List<Point> outputPoints = new List<Point>(6);
    outputPoints.Add(from);
    List<Point> inputPoints = new List<Point>(6);
    inputPoints.Add(to);
    bool isReversed = from.X > to.X;
    //swivel points to they no longer intersect the two rectangles
    int direction = from.Y >= to.Y ? fromRect.Top : fromRect.Bottom;
    if (LineRectangleIntersection(fromRect, outputPoints[outputPoints.Count - 1], inputPoints[inputPoints.Count - 1]))
        outputPoints.Add(new Point(outputPoints[outputPoints.Count - 1].X, direction));
    direction = from.Y <= to.Y ? toRect.Top : toRect.Bottom;
    if (LineRectangleIntersection(toRect, outputPoints[outputPoints.Count - 1], inputPoints[inputPoints.Count - 1]))
        inputPoints.Add(new Point(inputPoints[inputPoints.Count - 1].X, direction));
    //reverse the input points and add to output points
    inputPoints.Reverse();
    outputPoints.AddRange(inputPoints);
    path.AddLines(outputPoints.ToArray());
    return path;
}
public static bool LineRectangleIntersection(Rectangle rect, Point p1, Point p2)
{
    //top
    if (LineSegmentIntersection(p1, p2, new Point(rect.Left, rect.Top), new Point(rect.Right, rect.Top)))
    {
        return true;
    }
    //bottom
    if (LineSegmentIntersection(p1, p2, new Point(rect.Left, rect.Bottom), new Point(rect.Right, rect.Bottom)))
    {
        return true;
    }
    //left
    if (LineSegmentIntersection(p1, p2, new Point(rect.Left, rect.Top), new Point(rect.Left, rect.Bottom)))
    {
        return true;
    }
    //right
    if (LineSegmentIntersection(p1, p2, new Point(rect.Right, rect.Top), new Point(rect.Right, rect.Bottom)))
    {
        return true;
    }
    // no intersection
    return false;
}
internal static bool LineSegmentIntersection(
    float Ax, float Ay,
    float Bx, float By,
    float Cx, float Cy,
    float Dx, float Dy)
{
    float distAB, theCos, theSin, newX, ABpos;
    //  Fail if either line segment is zero-length.
    if (Ax == Bx && Ay == By || Cx == Dx && Cy == Dy)
        return false;
    //  (1) Translate the system so that point A is on the origin.
    Bx -= Ax;
    By -= Ay;
    Cx -= Ax;
    Cy -= Ay;
    Dx -= Ax;
    Dy -= Ay;
    //  Discover the length of segment A-B.
    distAB = (float) Math.Sqrt(Bx * Bx + By * By);
    //  (2) Rotate the system so that point B is on the positive X axis.
    theCos = Bx / distAB;
    theSin = By / distAB;
    newX = Cx * theCos + Cy * theSin;
    Cy = Cy * theCos - Cx * theSin;
    Cx = newX;
    newX = Dx * theCos + Dy * theSin;
    Dy = Dy * theCos - Dx * theSin;
    Dx = newX;
    //  Fail if segment C-D doesn't cross line A-B.
    if (Cy < 0f && Dy < 0f || Cy >= 0f && Dy >= 0f)
        return false;
    //  (3) Discover the position of the intersection point along line A-B.
    ABpos = Dx + (Cx - Dx) * Dy / (Dy - Cy);
    //  Fail if segment C-D crosses line A-B outside of segment A-B.
    if (ABpos < 0f || ABpos > distAB)
        return false;
    //  Success.
    return true;
}

Which for a single node pair and edge will draw the edge without touching either node...it basically juts to outside the bounds of each node then a direct line. Looks nice though.

Forgot to say, I was thinking more of laying out the rectangles so that overlapping edges don't occur...you could just layout the rects any old way, and route the edges using something like an A* algo. But you could end up with very long windy edges...that's one issue I've got at the mo.

Thanks, CJB110, for your response ! I am going to study your code and think about it for a few days, and I am sure it will help me refine the strategy to pursue.

best, Bill

"In the River of Delights, Panic has not failed me." Jorge Luis Borges

Bill,

I have some questions about this problem.

BillWoodruff wrote:
3. List set of rectangle pairs => all in rectangle array 'ra, which need to be 'connected' by 1-3 line segments.

What determines whether you have 1, 2, or 3 line segments for a rectangle pair?

Do the connections have to be made from top to top, left to left, or just in any order between the rectangle pairs, and can a point on one rectangle of the pair connect to more than one point on the other rectangle of the pair?

BillWoodruff wrote:
Simplest case would be a straight line: two points; then three points for a path with one right-angle turn; and, finally four points for a path with two right-angle turns.

What do you mean "a straight line" ... "for a path with xxx right-angle turns"?

BillWoodruff wrote:
Where: intersections of lines are minimized.

I am assuming that the lines are the rectangle pair connection lines from all of the pairs in the set.

Dave.

bw: "set of rectangle pairs => all in rectangle array 'ra, which need to be 'connected' by 1-3 line segments.">

Dave: "What determines whether you have 1, 2, or 3 line segments for a rectangle pair?"

Their position:

1. two rectangles of the same size that share either a common left, or top, can be connected with one line.

2. two rectangles, not the same size, if they share a common horizontal center, or vertical center, can be connected with one line.

3. two rectangles of same size, or variant size, which do not overlap each others bounds in such a way that two lines cannot join a center-point to the other rectangle's center-point, and that do not meet conditions 1,2 can be connected by two lines, with one 90 degree 'joint.'

4. the necessity for three lines is perhaps best expressed by an example: imagine you have r1 { 200, 200, 200, 200 } and r2 { 275, 500, 200, 200 }:

a. the shortest possible connecting line from the mid-point of the bottom of r1 to the mid-point of the top of r2 will take three lines (four points) to achieve with two 90 degree turns.

b. but, you may say, what about going from the right center-point of r1 and just drawing a first line out perpendicular to the r1's right, and then a line down so it falls on top of r2's right side. Nope, that's out, no overlapping like that allowed.

Dave: "Do the connections have to be made from top to top, left to left, or just in any order between the rectangle pairs, and can a point on one rectangle of the pair connect to more than one point on the other rectangle of the pair?"

1. No two rectangles can be connected by more than one line between them, but every rectangle can be connected to all other rectangles it has not already connected to.

2. all connection lines must originate from a mid-point on left, top, bottom, or right sides, and connect to a mid-point on the other rectangle's left, top, bottom, sides. Corners are out.

bw: "Simplest case would be a straight line: two points; then three points for a path with one right-angle turn; and, finally four points for a path with two right-angle turns."

Dave: "What do you mean "a straight line" ... 'for a path with xxx right-angle turns'?"

I mean that each line-segment of a connection can only be along a line parallel with either the horizontal or vertical axis of the graphics space, so segments can only be joined by a 90 degree rotation. Two points = straight line. Three points = two lines one of which will be at right-angles to the other. Four points = three lines, two of which will be at right-angles to each other.

bw: "Where: intersections of lines are minimized."

Dave: "I am assuming that the lines are the rectangle pair connection lines from all of the pairs in the set."

The 'set of connecting lines' I think of as a collection; each element of the collection contains 2-4 points that map to 1-3 line-segments, and some identifying information to be determined. Something like this:

XML

// will compile .NET 4.0 Client
// rough sketch for Line 'primitive'
Public class ConnectingLine
{
   public Rectangle sourceRectangle { get; set; }
   public Rectangle sinkRectangle { get; set; }
   public List<Point> cPoints { get; set; }
}

// will compile .NET 4.0 Client
// rough sketch for Line Manager Class
public static class ConnectingLines
{
   // Line Collection
   static internal List<ConnectingLine> ConnectingLineList = new List<ConnectingLine>();

   // using automatic property initializers
   public static void Add(Rectangle r1, Rectangle r2, List<Point> lPts)
   {
     ConnectingLineList.Add(new ConnectingLine
     {
       sourceRectangle = r1, sinkRectangle = r2, cPoints = lPts
     });
   }
}

// 'hard-coded' simulation of a call to add a new connection ...
// case where a connection requires 4 points that define 3 lines
// stick this in a method and call it
// will compile .NET 4.0 Client. Execute in a method body and inspect results
  ConnectingLines.Add
  (
      new Rectangle (200, 200, 200, 200),
      new Rectangle (275, 500, 200, 200),
      new List<Point> {new Point (300,400), new Point(300,450), new Point(375, 450), new Point(375,500)}
  );

In the 'solution' there would be, of course, some 'engine' analyzing the Rectangles selected to be joined, and generating the appropriate calls to ConnectingLines.Add.

Whether that 'connection engine' would make a first pass to figure out the shortest possible connection for each pair of connected rectangles, and then iterate over the complete result of the first pass, to try and identify the maximum number of overlapping connections, and then try to reduce them ... or, whether the engine would, as it created each new connection, then 'backtrack' over all the previous connections and perhaps make change them, and then compute a different choice for the current connection ... well, that's beyond my 'computer science' capacity Smile | :)

Many thanks for your detailed response !

best, Bill

"In the River of Delights, Panic has not failed me." Jorge Luis Borges

modified on Sunday, August 7, 2011 8:48 PM

Bill,

Thank you for the detailed reply.

Comes the dawn! Multi-layer circuit board design.

Dave.

Bill,

As Columbo would say "just one more thing".

BillWoodruff wrote:
1. No two rectangles can be connected by more than one line between them, but every rectangle can be connected to all other rectangles it has not already connected to.

Can one rectangle connect to more than 4 other rectangles? If so, then there can be more than one connection at any mid-point, correct?

Are there any data sets to play around with that define the bounding box, the rectangles, and the connect-to list of rectangle pairs?

And, circuit board is massively too big, you are talking about chip design, right?

Dave.

Hi Dave,

Dave: Can one rectangle connect to more than 4 other rectangles? If so, then there can be more than one connection at any mid-point, correct?

Yes, a given rectangle, could have many other rectangles connecting to any of its sides mid-points.

Dave: Are there any data sets to play around with that define the bounding box, the rectangles, and the connect-to list of rectangle pairs?

For right now, I'm assuming the following conditions, in addition to the ones I've described previously:

1. the bounding box of the container in which all rectangles are shown is known.

2. the location of each rectangle is known within the container.

3. the connections are made visually, at run-time, by the end-user. Of course they can be saved as a set, and saved sets can be loaded in: a set loaded in can have its connections added to connections already made after, perhaps, being filtered to exclude duplicates

Dave: And, circuit board is massively too big, you are talking about chip design, right?

No, this has nothing to do with hardware, it's more in the area of wanting to show complex interconnections between multiple hierarchical data sets. A form of "meta-cataloging," if you will. But I ... instinctively ... feel that the same issues must arise in printed circuit-board design, and algorithms that create mazes, etc.

Again, thanks for your time, and response. I am going to "take my head out of this problem-space for a few days" (no deadline pending here), and think about the points you and CJB110 have raised.

best, Bill

"In the River of Delights, Panic has not failed me." Jorge Luis Borges

Bill,

"just one more thing". A connection between two rectangles has 1, 2, or 3 segments with right angle turns. This I understand. I also understand that the connections must be made to and from a midpoint on a rectangle edge. Is there also a restriction that the pathway between the two rectangles must be open, i.e. that there can not be another rectangle that blocks the way (you cannot zig zag around the obstacle with a limitation of two right turns in the path)? Or, can the connections be determined solely on the basis of the two rectangles themselves and the chosen path (segmented or not), disregarding all other rectangles for the moment (maybe hyper-space connections). This is not too far fetched. I have envisioned a computer architecture in the form of a silo, where the CPUs and IO controllers communicate via IR signals (no front or back bus, just the ether), and all of the MMUs examine the request and all ignore the request except the MMU holding the address, and the returned data is sent back by the same method, and all CPUs and IO controllers examine all memory data and all ignore the returned data except the requester.

Another thing. Consider a neat layout of rows and columns for the rectangles. It appears that with the connection specifications as stated, a center rectangle can potentially connect to ANY other rectangle in its row or column or connect to ANY other rectangle in the rows or columns adjacent to its row or column, (3 possible paths for the four immediately horizontally or vertically adjacent rectangles, 2 paths for other rectangles in the same row or column, only 1 path for rectangles in adjacent rows or columns), and that there are no other possible connections for that center rectangle. Is this correct?

Dave.

Hi, Member 4194593,

Thanks for your response !

Yes, the stipulation of a maximum three line segments (four points) is based on the assumption that all the rectangles will be in front of all lines in the z-order, so that a line can pass through the bounds of any other rectangle.

Your idea for a 'silo' computer architecture is interesting, but beyond my "depth" to envision.

Yes, there is a kind of a grid inherent here in that these lines connect nodes in hierarchies together: from node to node within one hierarchy, and/or from node to node 'across' hierarchies. So connecting lines are not limited to 'neighbors' in the same x,y cell of the 'virtual grid.'

Since the visual presentation of these hierarchies will be in TreeView form, then indent order visibly reflects 'inheritance' in the hierarchy, and above-below order reflects 'depth,' and 'ordinal position' in relation to sibling nodes.

However, there may be no fundamental relationship between the #n hierarchies currently displayed. A node at a nesting level of #3 in hierarchy #1 may be completely unrelated to the fact there are nodes in another hierarchy with depth of level #3 ... or, that could be meaningful.

Creating and inspecting these 'connections' between 'nodes' will be facilitated by using some graphic techniques: imagine something like you alt-click on a 'node's display rectangle, and all the displayed rectangles for nodes in all hierarchies that have no 'connection' ... direct or indirect ... to the node you selected become 50% transparent.

Or, imagine a use of one color to indicate 'connections' made by the user directly, and another color used for lines which connect indirectly to the selected node's rectangle representation.

While a 'connection line' is defined as an object of #n:1~3 segments, or #2~4 points, it is, architecturally a data structure inside the 'connection object.'

If you think of the total connection objects per one node of a hierarchy, then you can also think of a set of all possible paths from this node to other nodes: that set, the 'path' object, may be organized based on multiple criteria: for example: sequence in time: the user connected node a to node b then to node c one after the other.

But, no, this is not a scenario where a combinatorial 'explosion' of potential 'routes' will be computed, or, like the infamous 'travelling salesman' problem a case where the shortest route will need to be solved based on passing through a required subset of connected nodes.

best, Bill

"In the River of Delights, Panic has not failed me." Jorge Luis Borges

Ray trace image[^]
As you can see by the image there are considerable artifacts in the render output. I have no idea where to start with this issue. I can post code on request. This is a standard Raytracing model of shooting rays from the camera.
Does anybody know how to fix artifacts like this? (The lines between the triangles even though they touch)

Made in VS2010 c# using a picture box and one image I made in Photoshop

Thank you all Smile | :)

[edit]algorithm posted[/edit]
Here is the algorithm I am using. A lot of extra features removed for simplicity. But this is its core.

C#

for (int X = 0; X < Width; X++)
{
    for (int Y = 0; Y < Height; Y++)
    {
        Ray TRay = new Ray(V3.Zero(), V3.Normalize(new V3(X - HalfWidth, 20f, Y - HalfHeight)));
        foreach (Triangle TempTriangle in SceneTriangles)
        {
            Intersection TInter = TempTriangle.Intersects(TRay);
            if (TInter.Hits) Temp.SetPixel(X, Y, CalculateColour(TInter, ColourMode.Lambert));
        }
    }
}

A ray is defined as a start point and a direction
V3 is a 3D vector
Intersection stores: V3 of impact, If it hit, colour of pixel on triangle

Thomas Williams - Chimp Twist

modified on Monday, August 1, 2011 5:33 AM

This is the Algorithms forum, please select a forum more appropriate to your subject.

The best things in life are not things.

It is an algorithm question. I didn't post code to bog down. See Edit. There is an error somewhere in the process I am using to work out each colour of the pixel on the screen.
Which other forum would it belong in? I figured this would be the best place

Thomas Williams - Chimp Twist

I don't think it's so much the fault of the algorithm as it is of the implementation of the hit test. It appears to be "too narrow".

I've had a go at moving through the pixels in half steps. This hasn't worked, but:
I am going to have a go at getting the average colour of the pixel between the half steps in an attempt to do some anti-aliasing Smile | :)

Thomas Williams - Chimp Twist

Hi Everyone,

I'm working on a 128 bit unsigned integer class (due to Numerics.BigInt being too slow). I've gotten most of the regular arithmetic functions working, but now I'm on the Modulo one. Does anyone know of shortcuts to finding the remainder without having to go through the full division? (Yes, I have googled this for several days, with little progress)

So far the only one I've found is if the divisor is a power of 2, you can use

C#

Remainder = Dividend & (Divisor - 1);

But that's it. Nothing for any other number. So if anyone knows of anything similar, or heck, just a really fast division/mod algorithm, please let me know.

Thanks,
John

I'm not sure this will help in your case, but it seems that eons ago I saw an algorithm that basically repeatedly bit shifted and subtracted in binary. Perhaps the Mongomery algorithm[^] would suit your purpose?

CQ de W5ALT

Walt Fair, Jr., P. E.
Comport Computing
Specializing in Technical Engineering Software

This looks interesting. It seems like it could be it. The only problem I can see with it is that it seems to be just for working with primes and semiprimes? Can I use this with any positive integer?

Thanks,
John

I really don't know. Sorry about that.

CQ de W5ALT

Walt Fair, Jr., P. E.
Comport Computing
Specializing in Technical Engineering Software

128 bits isn't "really big", so the asymptotically optimal algorithms aren't a very good choice here.
For 128 bits, I think what would work best is a simple multiword division. There's lots of stuff on google, it's in one of Knuth's books, and hackers delight has some code here[^] that also explains the algorithm.
edit: yes that does a division, and you go to mod from there - I know of no general way to do a mod without a division.

Just wondering, how did you implement multiplication? I hope it's not shifts and adds.. it works, to be fair, but it's very much slower than using long multiplication in base 2^32 (or base 2^64 if you have access to a 64x64->128 multiplication)

Hi,

i have created one portable application,initially it will take several time to install on to pendrive(installer doing more on dll copy option), for that i want to show time remaining in my UI.
can any one suggest me best algorithm to do this please

If you know how much data you need to install then you can set a timer to measure your install speed and use that value to estimate how much time the remainder will take. Adjust the value as you go through the install. Something like:
Total to install 1Mb
After installing 100Kb time taken is 2 seconds, so time left is ((1000 - 100) / 100 * 2) = 18 seconds
After installing 200Kb time taken is 3 seconds, so time left is ((1000 - 200 / 200 * 3) = 12
etc.

The best things in life are not things.