Daily Challenge Day 23

Following on from yesterday, when looking at the use of linked lists, it became apparent that I could reduce some data storage, and that all I needed to do was make some changes to the next node references. So initially I wrote a swap next node subroutine, then thought about it some more and discarded that idea, and wrote a set node routine instead, and ran that. That was a bad idea.  Some I drew some diagrams and determined that I had cut the list in two, with one part not having a terminating tale, so if unlucky to get stuck in the wrong part of the list then the program failed to stop.

So I needed somewhere to put the missing link reference, and since the tail of the list is easily accessible I thought I could put the reference there, But I could only do that once as I would then loose the tail, so I also needed to set the tail and thus reform the list. There’s a problem with that idea though, as it requires access to a previous node, and I cannot do that without scanning through the list. Since the whole point of deciding to use the linked lists was to reduce the amount of data scanned on each comparison I was making, that wasn’t an acceptable option. So it jumped to my mind that I needed to store the previous node, and that brought to mind doubly linked lists. Since I didn’t have any computer science books at hand at the time, I searched the internet for some background, to check that they are what I thought them to be, and if it was otherwise overkill.  Thinking about it over night, I concluded that maybe I could get away with just using another pointer/counter to track the previous node.

Anycase this morning I decided to skip the lists, and try and get the drawn path out of the ProgeCAD drawing. I thought this would be easy on basis that I am certain written subroutines already. But searching through some 27,000 spreadsheets I couldn’t find what I was looking for. One of the problems with vba hidden inside workbooks, is have to open the workbook, then have limited search capabilities. If I had exported the basic modules then I could Filelocator Pro to seek out the appropriate file. Anyway I was certain that the last time I worked on a sail shade or sports net that I wrote subroutines to extra data from Cadopia intelliCAD 2001 to assist in building the text based data files for input for structural analysis, and not just display the results. So there has to be a file somewhere that I haven’t yet look in.

Not finding the file I wanted I decided to write a new module to extract the lines. That raised other issues, whilst I had previous code available used for extracting block and xref information, I didn’t have any information about entity type codes available. I couldn’t find the information in the help files, so I searched the internet, couldn’t find them there either. The main thing I dug up was my own enquiry about errors in ProgeCAD xref identification, which was kindly fixed at the time. I was about to write a program to scan the entities and list the types and then see If I could identify with the objects in a simple drawing. Then I remembered the object browser and thought I’d see if there was anything relevant in there, and found some constants. So put a series of the codes into a select test, and kept adding codes until all entities in modelspace of my map drawing were identified.

Then I attempted to extract lines from a specific layer, the one with the travel path on it. First attempt had the wrong one, used the layer for the new path I hope to generate rather than the manually drawn path. Fixed the layer still didn’t find any lines. Realised I turned the lines into a polyline to get the travel length. turned out that wasn’t a polyline but a Lightweight Polyline. Fixed that.

In terms of layers I initially attempted to create a layer object to get the layer name, but turned out the entity layer property was a string containing the layer name not a layer object. Once got the layer and the correct type of polyline, I wrote the vertice coordinates to the columns of a worksheet alongside the entity reference. It was a quick check to see how to reference the coordinates. I then modified the code to write the vertex coordinates on a different worksheet as a table with x and y coordinate fields.

Once I had the coordinates the next task was to compare with the coordinates of the towns. To do this I copied the worksheet into that with the list of towns. Sorted the coordinates for the travel path on the y-coordinate and likewise the coordinates for the towns. Then aligned the two lists, 8 towns were missing from the travel path: that was to be expected as there are clusters of towns where it is difficult to see the individual towns. Need to redefine my town marker block so that the attribute text is on a different layer to the marker circle, so that the text can be switched off.

So with the two lists aligned, I metaphorically crossed my fingers and hoped that there no round off difference in the coordinates. I then created conditional tests in the worksheet cells and checked the cell coordinates, identifying where the two lists were out of phase due to the missing towns. Identified the towns missing from the travel path and removed from the list of towns. I then had two aligned lists, with matching coordinates and thus able to match the towns to the travel path.

I then used VLookup functions on my linked list worksheet, to get the new numerical sequence as defined by the vertex numbers of the travel path. Errors in the Vlookup return values once again identified the towns missing from the travel path, these were removed from the linked list. Worksheet cell formula were used to generate cad script to plot a polyline. This column of text commands was then pasted back into ProgeCAD, to generate a travel path over the top of the original free hand travel path. A separate polyline for the missing towns was also generated so that could locate where they were.

The missing towns were then added to the end of the list, and the list sorted on y-coordinate. The node number above the empty cell was then repeated down into the empty cells. The list was then sorted again on node number and the nodes renumbered. The script for the new travel path then copy/pasted to ProgeCAD.

The new travel path contained lines which crossed one another in the town clusters, so manually adjusted the travel path in these areas, by first exploding the polyline. I also switched off the layer with the place marker block, and discovered I had kept the point entities, first inserted as a test. I used these points for snapping, however I still had problems joining the polyline back together and had to edit several other segment endpoints before I could reconnect the line segments. I then ran my subroutine again and grabbed the points back into excel. Though I seem to have lost some towns again, so I haven’t aligned the travel path and town point lists.

I looked at my map drawing and seems may have multiple place markers. A few weeks back when I placed the east/west zigzag path into the map, the path didn’t join the towns and I revised the town place markers. Whilst the other day I scaled all the place markers to make them more readable whilst working in model space, not necessarily on the printout. The worksheet seemingly used for that purpose contains 128 towns, whilst my current file only contains 124. The difference is because the original list contains duplicate towns, I’m not sure if that is because towns were incorrectly allocated to councils in the sources that I used, or some towns are split and in two council areas. Anycase, need to clean up the node list of towns and clean up the drawings, and the raw data I am using, as I have a multitude of files, covering the conversion between simple lists of towns, to kml file generation uploaded to google earth, then kml downloaded with geocoded coordinate data, then modified for import to QGIS, then exported to Australian Map Grid Coordinates and formed into various cad drawings. So need to separate the good stuff from the intermediate experimental rubbish.

So once get a pre-drawn path visiting all the towns, then have a predefined linked list to start work with.  A program can then traverse the path and modify the links, based  on finding a town closer than the one already connected to.

On the other hand I could just get my operations research books refresh my memory on the travelling salesman problem, which from memory can be written as a linear program and solved using the simplex method: though not efficiently. MS Excel in the past could only handle 30 equations in 30 unknowns: not sure if this is still the case. Though some where I have the MS DOS version of LINDO, which came with a numerical methods book I think along with some other application  (possibly dynacode for dynamic programming). I cannot remember but I think the transportation method/algorithm is the more practical way to solve the problem. Though none of this puts the results on a map, which is the objective at the moment.