Community
Participate
Working Groups
Created attachment 106156 [details] Routing result with the orignial algorithm Steps To Reproduce: With anchor having negative direction, you may end up with the wrong point in your routing list. See shape 1 linked iwth 2 and shape 3 linked with 4 in the attached screen shot. Also, if a link pass close to the y or x axis, it wont cross it (see shape 5 linked with shape 6 in the attached screen shot). More information: The problem is that the proper coordinates loose its appropriate sign because of the startDirection or endDirection. I've fixed the problem by keeping rays startOrientation and endOrientation which can only be (0, 1) or (1,0) and I use them with a dotProduct to eliminate the proper part (horizontal or vertical) of obtained ray. Before, this was done using startNormal.similarity, which didn't return the proper signs in all cases.
Created attachment 106157 [details] Routing result with the fixed algorithm
Created attachment 106158 [details] ManhattanConnectionRouter with the fixed algorithm
Hi Melanie, I need a patch to the code in CVS, you have attached the entire ManhattanConnectionRouter so I cannot determine which code you changed.
Hi Anthony, The code I've changed is in the route method. I've used two rays, startDirection and endDirection that are used instead of the similarity method.
Contributions to Eclipse are tracked by an automated intellectual property log. For GEF it's at: http://www.eclipse.org/projects/ip_log.php?projectid=tools.gef So I need a real patch so the system will see the actual lines you are contributing. I also need you to attach the patch since the automation uses your email address for the log.
Created attachment 115822 [details] Patch fixing this bug Here's the real patch. Sorry for the delay, I was in a rush at work and it's my first patch! Hope this helps!
The proposed patch is overly complicated. There are only two simple bugs in the code, which can be fixed with the following patch. 340c340 < if (startNormal.dotProduct(direction) >= 0) --- > if (startNormal.dotProduct(direction) <= 0) 364c364 < if (startNormal.dotProduct(direction) < 0) { --- > if (endNormal.dotProduct(direction) > 0) {
(In reply to comment #7) > The proposed patch is overly complicated. > There are only two simple bugs in the code, which can be fixed with the > following patch. > > 340c340 > < if (startNormal.dotProduct(direction) >= 0) > --- > > if (startNormal.dotProduct(direction) <= 0) > 364c364 > < if (startNormal.dotProduct(direction) < 0) { > --- > > if (endNormal.dotProduct(direction) > 0) { Could you please apply a patch for this?
(In reply to comment #8) > (In reply to comment #7) > > The proposed patch is overly complicated. > > There are only two simple bugs in the code, which can be fixed with the > > following patch. > > > > 340c340 > > < if (startNormal.dotProduct(direction) >= 0) > > --- > > > if (startNormal.dotProduct(direction) <= 0) > > 364c364 > > < if (startNormal.dotProduct(direction) < 0) { > > --- > > > if (endNormal.dotProduct(direction) > 0) { > > Could you please apply a patch for this? Can somebody please apply the simple patch above ?
(In reply to comment #9) > (In reply to comment #8) > > (In reply to comment #7) > > > The proposed patch is overly complicated. > > > There are only two simple bugs in the code, which can be fixed with the > > > following patch. > > > > > > 340c340 > > > < if (startNormal.dotProduct(direction) >= 0) > > > --- > > > > if (startNormal.dotProduct(direction) <= 0) > > > 364c364 > > > < if (startNormal.dotProduct(direction) < 0) { > > > --- > > > > if (endNormal.dotProduct(direction) > 0) { > > > > Could you please apply a patch for this? > > Can somebody please apply the simple patch above ? As already stated within Anthony's earlier comments: Can you please add your patch as an attachment. We can than keep track of your contribution and will schedule it for 3.7.2 (3.7.1 is passed RC3 so it may no go into it any more).
Created attachment 203725 [details] Manhattan Patch Attaching the patch as requested. My version of draw2d is much out of date and I don't have the patience to find how to import the draw2d sources to generate a proper patch. This patch changes exactly two characters in the file to implement the intended design. Please apply the patch.
(In reply to comment #11) > Created attachment 203725 [details] > Manhattan Patch > > Attaching the patch as requested. > My version of draw2d is much out of date and I don't have the patience to find > how to import the draw2d sources to generate a proper patch. > > This patch changes exactly two characters in the file to implement the intended > design. > Please apply the patch. I used the logic example to validate the patch. Indeed it does not seem to be a valid fix, because after having applied the changes you propose, routing seems to be a total mess. As such, we will have to further investigate what the problem is.
I beg to differ. I completely reverse engineered the source and fully understood why the original code produces the behavior. Did you make sure the patch actually changed the correct lines ? Also, perhaps the logic example already has code to work around this 2 year old bug. At this point, fixing this is going to break a lot of workarounds. I would be glad to scan and fax the hand draw sheet I used for all the possible scenarios this algorithm should support, and the correlation with each of the variables and statements used in the source, which helped me identify the intent of the design and source of the bug.
(In reply to comment #13) > I beg to differ. > I completely reverse engineered the source and fully understood why the > original code produces the behavior. That's fine, because I haven't done so yet... > Did you make sure the patch actually changed the correct lines ? Unfortunately the patch is not directly consumable, as it was not created via Team->Create Patch, so I applied the changes manually. But I double checked it again and it seems I have changed the two lines as specified. > Also, perhaps the logic example already has code to work around this 2 year old > bug. At this point, fixing this is going to break a lot of workarounds. I doubt that, as ManhattenConnectionRouter does not seem to have been subclassed in the logic example. Maybe the fix causes another problem that up to now has not shown. > I would be glad to scan and fax the hand draw sheet I used for all the possible > scenarios this algorithm should support, and the correlation with each of the > variables and statements used in the source, which helped me identify the > intent of the design and source of the bug. It would be fine if you could do so. Maybe that could not only help to sort this out, but to enhance the code with some proper comments, so it can be better understood.
I found the paper I used to diagram the situations. The bottom part corresponds to the first section of the algorithm, when start and end normal are colinear. The second part of the algorithm is mapped at the top of the diagram, with the two situations reported in the bug highlighted. In the latest version I could get for the code, it looks like a whole section is missing, with an endNormal replaced with a startNormal. I'll have to search for the version I subclassed to compare. The algorithm works by making a list of intersects for an alternating sequence of horizontal and vertical lines to follow. The maximum number of 'points is 5 since at most 3 lines have to be drawn and 2 offsets may be required. When the direction of travel is opposite the start direction or opposite the endNormal of the anchor, the algorithm uses the normals to add a small offset of 10 pixels. The intermediate values added to the list of intercepts are obtained from midpoints between the start and end. The colinear case looks fine. The non-colinear case is missing a section. The last offset should be added to the endNormal. I'll follow up tomorrow once I find the 'good' code to which the patch applies.
Created attachment 204137 [details] manhattan routing diagram
Created attachment 204811 [details] Current situation - Before patch This was created to show the current defects.
Created attachment 204812 [details] Unit test with patched routing. I used the same unit test after patching the router.
Created attachment 204813 [details] Patch for the router The patch uploaded earlier didn't work, omitting the other error (startNormal vs endNormal) in the original code. This patch works properly.
(In reply to comment #19) > Created attachment 204813 [details] > Patch for the router > > The patch uploaded earlier didn't work, omitting the other error (startNormal > vs endNormal) in the original code. > This patch works properly. Alexander, you were right, the patch I send earlier was flawed as it missed the other error in the code.
Created attachment 204841 [details] 4-bit-adder using the patched Manhattan router Thanks for your effort, Jean-Denis. Unfortunately, the patch does not seem to lead to correct routing results yet. I have applied it to the 4-bit adder logic example, where it leads to quite strange results compared to the current implementation (see attached screenshot). I am not sure if this is a problem with your patch or some side-effect that has been compensated so far, but the results are quite unsatisfying. I fear will have to dig deeper...
(In reply to comment #21) > Created attachment 204841 [details] > 4-bit-adder using the patched Manhattan router > > Thanks for your effort, Jean-Denis. Unfortunately, the patch does not seem to > lead to correct routing results yet. I have applied it to the 4-bit adder logic > example, where it leads to quite strange results compared to the current > implementation (see attached screenshot). I am not sure if this is a problem > with your patch or some side-effect that has been compensated so far, but the > results are quite unsatisfying. I fear will have to dig deeper... Ok, thanks for the screenshot. So I understand what's going on. The original author had added these lines that extend the startNormal and endNormal out of the anchor point so the connections would not arrive directly over the figure at an angle. That's what the normal.similarity(end.getAdded(normal.getscaled()) calls are supposed to do. Also, his original intent was to reach the endNormals at the tip, going around the figure. The bug was making the lines reach them through the figure. The screenshot shows that the normals for the 'end' terminals in the adder point down, and that's why the connections seem to exit the box and connect to the terminal by going outside the adder. I think these terminal input anchors have been reversed to acomodate the bug and should be reversed. If you look at the LED and gates anchors, they are correctly oriented. If you look at the last terminal on the last adder in the bottom right corner, it is definitely showing that its input anchor point in the same direction as the output anchor. At this point I'm not sure what to advocate. If the figures cvs history shows they were modified to acomodate the bug, I would reverse them. Otherwise, maybe the router should be left alone and a new one created. It's all up to you. Thanks . J.D.
Removing target milestone 3.7.2. This will have to be investigated in detail.