TSP art generator

[Gianni]

After reading this page, (http://www.drububu.com/illustration/tsp/index.html) I was curious and I put together this script.
it is not a "stand alone" script, as it uses some third parties programs*, but in few steps it acomplish the conversion to the TSP art. The generated images are quite nice, but you have to try more attempts to find the right combinations of parameters for different source images. Best results can easily obtained with schematic black and wite images. Drag and drop for example something like in this link.
Also, set the "Variable thickness line" option and try with the image at this link for another example: (https://images.fineartamerica.com/images/artworkimages/mediumlarge/1/david-michelangelo-murphy-elliott.jpg)
Since used programs generate also some temporay files, please save this script and the dependencies into a single folder so to avoid the scattering of files around and also allowing the main script to find the needed programs.

Example of an TSP art generated with this script and related programs (the image on the left is converted in the image on the right) just drag and drop images on the GUI of the script and all is done automatically.

* Here are the links to download the needed "dependencies": ( just put all the stuff in a single folder along with the script.)

voronoi.exe     http://www.drububu.com/illustration/tsp/voronoi.zip
stippler.dll    also contained in the above archive

concorde.exe    http://www.math.uwaterloo.ca/tsp/concorde/downloads/codes/cygwin/concorde.exe.gz
                this program needs the cygwin dll (a very nice one)
                (I've used 7zip to open this archive)

cygwin1.dll     https://cygwin.com/snapshots/
                get one x86 cygwin1-xxxxxxxx.dll.xz (only dll)

svg_extract.exe http://www.drububu.com/illustration/tsp/svg_extract.zip
tsp2svg.exe     http://www.drububu.com/illustration/tsp/tsp2svg.zip

here the script:

expandcollapse popup

; TSP Art generator
#include <FileConstants.au3>
#include <WinAPISys.au3>
#include <GUIConstantsEx.au3>
#include <WindowsConstants.au3>
#include <GuiEdit.au3>
#include <GDIPlus.au3>

If Not _CheckDependencies() Then Exit ; can't run without dependencies.
Global $bDropped, $sFile, $bDropAllowed = True

; create a blank file, or empty it if it's already created
Global $hTail, $sLogFile = FileGetShortName(@ScriptDir & "\LogFile.txt")

_GDIPlus_Startup() ; just for image format conversion to PNG (if needed)

$Form1 = GUICreate("TSP art generator", 500, 650, -1, -1, -1, $WS_EX_ACCEPTFILES)

; --- options
$Combo1 = GUICtrlCreateCombo("", 350, 505, 60, 25)
GUICtrlCreateLabel("Sampling points", 415, 510, 80, 25)
GUICtrlSetData($Combo1, "1000|2000|4000|6000|8000|10000|20000|40000|60000", "4000") ; some sampling rate
$Checkbox1 = GUICtrlCreateCheckbox("Variable thickness line", 350, 535, 145, 25)
$Checkbox2 = GUICtrlCreateCheckbox("Color (voronoi only)", 350, 565, 145, 25)

; --- Log viewer
Global $hLog = GUICtrlCreateEdit("", 5, 500, 340, 145, BitOR($WS_VSCROLL, $WS_HSCROLL, $ES_AUTOVSCROLL, $ES_AUTOHSCROLL, $ES_MULTILINE, $ES_READONLY)) ; log viewer
GUICtrlSetBkColor(-1, 0x000000)
GUICtrlSetColor(-1, 0x00FF00)
GUICtrlSetFont(-1, 9, -1, -1, "Courier New")


; following is a transparent control over the browser control
; purpose is to avoid that the drop event is captured by the browser control
$hGlass = GUICtrlCreateLabel("", 0, 0, 500, 650)
GUICtrlSetBkColor(-1, $GUI_BKCOLOR_TRANSPARENT) ; This is like a glass over the following underlying browser Control
GUICtrlSetCursor(-1, 2) ; Cursor is an arrow (instead of the default I-beam)

; --- Embed a browser control
Global $oIE = ObjCreate("Shell.Explorer.2")
$hIE = GUICtrlCreateObj($oIE, 5, 5, 490, 490)
$oIE.navigate("about:blank")

AutoItSetOption("GUIOnEventMode", 1)
GUISetOnEvent($GUI_EVENT_CLOSE, "_Exit")
GUIRegisterMsg($WM_DROPFILES, "WM_DROPFILES")
GUISetState(@SW_SHOW, $Form1)

_LogPrint(@CRLF & _
        "Hello," & @CRLF & _
        "Drag and dropping images here above," & @CRLF & _
        "will be converted into a TSP Art." & @CRLF & _
        "have fun...")

; --- Main loop
While 1
    $nMsg = GUIGetMsg()
    Select
        Case $nMsg = $GUI_EVENT_CLOSE
            _Exit()
        Case $bDropped = True
            $bDropped = False
            $bDropAllowed = False ; Drop not allowed while generating
            _Generate_PST_Art()
            $bDropAllowed = True
    EndSelect
WEnd

; --- Call externa programs the right sequence
Func _Generate_PST_Art()

    _EmptyLog() ; empty the temporary log file
    _checkFileFormat($sFile) ; if dropped image isn't a PNG convert it to PNG
    _ShowInBrowser($sFile) ; show dropped image in the browser control

    ; step 1) Transform PNG image into a voronoi svg image
    ; ============================================================================
    If GUICtrlRead($Checkbox1) = $GUI_CHECKED Then ; variable thickness line?
        $sOptions = ""
    Else
        $sOptions = " -f " ; fixed radus
    EndIf

    If GUICtrlRead($Checkbox2) = $GUI_CHECKED Then ; color points for voronoi?
        $sOptions = " -c " & $sOptions
    EndIf
    ; _call_External_Program(".\voronoi.exe " & $sOptions & "-s " & GUICtrlRead($Combo1) & " -n -I " & $sFile & " -O out.svg", True)
    _call_External_Program(FileGetShortName(@ScriptDir & '\voronoi.exe') & $sOptions & ' -s ' & GUICtrlRead($Combo1) & ' -n -I ' & $sFile & ' -O out.svg', True)

    _ShowInBrowser(FileGetShortName(@ScriptDir & "\out.svg")) ; show generated voronoi image in the browser control
    ;
    ; step 2) Extract points from the voronoi svg image and save to positions.tsp file
    ; for later input by the concorde TSP solver
    ; ============================================================================
    _call_External_Program(FileGetShortName(@ScriptDir & '\svg_extract.exe') & " out.svg")
    _LogPrint("... going to next step ...")
    ;
    ; step 3) Resolve the Traveling Salesman Problem using the very good
    ; concorde.exe program (it needs the presence of the cygwin1.dll to work)
    ; ============================================================================
    _call_External_Program(FileGetShortName(@ScriptDir & "\concorde.exe") & " -V -o tour.cyc positions.tsp", True)
    _LogPrint("... going to next step ...")
    ;
    ; step 3a) some adjustments to the tour.cyc file generated by concorde.exe
    ; ============================================================================
    $hfile = FileOpen(FileGetShortName(@ScriptDir & '\tour.cyc'))
    Local $sContent = FileRead($hfile)
    FileClose($hfile)
    FileDelete(FileGetShortName(@ScriptDir & '\tour.cyc'))
    $sContent = StringReplace($sContent, Chr(0x20), Chr(0x0A))
    _LogPrint("Replaced 0x20 with 0x0A " & @extended & " times.")
    $sContent = StringReplace($sContent, Chr(0x0A) & Chr(0x0A), Chr(0x0A))
    _LogPrint("Replaced 0x0A 0x0A with 0x0A " & @extended & " times." & @CRLF)
    Local $x = StringInStr($sContent, Chr(0x0A)) ; first 0A
    $sContent = StringMid($sContent, $x + 1) ; remove first data (it's the number of points, not a point)
    $hfile = FileOpen(FileGetShortName(@ScriptDir & '\tour.cyc'), $FO_OVERWRITE + $FO_BINARY)
    FileWrite($hfile, $sContent) ; save adjusted data
    FileFlush($hfile)
    FileClose($hfile)
    ;
    ; step 4) "merge" data from out.svg and tour.cyc into the final tsp_art.svg file
    ; ============================================================================
    If GUICtrlRead($Checkbox1) = $GUI_CHECKED Then
        $sOptions = " +w" ; variable thickness line
    Else
        $sOptions = "" ; fixed thickness line
    EndIf
    $sOptions = FileGetShortName(@ScriptDir & "\tsp2svg.exe") & " out.svg tour.cyc" & $sOptions
    _call_External_Program($sOptions)
    _ShowInBrowser(FileGetShortName(@ScriptDir & "\tsp_art.svg"))

    _LogPrint(@CRLF & _
            "+-----------------------------------+" & @CRLF & _
            "| End of conversion --> tsp_art.svg |" & @CRLF & _
            "+-----------------------------------+" & @CRLF)

EndFunc   ;==>_Generate_PST_Art

; === Functions

Func _call_External_Program($sCommand, $bVerbose = False)

    Local $sLine

    If $bVerbose = True Then
        $sCommand = @ComSpec & " /c " & $sCommand & ">>" & $sLogFile & " 2>>&1"
    EndIf

    Local $hPid = Run($sCommand, ".", @SW_HIDE)

    If Not $hPid Then
        _LogPrint("Error on run external program" & @CRLF)
        Return SetError(1)
    EndIf

    Do
        If $bVerbose Then
            $sLine = FileReadLine($hTail)
            If Not @error Then
                _LogPrint($sLine)
            EndIf
        EndIf

    Until Not ProcessExists($hPid)

    If $bVerbose Then
        $sLine = "..." ; "Task execution terminated ...."
        Do
            _LogPrint($sLine)
            $sLine = FileReadLine($hTail)
        Until @error
    EndIf
EndFunc   ;==>_call_External_Program

Func _LogPrint($sLine)
    If StringLen(GUICtrlRead($hLog)) > 25000 Then ; Max Len of a CtrlBox is 30000 char
        _GUICtrlEdit_SetText($hLog, StringRight(GUICtrlRead($hLog), 20000)) ; short the content of CtrlBox to 20000 char
    EndIf
    _GUICtrlEdit_AppendText($hLog, $sLine & @CRLF)
EndFunc   ;==>_LogPrint

Func WM_DROPFILES($hWnd, $iMsg, $wParam, $lParam)
    If $bDropAllowed Then
        Local $sExt = ".bmp|.png|.jpg|.gif" ; img drop filtering thanks to @UEZ
        Local $aFileList = _WinAPI_DragQueryFileEx($wParam)
        If Not @error Then
            For $i = 1 To $aFileList[0]
                If StringInStr($sExt, StringRegExpReplace($aFileList[$i], ".*(\.+)", "$1")) Then
                    $bDropped = True
                    $sFile = FileGetShortName($aFileList[$i])
                    ExitLoop
                EndIf
            Next
        Else
            _LogPrint("Error on drop" & @CRLF)
        EndIf
        _WinAPI_DragFinish($wParam)
        _LogPrint("Droped: " & $sFile & @CRLF)
        Return 0
    EndIf
EndFunc   ;==>WM_DROPFILES

Func _ShowInBrowser($sImg) ; setup Javascript engine with also embeded the "entity" library

    If StringRight($sImg, 3) = "svg" Then
    Else
    EndIf
    ; *** create a minimal 'html' page listing for the browser control
    Local $sHTML = "<HTML><HEAD>" & @CRLF & _
            "<meta http-equiv=""X-UA-Compatible"" content=""IE=edge"" />" & @CRLF & _
            "</HEAD>" & @CRLF & _
            "<body>" & @CRLF & _
            '<img src="' & $sImg & '" style="width:100%; height:100%;" />' & @CRLF & _
            "</body>" & @CRLF & _
            "</HTML>" & @CRLF ; html closing tags
    ; *** end of html page listing
    ; _LogPrint(">_" & @CRLF)
    $oIE.navigate('about:blank')
    While Not String($oIE.readyState) = 'complete' ; wait for about:blank
        Sleep(100)
    WEnd

    $oIE.document.Write($sHTML) ; inject lising directly to the HTML document:
    $oIE.document.close() ; close the write stream
    Sleep(1000)
    $oIE.document.execCommand("Refresh")
EndFunc   ;==>_ShowInBrowser

Func _checkFileFormat($sFile)
    Local $hImage = _GDIPlus_ImageLoadFromFile($sFile)
    Local $aFormat = _GDIPlus_ImageGetRawFormat($hImage)
    If $aFormat[1] <> "PNG" Then _ConvertToPNG($hImage)
    _GDIPlus_ImageDispose($hImage)
EndFunc   ;==>_checkFileFormat

Func _ConvertToPNG(ByRef $hImage)
    Local $CLSID = _GDIPlus_EncodersGetCLSID('PNG')
    $sFile = FileGetShortName(@ScriptDir & "\Input.png")
    _GDIPlus_ImageSaveToFileEx($hImage, $sFile, $CLSID)
EndFunc   ;==>_ConvertToPNG

Func _EmptyLog()
    FileClose($hTail)
    $hTail = FileOpen($sLogFile, $FO_OVERWRITE)
    FileWrite($hTail, "Start log: " & @YEAR & '/' & @MON & '/' & @MDAY & ' ' & @HOUR & ':' & @MIN & ':' & @SEC & @CRLF)
    FileFlush($hTail)
    FileClose($hTail)
    $hTail = FileOpen($sLogFile) ; read only
EndFunc   ;==>_EmptyLog

Func _CheckDependencies()
    Local $iDependencie = 0
    $iDependencie += FileExists(@ScriptDir & "\voronoi.exe") ; http://www.drububu.com/illustration/tsp/voronoi.zip
    $iDependencie += FileExists(@ScriptDir & "\stippler.dll") ; " also contained in the above archive
    $iDependencie += FileExists(@ScriptDir & "\concorde.exe") ; http://www.math.uwaterloo.ca/tsp/concorde/downloads/codes/cygwin/concorde.exe.gz
    $iDependencie += FileExists(@ScriptDir & "\cygwin1.dll") ; get one from here https://cygwin.com/snapshots/ get cygwin1-xxxxxxxxx.dll.xz
    $iDependencie += FileExists(@ScriptDir & "\svg_extract.exe") ; http://www.drububu.com/illustration/tsp/svg_extract.zip
    $iDependencie += FileExists(@ScriptDir & "\tsp2svg.exe") ; http://www.drububu.com/illustration/tsp/tsp2svg.zip
    Return $iDependencie = 6
EndFunc   ;==>_CheckDependencies

Func _Exit()
    _GDIPlus_Shutdown()
    FileClose($hTail)
    AutoItSetOption("GUIOnEventMode", 0)
    GUIRegisterMsg($WM_DROPFILES, "")
    Exit
EndFunc   ;==>_Exit

 

Edited September 21, 2019 by Chimp
updated image link

[iamtheky]

but can you make that an actual solvable maze

no but seriously, someone do that.

[RTFC]

@Chimp: Great; interesting to see TSP being used in this way.

@iamtheky: This is by definition a solvable maze, as it's a single line. So in a maze like that, just keep either your left hand (c.q. your right hand) touching the nearest left (c.q. right) wall as you keep walking forward, and you'll get to the exit.

For those interested in the underlying maths, an example of an AutoIt script solving the TSP (Travelling Salesman Problem), see example 2 in my Simulated Annealing thread.

Edited October 25, 2017 by RTFC

[UEZ]

Well done @Chimp 

The script doesn't run properly when the path has blanks (white space) and I cannot scroll the result using the scrollbar to the right.

 

 

 

[Gianni]

Hi all, thanks for the likes and the feedback

@iamtheky, about the maze, as @RTFC sayd "This is by definition a solvable maze, as it's a single line", indeed it is already a maze,  but there is a funny way to find quickly the exit, here how:
1) to create a "maze" do like this: create a TSP art by setting sampling points to 1000 and then drag & droppo an image like the following for example  (a black square) to the tsp art generator.

A "maze" similar to this will be created.

2) now, open the folder of the script and you can find the tsp_art.svg that is the just created tsp_art, Right click it and select the open with notepad option.

go to the last line at the bottom and change this statement  stroke-width="0.25" to stroke-width="2" and save.

3) doubble.click the just modified file and it should open in a browser, zoom in or zoom out  the view of the browser to fit it on the screen if necessary abd then hit the "print screen" key.

4) now paste the screen in msPaint. There, using the eraser 'open' the "enter" of the maze at top left and the "exit" at right bottom.

5) using the fill tool, fill with a color the black line of the maze, you con see that only a part is filled, do the same with another color on the other part.

You can see that the the limit of the 2 colors is the best way to exit the maze.

@RTFC, Iv'e already used your nice TSP solver and it would be nice to use it here, but unfortunately the execution speed of AutoIt for solving a tsp problem with a number of points (towns) of the order of some thousands can not compete with the specialized program "concorde", written in C and compiled. (http://www.math.uwaterloo.ca/tsp/concorde/index.html)

 

On 10/25/2017 at 10:57 AM, UEZ said:

The script doesn't run properly when the path has blanks (white space) and I cannot scroll the result using the scrollbar to the right.

  Hi @UEZ, I've modified the script and posted in first post, now should work ok also with paths with white spaces.
About the scroll bars, my intention was to use the display window just as a little preview. For this purpose I'm using this statement within the HTML part that shows the svc file on the browser control: style="width:100%; height:100%;" this should fit the whole image in the available display area without the need of "scrolling", and it works like this on my pc,  but maybe, as you reported, this is not always the case.
The inibition of the scroll bars is due to the fact I've overlapped to the browser control area another trasparent control (a transparent label), that avoids the interaction of the user with the browser control itself. This has been done because otherwise when you drag and drop an image to the browser control, the drop event is captured by the browser control instead of by the GUI, avoiding the management of the drop event into the script.
I will try to use some other technique so to allow the use of the both (suggestions are welcome )
... anyway, not need to say that the final generated TSP_art is saved in the same directory of the script with the name tsp_art.svg. ready to be doubble-clicked...,, also the intermediate "voronoi art" is saved in the same directory with the name of out.svg.

Edited September 21, 2019 by Chimp
update images links

[UEZ]

Thanks for the update.

[RTFC]

14 hours ago, Chimp said:

unfortunately the execution speed of AutoIt for solving a tsp problem with a number of points (towns) of the order of some thousands can not compete

I'm not surprised. Thanks for the reference; unfortunately, the website appears to be down at the moment; I'll try again later.

It's funny though; the longer I look at these patterns, the more I'm reminded of brains; possibly not a coincidence that TSP optimises for shortest path and neuronal connections form a small-world network. Food for thought...

[Lakes]

TSP Art picture of a brain.

[willichan]

I love this.  I am having all kinds of fun already.

[DWB]

I am new to TSP art and to AutoIt.  I've downloaded all the dependencies and script into a single director (C:\TSP).  When I double-click on the script (TSP.au3), nothing happens.  I've attached an image of the directory in which I'm working.  I'd like to make TSP art from the Tree1.png file.  Thanks for any suggestions on how to proceed.

 

[Gianni]

Hi @DWB,

renaming the file cygwin1-20180309.dll to cygwin1.dll should fix....
let us know ...