Jump to content

Convex Polygon Graph from Image


Recommended Posts

I am trying to figure out a way to generate a graph of convex polygonal shapes from an image.

This is roughly the image I would like to try with:

Posted Image

I want to create the polygons from the white space.

Anyone have any ideas?

Currently the one idea I have is turning the image into a vector and then converting all the polygons generated from that into purely convex ones, but I'm still looking into the implementation of that.

Link to comment
Share on other sites

There is no simple solution to this problem and the solution isn't unique in general.

This is the classical understatement to mean that the problem is awfully complex and costly in computing time*power.

It amounts to optimize the selection of edge points to perform a Delaunay triangulation. With rugged edges like this, you're likely to end up with 10^K triangulations to compute and compare, with K > too much. Smoothing the edges won't make you much good.

Try vectorizing the edges to give you a idea of the number of vertices necessary.

Don't even think doing this in AutoIt and switch to Matlab (or one of its clones), Mapple, Sage, Mathematica or even better AMPL (or Fortran if you're a Real Programmer™).

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
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)

Link to comment
Share on other sites

Anyone have any ideas?

That girl with the ponytail... I know her!

-- or --

This forum does not support the botting of your Rorschach Test!

Oh, wait, you meant helpful ideas.

:mellow:

Edited by PsaltyDS
Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law
Link to comment
Share on other sites

Heheh I forgot to mention a couple things in my original post.

I really do not need much accuracy for the edges. I did a little by hand for an example:

Posted Image

What you can see started in the upper left there is really all the accuracy I need. Also runtime, as long as it is not astronomical, shouldn't be an issue. I don't need this to run in real time or anything close to it. Delaunay may still be the way to go or, perhaps just by hand like in the image above :P.

EDIT:

Perhaps I just do it by hand and then run an optimization algorithm on what I created, since we all know what I have just shown you is far from perfect :mellow:

Edited by Desu
Link to comment
Share on other sites

That's an important "detail".

If accuracy and optimality are dropped, you might have a half-baked simple solution in approximating by hand a vector path along the edges, then triangulating the vertices by starting with one vertex both sides and including next vertex from the right side (first triangle), then the last edge plus the next vertex from the left side (second triangle) and so on. You're guaranteed to have only convex polygons (triangles), which you can then eventually feed to a Delaunay reduction which will reorganize and merge vertices into larger convex polygons.

Clearly doable in AutoIt, even if a little off typical spectrum.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
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)

Link to comment
Share on other sites

I've tried to compose something specific to this image you've posted. If cheap color remapping isn't your style, you can try _GDIPlus_ImageAttributesSetColorKeys. For example, an area full of grass patterns is in green and a little bit brown here and there. You can remap a range of green and brown colors to a unique color and then work with Regions and/or GraphicsPath.

#include <GDIP.au3>
Opt("MustDeclareVars", 1)

_GDIPlus_Startup()

Local $hImage, $hClone, $hGraphics, $hIA, $aClrs[2][2], $aSize, $iW, $iH
Local $hBmpSave, $hBrush, $hRegion

$hImage = _GDIPlus_ImageLoadFromFile(@ScriptDir & "\mapimage.jpg")
$aSize = _GDIPlus_ImageGetDimension($hImage)
If IsArray($aSize) Then
    $iW = $aSize[0]
    $iH = $aSize[1]
EndIf

$hClone = _GDIPlus_BitmapCreateFromScan0($iW, $iH)
$hGraphics = _GDIPlus_ImageGetGraphicsContext($hClone)

$hIA = _GDIPlus_ImageAttributesCreate()

$aClrs[0][0] = 1
$aClrs[1][0] = 0xFFFFFFFF ; replace white
$aClrs[1][1] = 0xFF0000FF ; with red

_GDIPlus_ImageAttributesSetRemapTable($hIA, 1, True, $aClrs)
_GDIPlus_GraphicsDrawImageRectRectIA($hGraphics, $hImage, 0, 0, $iW, $iH, 0, 0, $iW, $iH, $hIA)

_GDIPlus_GraphicsDispose($hGraphics)
_GDIPlus_ImageAttributesDispose($hIA)

$hRegion = _ComposeInteriorRegion($hImage, $hClone)

$hBmpSave = _GDIPlus_BitmapCreateFromScan0($iW, $iH)
$hGraphics = _GDIPlus_ImageGetGraphicsContext($hBmpSave)
$hBrush = _GDIPlus_BrushCreateSolid(0xFFFF99EE)

_GDIPlus_RegionCombineRect($hRegion, _GDIPlus_RectFCreate(0, 0, $iW, $iH), 3)
_GDIPlus_GraphicsFillRegion($hGraphics, $hRegion, $hBrush)
_GDIPlus_ImageSaveToFile($hBmpSave, @ScriptDir & "\test1.jpg")

_GDIPlus_BrushDispose($hBrush)
_GDIPlus_GraphicsDispose($hGraphics)
_GDIPlus_BitmapDispose($hBmpSave)

_Gdiplus_BitmapDispose($hClone)
_GDIPlus_ImageDispose($hImage)

_GUIDrawRegionRects($hRegion, $iW, $iH)

; Hit test a few points
ConsoleWrite(_GDIPlus_RegionIsVisiblePoint($hRegion, 1, 1) & @CRLF)
ConsoleWrite(_GDIPlus_RegionIsVisiblePoint($hRegion, 256, 256) & @CRLF)

_GDIPlus_RegionDispose($hRegion)
_GDIPlus_Shutdown()

Func _GUIDrawRegionRects($hRgn, $iGUIWidth, $iGUIHeight)
    Local $hGUI, $hGraphics, $hPath, $hCloneRgn, $aRects

    $hGUI = GUICreate("Testo", $iGUIWidth, $iGUIHeight)

    $hCloneRgn = _GDIPlus_RegionClone($hRgn)
    $hGraphics = _GDIPlus_GraphicsCreateFromHWND($hGUI)
    $hPath = _GDIPlus_PathCreate()
    $aRects = _GDIPlus_RegionGetScans($hCloneRgn)
    _GDIPlus_PathAddRectangles($hPath, $aRects)

    GUISetState()

    _GDIPlus_GraphicsDrawPath($hGraphics, $hPath)

    Do
    Until GUIGetMsg() = -3

    _GDIPlus_RegionDispose($hCloneRgn)
    _GDIPlus_PathDispose($hPath)
    _GDIPlus_GraphicsDispose($hGraphics)
    GUIDelete()

EndFunc

Func _ComposeInteriorRegion($hImg1, $hImg2)
    Local $aSize, $iW, $iH, $iSize, $tbmData1, $tbmData2, $tPixels1, $tPixels2
    Local $pScan0_1, $pScan0_2
    Local $aPixs1, $aPixs2
    Local $hRgn

    $aSize = _GDIPlus_ImageGetDimension($hImg1)
    If Not IsArray($aSize) Then Return SetError(1, 0, 0)
    $aSize = _GDIPlus_ImageGetDimension($hImg2)
    If Not IsArray($aSize) Then Return SetError(2, 0, 0)

    $iW = $aSize[0]
    $iH = $aSize[1]
    $iSize = $iW * $iH * 3

    $hRgn = _GDIPlus_RegionCreateFromRect(_GDIPlus_RectFCreate(0, 0, $iW, $iH))

    $tbmData1 = _GDIPlus_BitmapLockBits($hImg1, 0, 0, $iW, $iH, $GDIP_ILMREAD, $GDIP_PXF24RGB)
    $tbmData2 = _GDIPlus_BitmapLockBits($hImg2, 0, 0, $iW, $iH, $GDIP_ILMREAD, $GDIP_PXF24RGB)

    $pScan0_1 = DllStructGetData($tbmData1, "Scan0")
    $tPixels1 = DllStructCreate("byte[" & $iSize & "]", $pScan0_1)
    $pScan0_2 = DllStructGetData($tbmData2, "Scan0")
    $tPixels2 = DllStructCreate("byte[" & $iSize & "]", $pScan0_2)

    $aPixs1 = StringRegExp(StringTrimLeft(DllStructGetData($tPixels1, 1), 2), "(?i)[a-z0-9]{6}", 3)
    $aPixs2 = StringRegExp(StringTrimLeft(DllStructGetData($tPixels2, 1), 2), "(?i)[a-z0-9]{6}", 3)

    For $i = 0 To $iW-1 Step 8
        For $j = 0 To $iH-1 Step 8
            If $aPixs1[$i*$iW+$j] <> $aPixs2[$i*$iW+$j] Then
                _GDIPlus_RegionCombineRect($hRgn, _GDIPlus_RectFCreate($j, $i, 7, 7), 3)
            EndIf
        Next
    Next

    _GDIPlus_BitmapUnlockBits($hImg1, $tbmData1)
    _GDIPlus_BitmapUnlockBits($hImg2, $tbmData2)

    Return SetError(0, 0, $hRgn)
EndFunc

The last GUI window is not something you can work with to make a meaningful GraphicsPath object, or polygon figure. I still need to figure the raw data that is stored as an array of bytes and build closed shape from it. Basically, the clipped region should contain smaller rectangles. You'll see what I mean.

..and GDIP.au3.

Link to comment
Share on other sites

I've tried to compose something specific to this image you've posted. If cheap color remapping isn't your style, you can try _GDIPlus_ImageAttributesSetColorKeys. For example, an area full of grass patterns is in green and a little bit brown here and there. You can remap a range of green and brown colors to a unique color and then work with Regions and/or GraphicsPath.

#include <GDIP.au3>
Opt("MustDeclareVars", 1)

_GDIPlus_Startup()

Local $hImage, $hClone, $hGraphics, $hIA, $aClrs[2][2], $aSize, $iW, $iH
Local $hBmpSave, $hBrush, $hRegion

$hImage = _GDIPlus_ImageLoadFromFile(@ScriptDir & "\mapimage.jpg")
$aSize = _GDIPlus_ImageGetDimension($hImage)
If IsArray($aSize) Then
    $iW = $aSize[0]
    $iH = $aSize[1]
EndIf

$hClone = _GDIPlus_BitmapCreateFromScan0($iW, $iH)
$hGraphics = _GDIPlus_ImageGetGraphicsContext($hClone)

$hIA = _GDIPlus_ImageAttributesCreate()

$aClrs[0][0] = 1
$aClrs[1][0] = 0xFFFFFFFF ; replace white
$aClrs[1][1] = 0xFF0000FF ; with red

_GDIPlus_ImageAttributesSetRemapTable($hIA, 1, True, $aClrs)
_GDIPlus_GraphicsDrawImageRectRectIA($hGraphics, $hImage, 0, 0, $iW, $iH, 0, 0, $iW, $iH, $hIA)

_GDIPlus_GraphicsDispose($hGraphics)
_GDIPlus_ImageAttributesDispose($hIA)

$hRegion = _ComposeInteriorRegion($hImage, $hClone)

$hBmpSave = _GDIPlus_BitmapCreateFromScan0($iW, $iH)
$hGraphics = _GDIPlus_ImageGetGraphicsContext($hBmpSave)
$hBrush = _GDIPlus_BrushCreateSolid(0xFFFF99EE)

_GDIPlus_RegionCombineRect($hRegion, _GDIPlus_RectFCreate(0, 0, $iW, $iH), 3)
_GDIPlus_GraphicsFillRegion($hGraphics, $hRegion, $hBrush)
_GDIPlus_ImageSaveToFile($hBmpSave, @ScriptDir & "\test1.jpg")

_GDIPlus_BrushDispose($hBrush)
_GDIPlus_GraphicsDispose($hGraphics)
_GDIPlus_BitmapDispose($hBmpSave)

_Gdiplus_BitmapDispose($hClone)
_GDIPlus_ImageDispose($hImage)

_GUIDrawRegionRects($hRegion, $iW, $iH)

; Hit test a few points
ConsoleWrite(_GDIPlus_RegionIsVisiblePoint($hRegion, 1, 1) & @CRLF)
ConsoleWrite(_GDIPlus_RegionIsVisiblePoint($hRegion, 256, 256) & @CRLF)

_GDIPlus_RegionDispose($hRegion)
_GDIPlus_Shutdown()

Func _GUIDrawRegionRects($hRgn, $iGUIWidth, $iGUIHeight)
    Local $hGUI, $hGraphics, $hPath, $hCloneRgn, $aRects

    $hGUI = GUICreate("Testo", $iGUIWidth, $iGUIHeight)

    $hCloneRgn = _GDIPlus_RegionClone($hRgn)
    $hGraphics = _GDIPlus_GraphicsCreateFromHWND($hGUI)
    $hPath = _GDIPlus_PathCreate()
    $aRects = _GDIPlus_RegionGetScans($hCloneRgn)
    _GDIPlus_PathAddRectangles($hPath, $aRects)

    GUISetState()

    _GDIPlus_GraphicsDrawPath($hGraphics, $hPath)

    Do
    Until GUIGetMsg() = -3

    _GDIPlus_RegionDispose($hCloneRgn)
    _GDIPlus_PathDispose($hPath)
    _GDIPlus_GraphicsDispose($hGraphics)
    GUIDelete()

EndFunc

Func _ComposeInteriorRegion($hImg1, $hImg2)
    Local $aSize, $iW, $iH, $iSize, $tbmData1, $tbmData2, $tPixels1, $tPixels2
    Local $pScan0_1, $pScan0_2
    Local $aPixs1, $aPixs2
    Local $hRgn

    $aSize = _GDIPlus_ImageGetDimension($hImg1)
    If Not IsArray($aSize) Then Return SetError(1, 0, 0)
    $aSize = _GDIPlus_ImageGetDimension($hImg2)
    If Not IsArray($aSize) Then Return SetError(2, 0, 0)

    $iW = $aSize[0]
    $iH = $aSize[1]
    $iSize = $iW * $iH * 3

    $hRgn = _GDIPlus_RegionCreateFromRect(_GDIPlus_RectFCreate(0, 0, $iW, $iH))

    $tbmData1 = _GDIPlus_BitmapLockBits($hImg1, 0, 0, $iW, $iH, $GDIP_ILMREAD, $GDIP_PXF24RGB)
    $tbmData2 = _GDIPlus_BitmapLockBits($hImg2, 0, 0, $iW, $iH, $GDIP_ILMREAD, $GDIP_PXF24RGB)

    $pScan0_1 = DllStructGetData($tbmData1, "Scan0")
    $tPixels1 = DllStructCreate("byte[" & $iSize & "]", $pScan0_1)
    $pScan0_2 = DllStructGetData($tbmData2, "Scan0")
    $tPixels2 = DllStructCreate("byte[" & $iSize & "]", $pScan0_2)

    $aPixs1 = StringRegExp(StringTrimLeft(DllStructGetData($tPixels1, 1), 2), "(?i)[a-z0-9]{6}", 3)
    $aPixs2 = StringRegExp(StringTrimLeft(DllStructGetData($tPixels2, 1), 2), "(?i)[a-z0-9]{6}", 3)

    For $i = 0 To $iW-1 Step 8
        For $j = 0 To $iH-1 Step 8
            If $aPixs1[$i*$iW+$j] <> $aPixs2[$i*$iW+$j] Then
                _GDIPlus_RegionCombineRect($hRgn, _GDIPlus_RectFCreate($j, $i, 7, 7), 3)
            EndIf
        Next
    Next

    _GDIPlus_BitmapUnlockBits($hImg1, $tbmData1)
    _GDIPlus_BitmapUnlockBits($hImg2, $tbmData2)

    Return SetError(0, 0, $hRgn)
EndFunc

The last GUI window is not something you can work with to make a meaningful GraphicsPath object, or polygon figure. I still need to figure the raw data that is stored as an array of bytes and build closed shape from it. Basically, the clipped region should contain smaller rectangles. You'll see what I mean.

..and GDIP.au3.

Very nice GDI+ code demonstration again :mellow:

BR,

UEZ

Please don't send me any personal message and ask for support! I will not reply!

Selection of finest graphical examples at Codepen.io

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

Link to comment
Share on other sites

Very nice authenticity! That is just about exactly what I was going for and you've probably saved me a bunch of work :mellow: . Thanks for the help everyone, been quite educational thus far.

Link to comment
Share on other sites

You can try the following modified code to get the outline:

#include <GDIP.au3>
Opt("MustDeclareVars", 1)

_GDIPlus_Startup()

Local $hImage, $hClone, $hGraphics, $hIA, $aClrs[2][2], $aSize, $iW, $iH
Local $hBmpSave, $hBrush, $hRegion

$hImage = _GDIPlus_ImageLoadFromFile(@ScriptDir & "\mapimage.jpg")
$aSize = _GDIPlus_ImageGetDimension($hImage)
If IsArray($aSize) Then
    $iW = $aSize[0]
    $iH = $aSize[1]
EndIf

$hClone = _GDIPlus_BitmapCreateFromScan0($iW, $iH)
$hGraphics = _GDIPlus_ImageGetGraphicsContext($hClone)

$hIA = _GDIPlus_ImageAttributesCreate()

$aClrs[0][0] = 1
$aClrs[1][0] = 0xFFFFFFFF ; replace white
$aClrs[1][1] = 0xFF0000FF ; with red

_GDIPlus_ImageAttributesSetRemapTable($hIA, 1, True, $aClrs)
_GDIPlus_GraphicsDrawImageRectRectIA($hGraphics, $hImage, 0, 0, $iW, $iH, 0, 0, $iW, $iH, $hIA)

_GDIPlus_GraphicsDispose($hGraphics)
_GDIPlus_ImageAttributesDispose($hIA)

$hRegion = _ComposeInteriorRegion($hImage, $hClone)

$hBmpSave = _GDIPlus_BitmapCreateFromScan0($iW, $iH)
$hGraphics = _GDIPlus_ImageGetGraphicsContext($hBmpSave)
$hBrush = _GDIPlus_BrushCreateSolid(0xFFFF99EE)

_GDIPlus_RegionCombineRect($hRegion, _GDIPlus_RectFCreate(0, 0, $iW, $iH), 3)
_GDIPlus_GraphicsFillRegion($hGraphics, $hRegion, $hBrush)
_GDIPlus_ImageSaveToFile($hBmpSave, @ScriptDir & "\test1.jpg")

_GDIPlus_BrushDispose($hBrush)
_GDIPlus_GraphicsDispose($hGraphics)
_GDIPlus_BitmapDispose($hBmpSave)

_Gdiplus_BitmapDispose($hClone)
_GDIPlus_ImageDispose($hImage)

_GUIDrawRegionRects($hRegion, $iW, $iH)

; Hit test a few points
ConsoleWrite(_GDIPlus_RegionIsVisiblePoint($hRegion, 1, 1) & @CRLF)
ConsoleWrite(_GDIPlus_RegionIsVisiblePoint($hRegion, 256, 256) & @CRLF)

_GDIPlus_RegionDispose($hRegion)
_GDIPlus_Shutdown()

Func _GUIDrawRegionRects($hRgn, $iGUIWidth, $iGUIHeight)
    Local $hGUI, $hGraphics, $hPath, $hCloneRgn, $aPoints

    $hGUI = GUICreate("Testo", $iGUIWidth, $iGUIHeight)

    $hCloneRgn = _GDIPlus_RegionClone($hRgn)
    $hGraphics = _GDIPlus_GraphicsCreateFromHWND($hGUI)
    $hPath = _GDIPlus_PathCreate()
    $aPoints = _OutlineShapeFromRegion($hCloneRgn)
    _GDIPlus_PathAddPolygon($hPath, $aPoints)

    GUISetState()

    _GDIPlus_GraphicsDrawPath($hGraphics, $hPath)

    Do
    Until GUIGetMsg() = -3

    _GDIPlus_PathDispose($hPath)
    _GDIPlus_RegionDispose($hCloneRgn)
    _GDIPlus_GraphicsDispose($hGraphics)
    GUIDelete()

EndFunc

Func _ComposeInteriorRegion($hImg1, $hImg2)
    Local $aSize, $iW, $iH, $iSize, $tbmData1, $tbmData2, $tPixels1, $tPixels2
    Local $pScan0_1, $pScan0_2
    Local $aPixs1, $aPixs2
    Local $hRgn

    $aSize = _GDIPlus_ImageGetDimension($hImg1)
    If Not IsArray($aSize) Then Return SetError(1, 0, 0)
    $aSize = _GDIPlus_ImageGetDimension($hImg2)
    If Not IsArray($aSize) Then Return SetError(2, 0, 0)

    $iW = $aSize[0]
    $iH = $aSize[1]
    $iSize = $iW * $iH * 3

    $hRgn = _GDIPlus_RegionCreateFromRect(_GDIPlus_RectFCreate(0, 0, $iW, $iH))

    $tbmData1 = _GDIPlus_BitmapLockBits($hImg1, 0, 0, $iW, $iH, $GDIP_ILMREAD, $GDIP_PXF24RGB)
    $tbmData2 = _GDIPlus_BitmapLockBits($hImg2, 0, 0, $iW, $iH, $GDIP_ILMREAD, $GDIP_PXF24RGB)

    $pScan0_1 = DllStructGetData($tbmData1, "Scan0")
    $tPixels1 = DllStructCreate("byte[" & $iSize & "]", $pScan0_1)
    $pScan0_2 = DllStructGetData($tbmData2, "Scan0")
    $tPixels2 = DllStructCreate("byte[" & $iSize & "]", $pScan0_2)

    $aPixs1 = StringRegExp(StringTrimLeft(DllStructGetData($tPixels1, 1), 2), "(?i)[a-z0-9]{6}", 3)
    $aPixs2 = StringRegExp(StringTrimLeft(DllStructGetData($tPixels2, 1), 2), "(?i)[a-z0-9]{6}", 3)

    For $i = 0 To $iW-1 Step 8
        For $j = 0 To $iH-1 Step 8
            If $aPixs1[$i*$iW+$j] <> $aPixs2[$i*$iW+$j] Then
                _GDIPlus_RegionCombineRect($hRgn, _GDIPlus_RectFCreate($j, $i, 8, 8), 3)
            EndIf
        Next
    Next

    _GDIPlus_BitmapUnlockBits($hImg1, $tbmData1)
    _GDIPlus_BitmapUnlockBits($hImg2, $tbmData2)

    Return SetError(0, 0, $hRgn)
EndFunc

Func _OutlineShapeFromRegion($hRgn)
    Local $aRects, $aPts[1][2], $aRet[1][2], $aPts, $iP, $iSwapX, $iSwapY, $iX, $iY, $i, $j

    $aRects = _GDIPlus_RegionGetScans($hRgn)

    ReDim $aPts[$aRects[0][0]*4+1][2]
    $aPts[0][0] = $aRects[0][0]*4

    ReDim $aRet[$aPts[0][0]+1][2]
    $aRet[0][0] = 0

    For $i = 1 To $aRects[0][0]
        $iP = ($i-1)*4+1
        $aPts[$iP][0]   = $aRects[$i][0]
        $aPts[$iP][1]   = $aRects[$i][1]
        $aPts[$iP+1][0] = $aRects[$i][0]
        $aPts[$iP+1][1] = $aRects[$i][1] + $aRects[$i][3]
        $aPts[$iP+2][0] = $aRects[$i][0] + $aRects[$i][2]
        $aPts[$iP+2][1] = $aRects[$i][1]
        $aPts[$iP+3][0] = $aRects[$i][0] + $aRects[$i][2]
        $aPts[$iP+3][1] = $aRects[$i][1] + $aRects[$i][3]
    Next

    For $i = 1 To $aPts[0][0]
        For $j = 1 To $aPts[0][0]-$i-1
            If $aPts[$j][1] > $aPts[$j+1][1] Then
                $iSwapX = $aPts[$j][0]
                $iSwapY = $aPts[$j][1]
                $aPts[$j][0] = $aPts[$j+1][0]
                $aPts[$j][1] = $aPts[$j+1][1]
                $aPts[$j+1][0] = $iSwapX
                $aPts[$j+1][1] = $iSwapY
            EndIf
        Next
    Next

    $i = 1
    While $i <= $aPts[0][0]
        $iX = $aPts[$i][0]
        $iY = $aPts[$i][1]

        $i += 1
        While $i <= $aPts[0][0] And $iY = $aPts[$i][1]
            If $aPts[$i][0] < $iX Then $iX = $aPts[$i][0]
            $i += 1
        WEnd

        $aRet[0][0] += 1
        $aRet[$aRet[0][0]][0] = $iX
        $aRet[$aRet[0][0]][1] = $iY
    WEnd

    $i = $aPts[0][0]
    While $i >= 1
        $iX = $aPts[$i][0]
        $iY = $aPts[$i][1]

        $i -= 1
        While $i >= 1 And $iY = $aPts[$i][1]
            If $iX < $aPts[$i][0] Then $iX = $aPts[$i][0]
            $i -= 1
        WEnd

        $aRet[0][0] += 1
        $aRet[$aRet[0][0]][0] = $iX
        $aRet[$aRet[0][0]][1] = $iY
    WEnd

    ReDim $aRet[$aRet[0][0]+1][2]
    Return $aRet
EndFunc

The _OutlineShapeFromRegion function can be optimized to do about 4 times betters. The problem with the whole approach is that if your map is not an opaque shape (a circle inside a circle, for example), the exclusive inner shape will be included even though it shouldn't.

Edited by Authenticity
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...