ThinkGeo.com    |     Documentation    |     Premium Support

Routing Engine Makes U-turns

#1

 We have accidentally  discovered a pretty serious bug in the Routing Algorithm: it makes  U-turns.



 


 

 




The images below are  numbered 1xxx, 2yyy, 3zzz, and 4




 




The intial route  takes a right turn that we delete from the index, as shown if  1DeletedRightTurnSegment.jpg, for the purpose of testing the program.  The route  should avoid this turn, which it originally took.




 




Image 2Route.jpg is  the new route.  Initially we thought we had a bug in the program.  We thought  that the segment had not been deleted, because the route is still taking the  turn.  We also noticed the extra segment in the upper right-hand corner of the  route.




 




We found that:  the segment had indeed been deleted.  The new route went past this  intersection, made a U turn, then a left turn.




 




We tested the assumption by deleting the  left turn for the U-turn segment.  This is shown in  3DeletedLeftTurnSegment.jpg.




 




The last image, 4  Route.jpg shows the new route.  Now there is no left turn on the U turn segment,  so and the route properly follows the rules and goes around.




 




But obviously no U  turns should be allowed. 




 




The problem can  easily be reproduced.




 




Can you tell me if  this bug can be fixed?



 




UTurnRouting.zip (234 KB)

#2

Dear Al, 
  
 Thanks for you attachment, that help me know the questions quickly. 
  
 I have to say, it’s not a bug, because in your first image, you only deleted the opportunity to turn right, but you didn’t delete the chance to turn left in next segment, so it can go to next street and turn back to turn a left. Though it looks wired, but it make sense. 
  
 And in your 3rd images, you deleted the turn left now, if I don’t guess wrong, you didn’t rollback before you do this, so this time the chance to turn right is NONE, and the chance to turn left is NONE, it works fine now. 
  
 So you need delete both of the segment in this situation. 
  
 Any more questions please feel free to let me know. 
  
 Regards, 
  
 Gary

#3

You mean it go to the next street and make a U turn, don’t you?  There is no left turn, there is a U turn.  And it looks weird because it is.  You can deny it is a bug, but if I tried this maneuver I would be guaranteed a ticket, if not an accident. 
  
 Al Vgiil

#4

Dear Al, 
  
 Yes, it make a U-turn, but it happened because the next segment had that. It’s really make sense in logic, isn’t it? 
  
 Regards, 
  
 Gary 


#5

It makes absolutely no sense, logically or otherwise.  In fact it makes the Extension dangerous to use.  The next segment has no restrictions of any kind at this point.  At the end of the street you can turn right, you can turn left.  You can also, according to the routing extension, make a U Turn. 
  


#6

Gary, 
  
 If you think making a U turn is not a bug and makes perfect logical sense, then perhaps you should consider adding a No U Turn restriction to the restriction collection.  Keep in mind that No U turn is different from No Left Turn, for our case. 
  
 Not that I think this is a good idea, as then you would force me to update 26,000 intersections with this restriction.  A better idea would be to disallow U turn in all cases, but allow the ability to over-ride this with a U Turn Allowed permission. 
  
 Without one of these solutions the Extension is of no use to me, as we would become the town laughing stock if we created routes with U turns. 
  
 Al Vigil

#7

Dear Al, 
  
 Sorry for get you in trouble, We will find out a better way to deal with this solution. 
  
 I will answer you ASAP. 
  
 Thanks, 
  
 Gary

#8

Dear Al, 
  
 Because most scenarios people would want U Turns，so we designed the logic like that, however in this case, you don’t want  U Turns unless you specifically designates an intersection to have it, it’s also  a valid scenario. 
  
 But we can’t just change the API easily or very fast, so how about this, I will show some sample code tomorrow to help building the routing index file differently for your scenario, and then we can see if it’s work. 
  
 I appreciated for your patience. 
  
 Regards, 
  
 Gary

#9

100 percent of residential street intersections in the United States do not allow U turns.  Certain highways permit it, but these have special lanes for this purpose.  I do not understand how you conclude that the default case should be to allow U turns. 
  
 I look forward to your suggestion on how to solve my problem, which I suggest to you I share with any developer wanting to use the product in the countries I am familiar with (US, Central and South America, Europe). 
  
 Al Vigil

#10

Dear Al, 
  
 Thanks for the post, in our experience Uturns can be vital to proper routing.  However we recognize there are scenarios where UTurns can’t be used for larger vehicles and special circumstances.  That is why we suggest the solution of building the index to meet your scenario. 
  
 As far as Uturns being illegal in the United States in residential areas we don’t believe this to be the case.  Many in Car GPS units commonly say make a UTurn at the next safe location.  Additionally if you look at the following links they indicate that UTurns are legal in most situations: 
  
 texashighwayman.com/laws.shtml#UTurns 
 dmv.ca.gov/pubs/hdbk/turns.htm  (Scroll to the bottom). 
  
 We will be happy to provide you with the function that will remove UTurns from being present in the route as this can be accomplished when building the index. 
  
 Regards, 
  
 Gary

#11

I stand corrected.  These references do imply U turns are legal in most cases.  I personally would not want to try it, but evidently it is legal in most cases. 
  
 But if there is a sign that says No U Turn, how does one inform the routing index of this fact? 
  
 I hope your suggestion will show me a way.

#12

Dear Al,  
  
 I will try my best to resolve this situation. 
  
 Please give me some time to finish the sample. 
  
 Regards, 
  
 Gary

#13

Gary, Please keep in mind that U turns are not physically possible, in residential neighborhoods, except for motorcycles, since to legally make a U turn you have to get in the left lane, according to the references you sent me.  Most if not all residential streets are not wide enough to allow you to do this without stopping halfway through the turn an putting the car in reverse.  Given that you need 500 feet visibility (according to the Texas reference you sent), it is unlikely that you can complete this maneuver in time. 
  
 But I understand that you cannot easily change the API.  However I still believe that U Turns should be disallowed by the routing engine, unless specifically authorized.  Any solution you provide me should bear this in mind. 
  
 Al Vigil 
  


#14

Dear Al, 
  
 Thanks for your remind, I’m working on the sample and will post it later. 
  
 Regards, 
  
 Gary

#15

Dear Al, 
  
 Thanks for your patience, I’m sorry I didn’t finish the sample as plan, because I meet some problem when I’m working on it, let me confused. 
  
 I’m imagine that there are two scenarios need to take special logic to deal with the U turn problem, one is when you build the index file, another is when you edit the index file. 
  
 So if this guess is right, I need some information for these scenarios. 
  
 1. Did you have any information in your DBF file that could tell us whether the street allow the U-turn? like some columns? 
 2.If you edit a road and delete a right turn, is there a way I can know whether it allow the U-turn? or every operation means NO U-turn? 
  
 If the scenarios I guess is useful for you, I can make both of them, or I can just writhe something helpful. and if I misunderstanding something, please feel free to let me know. 
  
 Regards, 
  
 Gary

#16

This is my preferred scenario, 
  
 1.  U turns are not allowed.  This is the default for all intersections. 
 2.  The edit program allows you to Toggle the U turn restriction for the selected segment. 
  
 As the selected segment has two ends the edit program has to know which end you are editing.  It also needs to display the current status.  
  
 This requires a change in the Index Edit program.  It also requires a change to the Routing Extension, it seems to me, as currently the Routing Extension does not know about U turn restrictions. 
  
 As to your question of whether we have a column we can use in the shp file dbf table, the answer is yes.  However the question then becomes how do you edit the shp file to reflect the U turn status. 
  
 It would be preferable to change the Edit Routing File Index program as otherwise you are now dealing with two edit programs. 
  
 The only way you are going to know if a U turn is allowed or not is by storing this information in the routing file.  Storing it in the shp file forces you to create another editing program, which is more difficult than modifying the present Index edit program.  Why would you want to do this?  Unless the answer is that if the U turn restriction is in the dbf file you avoid having to change the Routing Extension.

#17

Dear Al, 
  
 I don’t need to edit the shp file, only want to know when I will disable the U-turn when I read every segment, but you said U turns is totally NOT allowed, so I only need know one thing is that how can I know which segment can’t turn right? which columns should I read? 
  
 I will show you a sample to how to rebuild the index file with NO u-turn. but I need your help in these details. otherwise, I can only show a idea and some code, and need you to complete the details. 
  
 Regards 
  
 Gary

#18

Currently all turn restrictions are stored in the Routing file Index, so you do not need this information stored in the shp file. 
  
 But since we will be redoing the sample we could easily add a column in the feature table of the shp file to hold No Right Turn data.  But you need two such fields, one to indicate no right turn, the other to indicate the end segment.  The end segment would be referenced to the segment direction. 
  
 To illustrate, say you have a segment, with direction West to East, and there is a No Right Turn restriction on the East end.  Say there is a field in the shp file called NoRight, and another field called NoRightEnd.  Then both of these would be set to a 1 for this segment.  If the restriction is on the West end the fields are set to 1 and 0 respectively. 
  
 But I am now editing the shp file.  It seems to me that all restrictions should be stored in the Routing Index file, as is the case now. 
  
 Keep in mind that I also need the ability to specify UTurn allowed at an intersection.  Are you proposing that this also be stored in the shp file?

#19

Dear Al, 
  
 The work flow is like this: we read the shp file and rebuild all the routing index file, in this progress, we will find out any road with No Right Turn and disable it’s U-turn chance. after this, you get a new routing index file and never worry about the U-turn problem. and we didn’t need to change the shp file, we only need some mark to know this road can’t turn, and now the field is NoRight and NoRightEnd, am I right? 
  
 Anything I misunderstanding please feel free to tell me, 
  
 Regards, 
  
 Gary

#20

I assume that you need some kind of code in the shape file to signal to the Routing Index to create a No U turn restriction.  I prefer to call this a No U Turn code rather than an No Right Turn code.  I assume you will use it to disable U turns, not right turns. 
  
 We can create two such columns in the shape file: NoUTurn and NoUturnEnd, type small int.  These two fields would be coded as follows 1,1 or 1,0, or 1,2, for cases where there is no U turn at the start, end, and both ends.  Most of the segments would be coded 1,2. 
  
 For the cases where a U turn is allowed the segment would be coded 0,1 or 0,0, or 0,2 for the cases where U turn is allowed at the start, end, and both ends. 
  
 Now my part in this is to create an editing program for the shp file.  I this correct?