# Sort Polygon Coordinates

## Recommended Posts

hi, guys, okay?
Can anyone give me a light?

I need to sort the coordinates of the vertices of a non-convex polygon, no matter whether it is clockwise, counterclockwise, from where or where it goes, just follow the "path" correctly!

I have here the image to exemplify and an array with the coordinates of the polygon in order "not correct".

Local \$XY[12][3] = [[0,0], [15,0], [15,3], [0,3], [6,3], [9,3], [9,12], [6,12], [0,12], [15,12], [15,15], [0,15]]

Here's what I tried to do, I tried to make the arctangent, arctangent 2, order from the center of the box that catches all vertices from the source and nothing has worked, since I drew on paper several times and I can not think in nothing!

Local \$XY[12][3] = [[0,0], [15,0], [15,3], [0,3], [6,3], [9,3], [9,12], [6,12], [0,12], [15,12], [15,15], [0,15]]
_SortCoords(\$XY)
_ArrayDisplay(\$XY)

Func _SortCoords(ByRef \$XY)
Local \$xcenter = (_ArrayMax(\$XY, 1, -1, -1, 0) - _ArrayMin(\$XY, 1, -1, -1, 0)) / 2
Local \$ycenter = (_ArrayMax(\$XY, 1, -1, -1, 1) - _ArrayMin(\$XY, 1, -1, -1, 1)) / 2

For \$i = 0 To UBound(\$XY) -1
\$XY[\$i][2] = atan2((\$ycenter - \$XY[\$i][1]),(\$xcenter - \$XY[\$i][0]))
Next

EndFunc   ;==>_SortCoords

Func atan2(\$y, \$x)
Return (2 * ATan(\$y / (\$x + Sqrt(\$x * \$x + \$y * \$y))))
EndFunc

If anyone can help me with this I would be immensely grateful

Edited by darkshark

##### Share on other sites
13 minutes ago, darkshark said:

I need to sort the coordinates of the vertices of a non-convex polygon

What do you mean with sorting in this particular case and why you want to sort it?

How should the sorted array look like?

Edited by UEZ

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

##### Share on other sites

I need the points are ordered because I want to calculate the moment of inertia of the second order, the product of inertia, area, centroid, etc. in this section, this is for structural analysis!

I need the coordinates follow a logical order, that part of point 1 (blue) and go to 2,3,4,5,6,7,8,9,10,11 and finish in 12

it is not necessary start from the point 1 may from another point but following the same logic!

Edit:

Here's The Coordinates of the vertices!

Edited by darkshark

##### Share on other sites

If the path always turns a corner, then you can set up some rules. One of the coordinates (x or y) must always repeat, but never more than once in a contiguous sequence. That prevents travelling in a straight line. eg between points 3, 4, 11, and 12. Write the code to always turn a corner et voila. You also have to select the coordinates closest to the current position when following these rules, and avoid visiting the same position twice. If the polygon has corners that are not right angles, this approach won't work.

Edited by czardas

##### Share on other sites

I think that's not possible because you don't know how the path between the points is really.

If you draw your polygons how you have provided the draw looks like this here:

#include <Array.au3>
#include <GDIPlus.au3>

\$fScale = 15
_GDIPlus_Startup()
Local \$XY[13][2] = [[12], [0 * \$fScale,0 * \$fScale], [15 * \$fScale,0 * \$fScale], [15 * \$fScale,3 * \$fScale], [0 * \$fScale,3 * \$fScale], _
[6 * \$fScale,3 * \$fScale], [9 * \$fScale,3 * \$fScale], [9 * \$fScale,12 * \$fScale], [6 * \$fScale,12 * \$fScale], _
[0 * \$fScale,12 * \$fScale], [15 * \$fScale,12 * \$fScale], [15 * \$fScale,15 * \$fScale], [0 * \$fScale,15 * \$fScale]]
Local \$hGUI = GUICreate("", 300, 300)
GUISetState()
\$hGfx = _GDIPlus_GraphicsCreateFromHWND(\$hGUI)
Local \$hPen = _GDIPlus_PenCreate(0xFFFF0000)

\$hPath = _GDIPlus_PathCreate()
\$hMatrix = _GDIPlus_MatrixCreate()
_GDIPlus_MatrixTranslate(\$hMatrix, 30, 30)

For \$i = 1 To \$XY[0][0]
_GDIPlus_PathAddRectangle(\$hPath, \$XY[\$i][0] - 2, \$XY[\$i][1] - 2, 4, 4)
Next
_GDIPlus_PathTransform(\$hPath, \$hMatrix)
_GDIPlus_GraphicsDrawPath(\$hGfx, \$hPath, \$hPen)

_GDIPlus_PenSetColor(\$hPen, 0xFF000000)
_GDIPlus_PathReset(\$hPath)
_GDIPlus_PathTransform(\$hPath, \$hMatrix)

_GDIPlus_GraphicsDrawPath(\$hGfx, \$hPath, \$hPen)

_GDIPlus_MatrixDispose(\$hMatrix)
_GDIPlus_PenDispose(\$hPen)
_GDIPlus_PathDispose(\$hPath)
_GDIPlus_GraphicsDispose(\$hGfx)
_GDIPlus_Shutdown()

Do

Until GUIGetMsg() = -3

The red squares are the coordinates and the black line represents the polygon.

Edited by UEZ

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

##### Share on other sites
14 minutes ago, UEZ said:

I think that's not possible

I agree. I thought I had figured it out, but it just dawned on me now after watching The X Files LOL. There isn't enough information for a general case. You beat me to it.

##### Share on other sites

I should also watch more X-Files for some "dawn moments".

Currently I'm playing also with polygons by trying to transform a 2d world map to a 3d sphere incl. rotating "the world". It runs currently with 2 fps...

Edited by UEZ
• 1

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

##### Share on other sites

just out of curiosity I tried to process the given points with the traveling salesman algorithm using and adapting this script by  @RTFC , to see what would come out, but the resulting shape is far from the desired one (of course... )

; the Travelling Salesman Problem (https://en.wikipedia.org/wiki/Travelling_salesman_problem)
; a Simulated Annealing example (combinatorial minimisation), by RTFC (22 Feb 2016)
; Adapted from Press et al. Numerical Recipes, 2nd ed., pp.438-443.

; Note that the algorithm converges on A local minimum (in terms of the
; user-defined cost-function(s)), which is not necessarily THE global minimum.
; Note also that the search path, duration, and final result may differ from run to run (city coordinates change every time).
; Several parameters and weights can be tweaked to adjust this.

#include <Array.au3>
#include <GUIConstants.au3>
#include <GDIplus.au3>
#include <Math.au3>

Global Const \$GUIwidth = 600
Global Const \$GUIheight = 400
Global Const \$citysize = 10
Global Const \$halfcitysize = \$citysize / 2

\$hwnd = GUICreate("Travelling Salesman Problem (using Simulated Annealing), by RTFC", \$GUIwidth, \$GUIheight)
GUISetState()

_GDIPlus_Startup()
Global \$graphics = _GDIPlus_GraphicsCreateFromHWND(\$hwnd)
Global \$bitmap = _GDIPlus_BitmapCreateFromGraphics(\$GUIwidth, \$GUIheight, \$graphics)
Global \$backbuffer = _GDIPlus_ImageGetGraphicsContext(\$bitmap)
Global \$hPenLine = _GDIPlus_PenCreate(0xFF0000FF, 4)
Global \$hPenCircle = _GDIPlus_PenCreate(0xFFFF0000, 4)

; Simulated Annealing vars
Global \$temperat, \$path, \$kk, \$nswap, \$nswapstep, \$cost, \$tempstep, \$absimp, \$lowestcost

; initialise
SRandom(@SEC + @AutoItPID); initialise randomising seed
\$verbose = True ; T: write regular progress updates to console

Local \$XY[12][2] = [[0, 0],[15, 0],[15, 3],[0, 3],[6, 3],[9, 3],[9, 12],[6, 12],[0, 12],[15, 12],[15, 15],[0, 15]]
; define cities
Global \$ncity = UBound(\$XY) ; 20
; if \$ncity<10 then Exit        ; we need something to work with

Global \$maxcity = \$ncity * 50
Global \$n[7], \$xx[7], \$yy[7] ; base-1 indexed
Global \$x[\$ncity + 1], \$y[\$ncity + 1], \$iorder[\$ncity + 1], \$jorder[\$maxcity + 1] ; base-1 indexed

;______START OF ANNEALING ROUTINE____________

\$nover = 100 * \$ncity ; maximum number of paths at any temperature
\$nlimit = 10 * \$ncity ; maximum number of successful path changes before continuing
\$nwrite = Int(\$nover / 5) ; default status update interval if verbose=.t.
\$tempsteps = 100 ; number of temperature steps to try
\$tfactor = 0.90 ; annealing schedule: temperature is reduced by this factor after each step
\$path = 0

While True
\$temperat = 0.5 ; initial temperature; smaller = more aggressive + more myopic search
\$absimp = 0 ; counter
\$nswapstepzero = 0 ; counter

; prep the buffers
For \$cc = 1 To 6
\$n[\$cc] = 0
Next

For \$cc = 0 To \$ncity - 1
\$x[\$cc] = 0.2 + \$XY[\$cc][0] * 0.020 ; Random()
\$y[\$cc] = 0.2 + \$XY[\$cc][1] * 0.020 ; Random()
\$iorder[\$cc] = \$cc
\$jorder[\$cc] = 0
Next

For \$cc = \$ncity + 1 To \$maxcity
\$jorder[\$cc] = 0
Next

; prep the cost vars
_CalcPathLength()
\$initcost = \$path
\$lowestcost = \$path

; main loop starts here
For \$tempstep = 1 To \$tempsteps ; try up to N temperature steps
\$nswap = 0
\$nswapstep = 0

For \$kk = 1 To \$nover
\$n[1] = Random(1, \$ncity, 1) ; choose beginning and end of segment
\$n[2] = Random(1, \$ncity, 1)
If \$n[2] >= \$n[1] Then \$n[2] = 1 + Mod((\$n[2] + 1), \$ncity)

; count number of cities not on segment (\$nn)
\$nn = 1 + Mod((\$n[1] - \$n[2] + \$ncity - 1), \$ncity)
If \$nn < 3 Then ContinueLoop

; decide whether to do a segment transport or reversal (equal chances)
\$doTransport = (Random() <= 0.5)
If \$doTransport Then ; try a segment transport
\$n[3] = \$n[2] + Int(Abs(\$nn - 2) * Random()) + 1
\$n[3] = 1 + Mod(\$n[3] - 1, \$ncity) ; transport to a location not on the path
_TransportCost()

Else ; try a reversal instead
_ReversalCost()
EndIf

; Listen to the wind, talk to the trees...
Case True
\$nswap += 1
\$path += \$cost
If \$doTransport Then
_DoTransport()
Else
_DoReversal()
EndIf

If \$lowestcost > \$path Then
\$nswapstep += 1
\$absimp += 1
\$lowestcost = \$path
EndIf

If \$nswap >= \$nlimit Then ExitLoop
EndSwitch
Next

If \$verbose Then _ScreenOut()
If \$nswapstep = 0 Then \$nswapstepzero += 1
If \$nswapstepzero = 30 Then ExitLoop ; no more improvements in the last N temperature steps

; reduce temperature = likelihood of following a trajectory away from the nearest LOCAL optimum (in the hope of getting nearer to the GLOBAL optimum)
\$temperat *= \$tfactor
Next

; show final result
MsgBox(\$MB_OKCANCEL, "Simulated Annealing Test Result", "Shortest Path Length: " & \$lowestcost)
Exit

WEnd

_GDIclose()
Exit

If \$cost < 0 Then
Return True
Else ; this is where all the magic happens!
Return (Random() < Exp(-(\$cost / \$temperat)))
EndIf

Func _CalcPathLength()

\$path = 0 ; Global var
Local \$cc, \$index1, \$index2
For \$cc = 1 To \$ncity - 1
\$index1 = \$iorder[\$cc]
\$index2 = \$iorder[\$cc + 1]
\$path += _Distance(\$x[\$index1], \$x[\$index2], \$y[\$index1], \$y[\$index2])
Next
\$index1 = \$iorder[\$ncity] ; close the loop by tying path ends together
\$index2 = \$iorder[1]
\$path += _Distance(\$x[\$index1], \$x[\$index2], \$y[\$index1], \$y[\$index2])

EndFunc   ;==>_CalcPathLength

Func _Distance(\$x1, \$x2, \$y1, \$y2)

Return Sqrt(((\$x1 - \$x2) ^ 2) + ((\$y1 - \$y2) ^ 2))
EndFunc   ;==>_Distance

Func _ReversalCost()

\$n[3] = 1 + Mod((\$n[1] + \$ncity - 2), \$ncity) ; find the city before n[1]...
\$n[4] = 1 + Mod(\$n[2], \$ncity) ; and after n[2]

; find coordinates of the four cities
Local \$ii, \$jj, \$dex
For \$jj = 1 To 4
\$dex = \$n[\$jj]
\$ii = \$iorder[\$dex]
\$xx[\$jj] = \$x[\$ii]
\$yy[\$jj] = \$y[\$ii]
Next

; calculate the cost of disconnecting the segment at both ends and reconnecting in the opposite order
\$cost = -_Distance(\$xx[1], \$xx[3], \$yy[1], \$yy[3])
\$cost -= _Distance(\$xx[2], \$xx[4], \$yy[2], \$yy[4])
\$cost += _Distance(\$xx[1], \$xx[4], \$yy[1], \$yy[4])
\$cost += _Distance(\$xx[2], \$xx[3], \$yy[2], \$yy[3])

EndFunc   ;==>_ReversalCost

Func _DoReversal()

Local \$mm = (1 + Mod((\$n[2] - \$n[1] + \$ncity), \$ncity)) * .5
Local \$ii, \$jj, \$ll, \$itmp
For \$jj = 1 To \$mm
\$ii = 1 + Mod((\$n[1] + \$jj - 2), \$ncity)
\$ll = 1 + Mod((\$n[2] - \$jj + \$ncity), \$ncity)

\$itmp = \$iorder[\$ii]
\$iorder[\$ii] = \$iorder[\$ll]
\$iorder[\$ll] = \$itmp
Next

EndFunc   ;==>_DoReversal

Func _TransportCost()

\$n[4] = 1 + Mod(\$n[3], \$ncity) ; find the city following n[3]
\$n[5] = 1 + Mod((\$n[1] + \$ncity - 2), \$ncity) ; find the city before n[1]...
\$n[6] = 1 + Mod(\$n[2], \$ncity) ; and after n[2]

; find coordinates of the six cities
Local \$jj, \$dex
For \$jj = 1 To 6
\$dex = \$n[\$jj]
\$ii = \$iorder[\$dex]
\$xx[\$jj] = \$x[\$ii]
\$yy[\$jj] = \$y[\$ii]
Next

; calculate the cost of disconnecting the path segment n1->n2, opening a space between n3-n4, connecting the segment in the space, and conencting n5 to n6
\$cost = -_Distance(\$xx[2], \$xx[6], \$yy[2], \$yy[6])
\$cost -= _Distance(\$xx[1], \$xx[5], \$yy[1], \$yy[5])
\$cost -= _Distance(\$xx[3], \$xx[4], \$yy[3], \$yy[4])
\$cost += _Distance(\$xx[1], \$xx[3], \$yy[1], \$yy[3])
\$cost += _Distance(\$xx[2], \$xx[4], \$yy[2], \$yy[4])
\$cost += _Distance(\$xx[5], \$xx[6], \$yy[5], \$yy[6])

EndFunc   ;==>_TransportCost

Func _DoTransport()

Local \$m1, \$m2, \$m3, \$pp
\$m1 = 1 + Mod((\$n[2] - \$n[1] + \$ncity), \$ncity) ; find # cities from n1->n2
\$m2 = 1 + Mod((\$n[5] - \$n[4] + \$ncity), \$ncity) ; find # cities from n4->n5
\$m3 = 1 + Mod((\$n[3] - \$n[6] + \$ncity), \$ncity) ; find # cities from n6->n3

Local \$mm = 1
For \$pp = 1 To \$m1
\$jj = 1 + Mod(\$pp + \$n[1] - 2, \$ncity)
\$jorder[\$mm] = \$iorder[\$jj]
\$mm += 1
Next

For \$pp = 1 To \$m2
\$jj = 1 + Mod(\$pp + \$n[4] - 2, \$ncity)
\$jorder[\$mm] = \$iorder[\$jj]
\$mm += 1
Next

For \$pp = 1 To \$m3
\$jj = 1 + Mod(\$pp + \$n[6] - 2, \$ncity)
\$jorder[\$mm] = \$iorder[\$jj]
\$mm += 1
Next

For \$pp = 1 To \$ncity
\$iorder[\$pp] = \$jorder[\$pp]
Next

EndFunc   ;==>_DoTransport

Func _ScreenOut()

ConsoleWrite("Simulated Annealing. Initial Path length: " & \$initcost & @CRLF)
ConsoleWrite("Step: " & \$tempstep & " of " & \$tempsteps & "; Temperature: " & \$temperat & @CRLF)
ConsoleWrite("Executed Swaps: " & \$nswap & "; shortest Path length: " & \$lowestcost & @CRLF)
ConsoleWrite("Total Improvements: " & \$absimp & "; Improvements this step: " & \$nswapstep & @CRLF & @CRLF)
_DrawTSroute()

EndFunc   ;==>_ScreenOut

Func _DrawTSroute()

_GDIPlus_GraphicsClear(\$backbuffer)

For \$cc = 1 To \$ncity - 1
\$index1 = \$iorder[\$cc]
\$index2 = \$iorder[\$cc + 1]
_DrawLine(\$x[\$index1], \$x[\$index2], \$y[\$index1], \$y[\$index2])
Next
\$index1 = \$iorder[\$ncity] ; close the loop by tying path ends together
\$index2 = \$iorder[1]
_DrawLine(\$x[\$index1], \$x[\$index2], \$y[\$index1], \$y[\$index2])
_GDIPlus_GraphicsDrawImageRect(\$graphics, \$bitmap, 0, 0, \$GUIwidth, \$GUIheight)

EndFunc   ;==>_DrawTSroute

Func _DrawLine(\$x1, \$x2, \$y1, \$y2)

Local \$x1scaled = Round(\$GUIwidth * \$x1, 0)
Local \$y1scaled = Round(\$GUIheight * \$y1, 0)
Local \$x2scaled = Round(\$GUIwidth * \$x2, 0)
Local \$y2scaled = Round(\$GUIheight * \$y2, 0)

_GDIPlus_GraphicsDrawArc(\$backbuffer, \$x1scaled - \$halfcitysize, \$y1scaled - \$halfcitysize, \$citysize, \$citysize, 0, 360, \$hPenCircle)
_GDIPlus_GraphicsDrawLine(\$backbuffer, \$x1scaled, \$y1scaled, \$x2scaled, \$y2scaled, \$hPenLine)

EndFunc   ;==>_DrawLine

Func _GDIclose()

_GDIPlus_PenDispose(\$hPenLine)
_GDIPlus_PenDispose(\$hPenCircle)
_GDIPlus_GraphicsDispose(\$backbuffer)
_GDIPlus_BitmapDispose(\$bitmap)
_GDIPlus_GraphicsDispose(\$graphics)
_GDIPlus_Shutdown()

EndFunc   ;==>_GDIclose

small minds discuss people average minds discuss events great minds discuss ideas.... and use AutoIt....

##### Share on other sites

I think the given case is solvable, but the general case is not. My idea is to always try to turn back the way you came (clockwise or anticlockwise). As soon as you add a few more coordinates though, the problem will acquire multiple solutions and become unsolvable. How to differentiate those patterns which only have one solution (given a set of rules) is unclear to me. The rules are not clearly defined anyway, but it's still interesting.

Edited by czardas

##### Share on other sites
43 minutes ago, UEZ said:

2 fps

Gee that's a bit clunky.

##### Share on other sites

Got it, guys, I also was not finding a solution so I decided to ask for help here to see if anyone could help me!

But the way I have to think of another way to do it!

But anyway, thank you all!

@Chimp
I loved this script, I had never seen, he makes clear my problem hahaha.

@UEZ and @czardas

Thank you for trying to help me!

##### Share on other sites
5 minutes ago, czardas said:

Gee that's a bit clunky.

Well, that's the limit of AutoIt. Have a look to the alpha version.

;coded by UEZ build 2016-04-08
#pragma compile(Icon, "c:\Program Files (x86)\AutoIt3\Icons\au3.ico")
#AutoIt3Wrapper_Run_Au3Stripper=y
#Au3Stripper_Parameters=/so /pe /rm
#AutoIt3Wrapper_Run_After=del /f /q "%scriptdir%\%scriptfile%_stripped.au3"5

#include <GDIPlus.au3>
#include <GuiConstantsEx.au3>
#include <WindowsConstants.au3>

_GDIPlus_Startup()
Global \$hGUI, \$iFPS = 0, \$iShowFPS = 0, \$bExit, \$i
Global Const \$iW = 947, \$iH = 620, \$iWh = \$iW / 2, \$iHh = \$iH / 2, \$sTitle = "GDI+ 3D Object Rotation v1.2 alpha"
Global Const \$fPi = ACos(-1), \$fRad = \$fPi / 180, \$fDeg = 180 / \$fPi

AutoItSetOption("GUIOnEventMode", 1)

GDIPlus_3DRotation()

AutoItSetOption("GUIOnEventMode", 0)
_GDIPlus_Shutdown()

Func GDIPlus_3DRotation()
\$bExit = False
\$hGUI = GUICreate(\$sTitle, \$iW, \$iH) ;, -1, -1, \$WS_POPUP)
GUISetState(@SW_SHOW, \$hGUI)

;create canvas elements
Local Const \$hDC = _WinAPI_GetDC(\$hGUI)
Local Const \$hHBitmap = _WinAPI_CreateCompatibleBitmap(\$hDC, \$iW, \$iH)
Local Const \$hDC_backbuffer = _WinAPI_CreateCompatibleDC(\$hDC)
Local Const \$DC_obj = _WinAPI_SelectObject(\$hDC_backbuffer, \$hHBitmap)
Local Const \$hCanvas = _GDIPlus_GraphicsCreateFromHDC(\$hDC_backbuffer)
_GDIPlus_GraphicsSetSmoothingMode(\$hCanvas, \$GDIP_SMOOTHINGMODE_HIGHQUALITY)
_GDIPlus_GraphicsSetPixelOffsetMode(\$hCanvas, \$GDIP_PIXELOFFSETMODE_HIGHQUALITY)

Local Const \$hBrush_Clr = _GDIPlus_BrushCreateSolid(0xFF303030), _
\$hBrush_FPS = _GDIPlus_BrushCreateSolid(0xFFA0A0A0), _
\$hBrush_Fill = _GDIPlus_BrushCreateSolid(0xFFFFFFFF), _
\$hBrush_Fill2 = _GDIPlus_BrushCreateSolid(0x10FFFFFF), _
\$hPen_Line = _GDIPlus_PenCreate(0xFF40B040, 1), _
\$hFormat_FPS = _GDIPlus_StringFormatCreate(), _
\$hFamily_FPS = _GDIPlus_FontFamilyCreate("Arial"), _
\$hFont_FPS = _GDIPlus_FontCreate(\$hFamily_FPS, 8), _
\$tLayout_FPS = _GDIPlus_RectFCreate(0, 0, 60, 16)

_GDIPlus_PenSetLineJoin(\$hPen_Line, 2)

\$iFPS = 0

Local Const \$hPath = _GDIPlus_PathCreate(), \$sPolygon = BinaryToString(_Polygons())

Local \$aSphere = CreateSphere(\$aData, \$iWh, \$iHh, 130)
Local \$iAmountDots = \$aSphere[0], \$tCoords = \$aSphere[1], \$tTypes = \$aSphere[2]

Local \$fRotX = 0 * \$fDeg, \$fRotY = 0, \$fRotZ = 10 * \$fDeg, \$iFillMode = 0, \$i

Local \$tPoints = DllStructCreate("float dots[" & 2 * \$iAmountDots & "]")

Do
DllCall(\$__g_hGDIPDll, "int", "GdipFillRectangle", "handle", \$hCanvas, "handle", \$hBrush_Clr, "float", 0, "float", 0, _
"float", \$iW, "float", \$iH) ;erase canvas background

For \$i = 1 To \$iAmountDots
Translate3Dto2D(\$tCoords, \$i, \$fRotX, \$fRotY, \$fRotY - \$fRotX, \$iWh, \$iHh, 1000)
\$tPoints.dots((2 * \$i - 1)) = \$tCoords.fX((\$i))
\$tPoints.dots((2 * \$i)) = \$tCoords.fY((\$i))
Next

\$hPath2 = DllCall(\$__g_hGDIPDll, "int", "GdipCreatePath2", "struct*", \$tPoints, "struct*", \$tTypes, "int", \$iAmountDots, "int", \$iFillMode, "handle*", 0)[5]

DllCall(\$__g_hGDIPDll, "int", "GdipFillPath", "handle", \$hCanvas, "handle", \$hBrush_Fill2, "handle", \$hPath)
DllCall(\$__g_hGDIPDll, "int", "GdipFillPath", "handle", \$hCanvas, "handle", \$hBrush_Fill, "handle", \$hPath2)
DllCall(\$__g_hGDIPDll, "int", "GdipDrawPath", "handle", \$hCanvas, "handle", \$hPen_Line, "handle", \$hPath2)

DllCall(\$__g_hGDIPDll, "int", "GdipDeletePath", "handle", \$hPath2)

\$fRotX += 0.025
\$fRotY += 0.033

_GDIPlus_GraphicsDrawStringEx(\$hCanvas, "FPS: " & \$iShowFPS, \$hFont_FPS, \$tLayout_FPS, \$hFormat_FPS, \$hBrush_FPS) ;draw background message text
_WinAPI_BitBlt(\$hDC, 0, 0, \$iW, \$iH, \$hDC_backbuffer, 0, 0, \$SRCCOPY) ;blit drawn bitmap to GUI

\$iFPS += 1
If \$bExit Then ExitLoop
Until Not Sleep(10)

;release resources
_GDIPlus_PathDispose(\$hPath)
_GDIPlus_PathDispose(\$hPath2)
_GDIPlus_FontDispose(\$hFont_FPS)
_GDIPlus_FontFamilyDispose(\$hFamily_FPS)
_GDIPlus_StringFormatDispose(\$hFormat_FPS)
_GDIPlus_BrushDispose(\$hBrush_Clr)
_GDIPlus_BrushDispose(\$hBrush_FPS)
_GDIPlus_BrushDispose(\$hBrush_Fill)
_GDIPlus_BrushDispose(\$hBrush_Fill2)
_GDIPlus_PenDispose(\$hPen_Line)
_GDIPlus_GraphicsDispose(\$hCanvas)
_WinAPI_SelectObject(\$hDC_backbuffer, \$DC_obj)
_WinAPI_DeleteDC(\$hDC_backbuffer)
_WinAPI_DeleteObject(\$hHBitmap)
_WinAPI_ReleaseDC(\$hGUI, \$hDC)
GUIDelete(\$hGUI)
EndFunc   ;==>GDIPlus_3DRotation

Func Translate3Dto2D(ByRef \$tStruct, \$iPos, \$fRotX, \$fRotY, \$fRotZ, \$fCenterX = 0, \$fCenterY = 0, \$fZDeepCorrection = 1000)
Local Const \$fCosRotX = Cos(\$fRotX), \$fSinRotX = Sin(\$fRotX), _
\$fCosRotY = Cos(\$fRotY), \$fSinRotY = Sin(\$fRotY), _
\$fCosRotZ = Cos(\$fRotZ), \$fSinRotZ = Sin(\$fRotZ), _
\$f1 = \$fCosRotY * \$tStruct.x((\$iPos)), _
\$f2 = \$fSinRotX * \$tStruct.y((\$iPos)), _
\$f3 = \$fCosRotX * \$tStruct.z((\$iPos)), _
\$f4 = \$fCosRotX * \$tStruct.y((\$iPos)), _
\$f5 = \$fSinRotX * \$tStruct.z((\$iPos)), _
\$f6 = \$f1 - \$fSinRotY * (\$f2 + \$f3), _
\$fXPos = \$fCosRotZ * \$f6 - \$fSinRotZ * (\$f4 - \$f5), _
\$fYPos = \$fSinRotZ * \$f6 + \$fCosRotZ * (\$f4 - \$f5), _
\$fZPos = \$fSinRotY * \$tStruct.x((\$iPos)) + \$fCosRotY * (\$f2 + \$f3), _
\$fZPerspCorrection = 1 / (\$fZPos / \$fZDeepCorrection + 1)
\$tStruct.fX((\$iPos)) = \$fXPos * \$fZPerspCorrection + \$fCenterX
\$tStruct.fY((\$iPos)) = \$fYPos * \$fZPerspCorrection + \$fCenterY
EndFunc   ;==>Translate3Dto2D

\$bExit = True

Func CalcFPS() ;display FPS
\$iShowFPS = \$iFPS
\$iFPS = 0
EndFunc   ;==>CalcFPS

Local \$tCoords = DllStructCreate("struct;float x[" & \$iAmountDots & "];float y[" & \$iAmountDots & "];float z[" & \$iAmountDots & "];float fX[" & \$iAmountDots & "];float fY[" & \$iAmountDots & "];float fZ[" & \$iAmountDots & "];endstruct")
Local \$tTypes = DllStructCreate("byte type[" & \$iAmountDots & "]")
Local \$i, \$fLongitude, \$fLatitude
For \$i = 1 To \$iAmountDots
\$fLatitude = 2 * ATan(2.718281828^((\$iHh - \$aData[\$i][1]) / \$fRadius)) - (\$fPi / 2)
\$tCoords.x((\$i)) = \$fRadius * Cos(\$fLatitude) * Cos(\$fLongitude)
\$tCoords.y((\$i)) = \$fRadius * Cos(\$fLatitude) * Sin(\$fLongitude)
Next
Local \$aResult[3] = [\$iAmountDots, \$tCoords, \$tTypes]
Return \$aResult
EndFunc

Func Add_Polygon(\$sPolygon, \$hPath, \$fScale = 1.0)
Local \$aPolygons = StringRegExp(\$sPolygon, "(?mi)polygon\((.*)\)", 3), \$i, \$j, \$k, \$aPolygon, \$tPoints
For \$i = 0 To UBound(\$aPolygons) - 1
\$aPolygon = StringRegExp(\$aPolygons[\$i], "\d*\.?\d+", 3)
\$tPoints = DllStructCreate("float coordinates[" & UBound(\$aPolygon) & "]")
\$k = 1
For \$j = 0 To UBound(\$aPolygon) - 2 Step 2
\$tPoints.coordinates((2 * \$k - 1)) = \$aPolygon[\$j] * \$fScale
\$tPoints.coordinates((2 * \$k)) = \$aPolygon[\$j + 1] * \$fScale
\$k += 1
Next
DllCall(\$__g_hGDIPDll, "int", "GdipAddPathPolygon", "handle", \$hPath, "struct*", \$tPoints, "int", UBound(\$aPolygon) / 2)
\$tPoints = 0
Next
EndFunc

;Code below was generated by: 'File to Base64 String' Code Generator v1.20 Build 2015-09-19

Func _Polygons(\$bSaveBinary = False, \$sSavePath = @ScriptDir)
Local \$Polygons
\$Polygons &= 'OQIMMgMM9QEzMgMZNgRaAmcKgQYMACk='
\$Polygons = _WinAPI_Base64Decode(\$Polygons)
If @error Then Return SetError(1, 0, 0)
Local \$tSource = DllStructCreate('byte[' & BinaryLen(\$Polygons) & ']')
DllStructSetData(\$tSource, 1, \$Polygons)
Local \$tDecompress
_WinAPI_LZNTDecompress(\$tSource, \$tDecompress, 69852)
If @error Then Return SetError(3, 0, 0)
\$tSource = 0
Local Const \$bString = Binary(DllStructGetData(\$tDecompress, 1))
If \$bSaveBinary Then
Local Const \$hFile = FileOpen(\$sSavePath & "\Polygon.txt", 18)
If @error Then Return SetError(2, 0, \$bString)
FileWrite(\$hFile, \$bString)
FileClose(\$hFile)
EndIf
Return \$bString
EndFunc   ;==>_Polygons

Func _WinAPI_Base64Decode(\$sB64String)
Local \$aCrypt = DllCall("Crypt32.dll", "bool", "CryptStringToBinaryA", "str", \$sB64String, "dword", 0, "dword", 1, "ptr", 0, "dword*", 0, "ptr", 0, "ptr", 0)
If @error Or Not \$aCrypt[0] Then Return SetError(1, 0, "")
Local \$bBuffer = DllStructCreate("byte[" & \$aCrypt[5] & "]")
\$aCrypt = DllCall("Crypt32.dll", "bool", "CryptStringToBinaryA", "str", \$sB64String, "dword", 0, "dword", 1, "struct*", \$bBuffer, "dword*", \$aCrypt[5], "ptr", 0, "ptr", 0)
If @error Or Not \$aCrypt[0] Then Return SetError(2, 0, "")
Return DllStructGetData(\$bBuffer, 1)
EndFunc   ;==>_WinAPI_Base64Decode

Func _WinAPI_LZNTDecompress(ByRef \$tInput, ByRef \$tOutput, \$iBufferSize)
\$tOutput = DllStructCreate("byte[" & \$iBufferSize & "]")
If @error Then Return SetError(1, 0, 0)
Local \$aRet = DllCall("ntdll.dll", "uint", "RtlDecompressBuffer", "ushort", 0x0002, "struct*", \$tOutput, "ulong", \$iBufferSize, "struct*", \$tInput, "ulong", DllStructGetSize(\$tInput), "ulong*", 0)
If @error Then Return SetError(2, 0, 0)
If \$aRet[0] Then Return SetError(3, \$aRet[0], 0)
Return \$aRet[6]
EndFunc   ;==>_WinAPI_LZNTDecompress

The background map is the original map saved as polygons. The rotating world is the transformation of that map.

Edited by UEZ
• 3

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

##### Share on other sites

@UEZ that's beautiful.

Edited by czardas
• 1

##### Share on other sites

Wow, that's Fantastic, UEz *-*

##### Share on other sites

I just... I don't even know how you do what you do UEZ Lol

4-5 fps on my computer.

##### Share on other sites

There is of course no unique "solution" to the question asked, at least in the general case (even as simple as your I-beam).

To convince you, try to persuade yourself that the "most logical path" could well be the following (code freely borrowed to UEZ):

#include <Array.au3>
#include <GDIPlus.au3>

Local \$nPoints = 12
Local \$fScale = 20
_GDIPlus_Startup()
Local \$XY[\$nPoints + 1][2] = [ _
[\$nPoints], _
[ 0,  0], _
[15,  0], _
[ 9,  3], _
[15,  3], _
[ 9, 12], _
[15, 12], _
[15, 15], _
[ 0, 15], _
[ 6, 12], _
[ 0, 12], _
[ 6,  3], _
[ 0,  3] _
]
For \$i = 1 To \$nPoints
\$XY[\$i][0] = \$XY[\$i][0] * \$fScale + 50
\$XY[\$i][1] = \$XY[\$i][1] * \$fScale + 50
Next
Local \$hGUI = GUICreate("", 20 * \$fScale + 25, 20 * \$fScale + 25)
GUISetState()
\$hGfx = _GDIPlus_GraphicsCreateFromHWND(\$hGUI)
Local \$hPen = _GDIPlus_PenCreate(0xFFFF0000)

\$hPath = _GDIPlus_PathCreate()
\$hMatrix = _GDIPlus_MatrixCreate()
;~ _GDIPlus_MatrixTranslate(\$hMatrix, 30, 30)

For \$i = 1 To \$nPoints
_GDIPlus_PathAddRectangle(\$hPath, \$XY[\$i][0] - 2, \$XY[\$i][1] - 2, 4, 4)
Next
_GDIPlus_PathTransform(\$hPath, \$hMatrix)
_GDIPlus_GraphicsDrawPath(\$hGfx, \$hPath, \$hPen)

_GDIPlus_PenSetColor(\$hPen, 0xFF000000)
_GDIPlus_PathReset(\$hPath)
_GDIPlus_PathTransform(\$hPath, \$hMatrix)

_GDIPlus_GraphicsDrawPath(\$hGfx, \$hPath, \$hPen)

_GDIPlus_MatrixDispose(\$hMatrix)
_GDIPlus_PenDispose(\$hPen)
_GDIPlus_PathDispose(\$hPath)
_GDIPlus_GraphicsDispose(\$hGfx)
_GDIPlus_Shutdown()

Do

Until GUIGetMsg() = -3

Even with simples vertice clouds, there are many possible variations, each of them being as "logical" or plausible than the others. Note that the section area is bigger in my example than the original I-beam, hence section area is not a valid criterion. Possible very dangerous structures could be built from most variants.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

##### Share on other sites
9 hours ago, Chimp said:

tried to process the given points with the traveling salesman algorithm

That approach might work, but you'd have to adjust the cost functions to define the desired result as the optimum to be achieved. Off the top of my head  (without trying), I'd say, maybe impose additional cost conditions (for this particular case!) of every vertex angle being 90 degrees, and minimising total enclosed surface area. Defining appropriate cost functions is always the hardest part.

My Contributions and Wrappers

Spoiler

##### Share on other sites

It would look something like this (with thanks to Chimp for the initial adaptation):

#include <Array.au3>
#include <GUIConstants.au3>
#include <GDIplus.au3>
#include <Math.au3>

Global Const \$GUIwidth = 600
Global Const \$GUIheight = 400
Global Const \$citysize = 10
Global Const \$halfcitysize = \$citysize / 2

\$hwnd = GUICreate("Straight-Angle Travelling Salesman Problem (using Simulated Annealing), by RTFC", \$GUIwidth, \$GUIheight)
GUISetState()

_GDIPlus_Startup()
Global \$graphics = _GDIPlus_GraphicsCreateFromHWND(\$hwnd)
Global \$bitmap = _GDIPlus_BitmapCreateFromGraphics(\$GUIwidth, \$GUIheight, \$graphics)
Global \$backbuffer = _GDIPlus_ImageGetGraphicsContext(\$bitmap)
Global \$hPenLine = _GDIPlus_PenCreate(0xFF0000FF, 4)
Global \$hPenCircle = _GDIPlus_PenCreate(0xFFFF0000, 4)

; Simulated Annealing vars
Global \$temperat, \$path, \$kk, \$nswap, \$nswapstep, \$cost, \$tempstep, \$absimp, \$lowestcost

; initialise
SRandom(@MSEC + @AutoItPID); initialise randomising seed
\$verbose = True ; T: write regular progress updates to console

; define cities
Global \$XY[12][2] = [[0, 0],[15, 0],[15, 3],[0, 3],[6, 3],[9, 3],[9, 12],[6, 12],[0, 12],[15, 12],[15, 15],[0, 15]]
Global \$ncity = UBound(\$XY) ; 20
Global \$wrongAnglePenalty=10

Global \$maxcity = \$ncity * 50
Global \$n[7], \$xx[7], \$yy[7] ; base-1 indexed
Global \$x[\$ncity + 1], \$y[\$ncity + 1], \$iorder[\$ncity + 1], \$jorder[\$maxcity + 1] ; base-1 indexed

;______START OF ANNEALING ROUTINE____________

\$nover = 100 * \$ncity ; maximum number of paths at any temperature
\$nlimit = 10 * \$ncity ; maximum number of successful path changes before continuing
\$nwrite = Int(\$nover / 5) ; default status update interval if verbose=.t.
\$tempsteps = 100 ; number of temperature steps to try
\$tfactor = 0.90 ; annealing schedule: temperature is reduced by this factor after each step
\$path = 0

While True
\$temperat = 0.5 ; initial temperature; smaller = more aggressive + more myopic search
\$absimp = 0 ; counter
\$nswapstepzero = 0 ; counter

; prep the buffers
For \$cc = 1 To 6
\$n[\$cc] = 0
Next

For \$cc = 0 To \$ncity - 1
\$x[\$cc] = 0.2 + \$XY[\$cc][0] * 0.020 ; Random()
\$y[\$cc] = 0.2 + \$XY[\$cc][1] * 0.020 ; Random()
\$iorder[\$cc] = \$cc
\$jorder[\$cc] = 0
Next

For \$cc = \$ncity + 1 To \$maxcity
\$jorder[\$cc] = 0
Next

; prep the cost vars
\$path=_CalcPathLength()
\$prevpath=\$path
\$initcost = \$path
\$lowestcost = \$path

; main loop starts here
For \$tempstep = 1 To \$tempsteps ; try up to N temperature steps
\$nswap = 0
\$nswapstep = 0

For \$kk = 1 To \$nover
\$n[1] = Random(1, \$ncity, 1) ; choose beginning and end of segment
\$n[2] = Random(1, \$ncity, 1)
If \$n[2] >= \$n[1] Then \$n[2] = 1 + Mod((\$n[2] + 1), \$ncity)

; count number of cities not on segment (\$nn)
\$nn = 1 + Mod((\$n[1] - \$n[2] + \$ncity - 1), \$ncity)
If \$nn < 3 Then ContinueLoop

; store original situation
\$oldiorder=\$iorder
\$oldjorder=\$jorder

; decide whether to do a segment transport or reversal (equal chances)
\$doTransport = (Random() <= 0.5)
If \$doTransport Then ; try a segment transport
\$n[3] = \$n[2] + Int(Abs(\$nn - 2) * Random()) + 1
\$n[3] = 1 + Mod(\$n[3] - 1, \$ncity) ; transport to a location not on the path
_DoTransport()
Else
_DoReversal()
EndIf
\$cost=_CalcPathLength()-\$prevpath

; Listen to the wind, talk to the trees...
Case True

\$nswap += 1
\$path += \$cost
\$prevpath=\$path

If \$lowestcost > \$path Then
\$nswapstep += 1
\$absimp += 1
\$lowestcost = \$path
EndIf

If \$nswap >= \$nlimit Then ExitLoop

case Else   ;restore
\$path=\$prevpath
\$iorder=\$oldiorder
\$jorder=\$oldjorder
EndSwitch
Next

If \$verbose Then _ScreenOut()
If \$nswapstep = 0 Then \$nswapstepzero += 1
If \$nswapstepzero = 30 Then ExitLoop ; no more improvements in the last N temperature steps

; reduce temperature = likelihood of following a trajectory away from the nearest LOCAL optimum (in the hope of getting nearer to the GLOBAL optimum)
\$temperat *= \$tfactor
Next

; show final result
MsgBox(\$MB_OKCANCEL, "Simulated Annealing Test Result", "Shortest Path Length: " & \$lowestcost)
Exit

WEnd

_GDIclose()
Exit

If \$cost < 0 Then
Return True
Else ; this is where all the magic happens!
Return (Random() < Exp(-(\$cost / \$temperat)))
EndIf

Func _CalcPathLength()

Local \$path = 0
Local \$cc, \$index1, \$index2
For \$cc = 1 To \$ncity - 1
\$index1 = \$iorder[\$cc]
\$index2 = \$iorder[\$cc + 1]
\$path += _Distance(\$x[\$index1], \$x[\$index2], \$y[\$index1], \$y[\$index2])
Next
\$index1 = \$iorder[\$ncity] ; close the loop by tying path ends together
\$index2 = \$iorder[1]
\$path += _Distance(\$x[\$index1], \$x[\$index2], \$y[\$index1], \$y[\$index2])

For \$cc = 1 To \$ncity - 2
\$index1 = \$iorder[\$cc]
\$index2 = \$iorder[\$cc + 1]
\$index3 = \$iorder[\$cc + 2]

Switch \$x[\$index1]=\$x[\$index2]
case True
Switch \$y[\$index1]<>\$y[\$index2]
case False
\$path += \$wrongAnglePenalty
EndSwitch

case Else
Switch \$y[\$index1]=\$y[\$index2]
case False
\$path += \$wrongAnglePenalty
EndSwitch
EndSwitch

Switch \$x[\$index2]=\$x[\$index3]
case True
Switch \$y[\$index2]<>\$y[\$index3]
case False
\$path += \$wrongAnglePenalty
EndSwitch
case Else
Switch \$y[\$index2]=\$y[\$index3]
case False
\$path += \$wrongAnglePenalty
EndSwitch
EndSwitch

If \$x[\$index1]=\$x[\$index2] And \$x[\$index2]=\$x[\$index3] Then \$path += \$wrongAnglePenalty
If \$y[\$index1]=\$y[\$index2] And \$y[\$index2]=\$y[\$index3] Then \$path += \$wrongAnglePenalty
Next

\$index1 = \$iorder[\$ncity-1]
\$index2 = \$iorder[\$ncity]
\$index3 = \$iorder[1]

Switch \$x[\$index1]=\$x[\$index2]
case True
Switch \$y[\$index1]<>\$y[\$index2]
case False
\$path += \$wrongAnglePenalty
EndSwitch
case Else
Switch \$y[\$index1]=\$y[\$index2]
case False
\$path += \$wrongAnglePenalty
EndSwitch
EndSwitch

Switch \$x[\$index2]=\$x[\$index3]
case True
Switch \$y[\$index2]<>\$y[\$index3]
case False
\$path += \$wrongAnglePenalty
EndSwitch
case Else
Switch \$y[\$index2]=\$y[\$index3]
case False
\$path += \$wrongAnglePenalty
EndSwitch
EndSwitch

If \$x[\$index1]=\$x[\$index2] And \$x[\$index2]=\$x[\$index3] Then \$path += \$wrongAnglePenalty
If \$y[\$index1]=\$y[\$index2] And \$y[\$index2]=\$y[\$index3] Then \$path += \$wrongAnglePenalty

\$index1 = \$iorder[\$ncity]
\$index2 = \$iorder[1]
\$index3 = \$iorder[2]

Switch \$x[\$index1]=\$x[\$index2]
case True
Switch \$y[\$index1]<>\$y[\$index2]
case False
\$path += \$wrongAnglePenalty
EndSwitch
case Else
Switch \$y[\$index1]=\$y[\$index2]
case False
\$path += \$wrongAnglePenalty
EndSwitch
EndSwitch

Switch \$x[\$index2]=\$x[\$index3]
case True
Switch \$y[\$index2]<>\$y[\$index3]
case False
\$path += \$wrongAnglePenalty
EndSwitch
case Else
Switch \$y[\$index2]=\$y[\$index3]
case False
\$path += \$wrongAnglePenalty
EndSwitch
EndSwitch

If \$x[\$index1]=\$x[\$index2] And \$x[\$index2]=\$x[\$index3] Then \$path += \$wrongAnglePenalty
If \$y[\$index1]=\$y[\$index2] And \$y[\$index2]=\$y[\$index3] Then \$path += \$wrongAnglePenalty

return \$path
EndFunc   ;==>_CalcPathLength

Func _Distance(\$x1, \$x2, \$y1, \$y2)

Return Sqrt(((\$x1 - \$x2) ^ 2) + ((\$y1 - \$y2) ^ 2))
EndFunc   ;==>_Distance

Func _DoReversal()

\$n[3]=1+Mod((\$n[1]+\$ncity-2),\$ncity)    ; find the city before n[1]...
\$n[4]=1+Mod(\$n[2],\$ncity)               ; and after n[2]

; find coordinates of the four cities
local \$ii,\$jj,\$dex
For \$jj=1 to 4
\$dex=\$n[\$jj]
\$ii=\$iorder[\$dex]
\$xx[\$jj]=\$x[\$ii]
\$yy[\$jj]=\$y[\$ii]
Next

Local \$mm = (1 + Mod((\$n[2] - \$n[1] + \$ncity), \$ncity)) * .5
Local \$ii, \$jj, \$ll, \$itmp
For \$jj = 1 To \$mm
\$ii = 1 + Mod((\$n[1] + \$jj - 2), \$ncity)
\$ll = 1 + Mod((\$n[2] - \$jj + \$ncity), \$ncity)

\$itmp = \$iorder[\$ii]
\$iorder[\$ii] = \$iorder[\$ll]
\$iorder[\$ll] = \$itmp
Next

EndFunc   ;==>_DoReversal

Func _DoTransport()

\$n[4]=1+Mod(\$n[3],\$ncity)               ; find the city following n[3]
\$n[5]=1+Mod((\$n[1]+\$ncity-2),\$ncity)    ; find the city before n[1]...
\$n[6]=1+Mod(\$n[2],\$ncity)               ; and after n[2]

; find coordinates of the six cities
local \$jj,\$dex
For \$jj=1 to 6
\$dex=\$n[\$jj]
\$ii=\$iorder[\$dex]
\$xx[\$jj]=\$x[\$ii]
\$yy[\$jj]=\$y[\$ii]
Next

Local \$m1, \$m2, \$m3, \$pp
\$m1 = 1 + Mod((\$n[2] - \$n[1] + \$ncity), \$ncity) ; find # cities from n1->n2
\$m2 = 1 + Mod((\$n[5] - \$n[4] + \$ncity), \$ncity) ; find # cities from n4->n5
\$m3 = 1 + Mod((\$n[3] - \$n[6] + \$ncity), \$ncity) ; find # cities from n6->n3

Local \$mm = 1
For \$pp = 1 To \$m1
\$jj = 1 + Mod(\$pp + \$n[1] - 2, \$ncity)
\$jorder[\$mm] = \$iorder[\$jj]
\$mm += 1
Next

For \$pp = 1 To \$m2
\$jj = 1 + Mod(\$pp + \$n[4] - 2, \$ncity)
\$jorder[\$mm] = \$iorder[\$jj]
\$mm += 1
Next

For \$pp = 1 To \$m3
\$jj = 1 + Mod(\$pp + \$n[6] - 2, \$ncity)
\$jorder[\$mm] = \$iorder[\$jj]
\$mm += 1
Next

For \$pp = 1 To \$ncity
\$iorder[\$pp] = \$jorder[\$pp]
Next

EndFunc   ;==>_DoTransport

Func _ScreenOut()

ConsoleWrite("Simulated Annealing. Initial Path length: " & \$initcost & @CRLF)
ConsoleWrite("Step: " & \$tempstep & " of " & \$tempsteps & "; Temperature: " & \$temperat & @CRLF)
ConsoleWrite("Executed Swaps: " & \$nswap & "; shortest Path length: " & \$lowestcost & @CRLF)
ConsoleWrite("Total Improvements: " & \$absimp & "; Improvements this step: " & \$nswapstep & @CRLF & @CRLF)
_DrawTSroute()

EndFunc   ;==>_ScreenOut

Func _DrawTSroute()

_GDIPlus_GraphicsClear(\$backbuffer)

For \$cc = 1 To \$ncity - 1
\$index1 = \$iorder[\$cc]
\$index2 = \$iorder[\$cc + 1]
_DrawLine(\$x[\$index1], \$x[\$index2], \$y[\$index1], \$y[\$index2])
Next
\$index1 = \$iorder[\$ncity] ; close the loop by tying path ends together
\$index2 = \$iorder[1]
_DrawLine(\$x[\$index1], \$x[\$index2], \$y[\$index1], \$y[\$index2])
_GDIPlus_GraphicsDrawImageRect(\$graphics, \$bitmap, 0, 0, \$GUIwidth, \$GUIheight)

EndFunc   ;==>_DrawTSroute

Func _DrawLine(\$x1, \$x2, \$y1, \$y2)

Local \$x1scaled = Round(\$GUIwidth * \$x1, 0)
Local \$y1scaled = Round(\$GUIheight * \$y1, 0)
Local \$x2scaled = Round(\$GUIwidth * \$x2, 0)
Local \$y2scaled = Round(\$GUIheight * \$y2, 0)

_GDIPlus_GraphicsDrawArc(\$backbuffer, \$x1scaled - \$halfcitysize, \$y1scaled - \$halfcitysize, \$citysize, \$citysize, 0, 360, \$hPenCircle)
_GDIPlus_GraphicsDrawLine(\$backbuffer, \$x1scaled, \$y1scaled, \$x2scaled, \$y2scaled, \$hPenLine)

EndFunc   ;==>_DrawLine

Func _GDIclose()

_GDIPlus_PenDispose(\$hPenLine)
_GDIPlus_PenDispose(\$hPenCircle)
_GDIPlus_GraphicsDispose(\$backbuffer)
_GDIPlus_BitmapDispose(\$bitmap)
_GDIPlus_GraphicsDispose(\$graphics)
_GDIPlus_Shutdown()

EndFunc   ;==>_GDIclose

Of course, the new cost function as crudely implemented here is favouring right angles and non-overlapping line segments as additional constraints (through var \$wrongAnglePenalty). A more general solution to close polygons would need more sophisticated cost functions. The problem is how to define a generic optimal solution; that'll still depend on your specific requirements. So this specific solution won't work for angles other than 90/270 degrees, for example.

Edited by RTFC
typo
• 1

My Contributions and Wrappers

Spoiler

## Create an account

Register a new account

×

• Wiki

• Back

• Git