LarsJ

Non-rectangular selections in an image

11 posts in this topic

#1 ·  Posted (edited)

You should read and download Navigating in an image before you read and download this example. The first example shows how to navigate in an image, and the zipfile contains the test images.

The first example contains an illustration of the GUI.

The example

image1_zpsb656b00d.png

The picture to the left shows a triangular selection. It's shown with a zoom factor of 24. Each 24x24 square equals a single pixel in the source image. The oblique lines in the triangle cut across the 24x24 squares. But a selection in the source image can only include entire pixels.

The horizontal/vertical polygon in the middle picture contains pixels that are completely inside the triangle. Pixels at borders are not included. The horz/vert polygon on the right is just outside the triangle, and contains pixels at the borders.

In this example you can draw a closed polygon with the mouse. The horz/vert polygon that follows the pixel edges along the oblique polygon lines are calculated, and pixels are selected. The horz/vert polygon can be calculated inside or outside the oblique polygon.

The example is not limited to triangles. You can create a selection like this with 15 line segments:

image2_zps5aaebcc5.png

Program modes

In Navigating in an image there is only one mode: View mode. To create a non-rectangular selection you have to switch to Polygon selection mode. Click button 3 below to switch mode. This will add a new Polygon selection toolbar.

Click button 3 again to leave Polygon selection mode. A click in the title bar, the menu bar, a tab item, buttons in toolbar not related to Polygon selection, the free area of the toolbar or the status bar will also leave Polygon selection mode.

Toolbar buttons

image3_zps31e40641.png

The left group is the Copy/paste toolbar. A click on a button in Polygon selection mode will switch to View mode.

  • 1) Copy selected pixels
  • 2) Paste as new image
The middle group is the Select toolbar. The buttons are available both in View mode and in Polygon selection mode.
  • 3) Polygon selection
  • 4) Center selection
  • 5) Remove selection
  • 6) Selection colors
The last group is the Polygon selection toolbar. This toolbar is only visible when button 3 is pressed.
  • 7) New polygon
  • 8) Recent polygons
  • 9) Polygons on opposite side of support lines
  • 10) Redraw polygons (after error or debug)
  • 11) Undo last support polygon action
  • 12) Redo last support polygon action
You can right (secondary) click button 1, 6 and 8.

Note that all toolbar buttons are provided with tooltips.

In addition to colors that can be set with button 6, you can set colors for frame and grid. Right click the tab item to set all colors at once, that best fits bright and dark images. By default colors are set to fit a bright image.

More details

Copy/paste toolbar

  • 1) Copy selected pixels

    Right (secondary) click to choose background color for the selection. The default color is white. You can choose a red, green or blue color.

  • 2) Paste as new image

    In this version a selection can only be pasted as a new image.

Select toolbar
  • 3) Polygon selection

    Click this button to switch to Polygon selection mode. A new toolbar appears with six buttons, which can be used in this mode. Button 3 stays in pressed state. Click the button again to leave Polygon selection mode.

  • 4) Center selection

    If the image has been moved, it can happen that the selection isn't visible in the picture control. Click this button to move the area of the image containing the selection back into the picture control.

  • 5) Remove selection

    In Polygon selection mode this will delete the support polygon and the horizontal/vertical polygons along the line segments.

    In View mode this will prevent the polygon from being drawn. The polygon is not deleted. Not drawing the polygon will make navigation work much smoother.

  • 6) Selection colors

    Click to switch between black and white selection borders.

    Right (secondary) click to choose colors for selection borders, validation errors, debug colors and line markers.

    Right click the tab item to set all colors at once, that best fits bright and dark images.

Polygon selection toolbar
  • 7) New polygon

    Create a new polygon. You draw a polygon with the mouse. See next section.

  • 8) Recent polygons

    Click to restore recent polygon.

    Right (secondary) click to restore older polygons.

    A polygon is added to the recent list when you click New polygon, Recent polygons or when you leave Polygon selection mode. Only finished (closed) polygons are added.

  • 9) Polygons on opposite side of support lines

    Calculate and draw the horizontal/vertical polygons on the opposite side of the support lines.

    You usually only need to click this button once. The following polygons will be positioned according to this setting.

  • 10) Redraw polygons (after error or debug)

    See the sections about line validations and the debug menu below.

  • 11) Undo last support polygon action

    Actions performed in Polygon selection mode can be undone. This includes the following actions: Adding/deleting a line segment, adjusting a line end point or corner point, moving the entire polygon.

    The undo/redo list is cleared when you click New polygon, Recent polygons or Remove selection. This means, that none of these actions can be undone.

Draw a polygon

To create a non-rectangular selection you just have to draw a non-rectangular polygon with the mouse.

Nomenclature: The oblique polygon you draw with the mouse is called the support polygon. The polygons which follows the pixel edges along each oblique support line are called horizontal/vertical or horz/vert polygons. In the first illustration above you see a support polygon in the left picture, and a support polygon plus three horz/vert polygons in the two other pictures.

A support polygon is drawn as a sequence of line segments. End point of previous line must be start point of next line. The polygon is finished, when end point of last line is equal to start point of first line.

  • 1) First line segment

    Click a start point with primary mouse button, drag line to an end point, release mouse button.

  • 2) Next line segment

    Click end point of previous line, drag line with mouse to end point of next line.

    Repeat this step as many times as needed.

  • 3) Last line segment

    Click end point of previous line, drag line with mouse to start point of first line.

This illustration shows how to create a triangular selection.

image4_zps74c99170.png

First line segment

  • Zoom in to a sufficiently high level with the mouse wheel
  • Click Polygon selection button to switch to Polygon selection mode
  • Click New polygon button to create a new polygon
  • Create the first oblique support line with the mouse
  • Click possibly "Polygons on opposite side of support lines" button to calculate and draw the horz/vert polygon on opposite side of the support line
The default action when you drag with the mouse is to move the image. A click at the New polygon button disables the default action for the next drag operation, and you can create the first line segment. For the following line segments you have to start the dragging at an end line marker. Dragging outside an end line marker will move the image.

Next line segment

  • Move the mouse pointer over the marker at the end of the first line segment
  • The pointer will change to a cross cursor
  • Create the next oblique support line
Last line segment
  • Move the pointer over one of the markers at the end of the two line segments
  • The pointer will change to a cross cursor
  • Create the last oblique support line
Force empty line after list

Mouse actions

In Polygon selection mode you can still zoom in/out with the mouse wheel, drag/move the image, and click a point to zoom around this point. This is described in Navigating in an image.

You can create a support polygon as explained above.

In addition to these actions you can adjust line end points and corner points, move the entire support polygon, and delete a support line.

To see which actions you can do, just hover the mouse pointer over a line marker, and you'll get information in a tooltip. Over a line marker the pointer will change to a cross cursor. When you click Polygon selection button, tooltips will be shown for the first few support lines.

To adjust an end point of a support line or a corner point between two support lines press the Shift button, move the mouse pointer over the marker, click and drag the point.

To move the entire polygon position the mouse pointer over a middle marker, click and drag the polygon. Note that this will move the polygon relative to the source image. If you have zoomed in to a factor 24 as in the image above, the polygon will be moved in steps af 24 pixels in the picture control.

To delete a support line position the mouse pointer over a middle marker, right (secondary) click and click "Delete line segment" in the context menu. Only end lines can be deleted. For a finished polygon any line can be deleted, but as soon as one line is deleted, only end lines can be deleted.

Keyboard actions

You can use Page Up/Page Down to zoom in/out, arrow keys to move the image a pixel at a time, and Shift plus arrow keys to move the image a page at a time.

Line validations

image5_zps9e61bf2b.png

If you are creating a selection as shown to the left, and have added line 0, 1 and 2 and are going to add line 3, it can happen that line 3 gets too close to line 0. This is an error, and you'll get a visual feedback as shown to the right. The end point of the line must not be inside the red region, and the line must not cross the red region.

To get rid of the red lines/circles just recreate line 3 and make it a little shorter, or click Redraw polygons button.

Several validations are performed on line segments in this order:

  • 1) Line segments must not be too short
  • 2) Line segments must not be horizontal or vertical
  • 3) Angles between neighbor lines must not be too small or too large
  • 4) Start or end point of a new line must not be too close to neigbor segments
  • 5) Start and end point of a line must not be too close to other segments (the illustration above)
To create selections with horizontal/vertical lines that doesn't violate point 2, you can do something like this:

image6_zpsf74a84be.png

Array limits

Array limits are not validated in this version. The limits are:

  • Line segments in a support polygon: 25
  • Points in a horizontal/vertical polygon along a support line: 2000
  • Points in the final polygon (drawn with _GDIPlus_GraphicsDrawPolygon): 10000
Force empty line after list

Debug menu

Right (secondary) click a middle marker to access the Debug menu. The illustration shows some of the features of the Debug menu.

image7_zps43d35f5d.png

Picture 1 is a simple quadrilateral (polygon with four sides) with four horz/vert polygons inside the support polygon.

Right (secondary) click the middle marker below the number and select Debug polygons | Draw this/next polygon | Entire polygons. The result is shown in picture 2. The horz/vert polygon for the current support line is blue, and the horz/vert polygon for the next support line is red. The picture shows the intersection point between the horz/vert polygons.

In picture 3 (Debug polygons | Draw this/next polygon | Adjusted polygons) the part of the horz/vert polygons on the wrong side of the intersection point is cut off, and the adjusted polygons are shown.

Picture 4 (Debug polygons | Show selected pixels) shows the selected pixels with a horizontal black line.

View mode

When you switch to View mode (click Polygon selection button or View mode button (arrow icon)), the separate horz/vert polygons along each of the oblique support lines are put together into one big closed polygon (which can be drawn with _GDIPlus_GraphicsDrawPolygon). The selected pixels are calculated from this final polygon, when you click the Copy button.

Note that the middle markers are still visible, and you can drag/move the polygon around in the image. In this way you can copy/paste several different regions with the same polygon.

Copy/paste

Click Copy button to create a copy of the selected pixels on a white background. In the context menu for the Copy button, you can choose a red, green or blue background color.

Click Paste button to paste selected pixels as a new image. The new image appears in a new tab item. In this version you can only paste the selected pixels as a new image.

More details

If you are interested, you can find more information about calculations and code for the following topics in posts below (I'll add the information in the course of a week, when I get my notes organized a little better.):

Force empty line after list

This version

This version is a test version to find out whether it's possible to carry out non-rectangular selections. Only functionality required for the test is coded.

If you run the example in Scite, you can see a few warnings and error messages in the console.

The code is not cleaned up according to double defined local variables or unused parameters in function calls (primary functions to handle windows messages). This means a lot of warnings if you run Au3Check.

Zipfile

The top level is the folder "Image Editor". It contains one subfolder: "2) Non-rectangular selections". The subfolder contains source and resource files. Most important source files are:

  • Selections.au3 - run this script
  • includestoolsSelectPolygon.au3 - executes the message loop which runs when the program is in Polygon selection mode. The message loop handles drawing of the oblique support lines and responds to button clicks. In bottom of the file you find the function to draw the final polygon in View mode.
  • includestoolsSelectPolygonFunctions1.au3 - utility functions. Functions to zoom in/out, to create the final polygon, and to extract the selected pixels.
  • includestoolsSelectPolygonFunctions2.au3 - all functions to calculate, adjust and draw the horizontal/vertical polygons along the oblique support lines.
  • includestoolsSelectPolygonValidations.au3 - functions to validate the oblique support lines.
  • includestoolsSelectPolygonDebug.au3 - functions for the Debug menu.
Tested with AutoIt 3.3.10 on Windows 7 32/64 bit and Windows XP 32 bit.

Selections.7z

This update fixes an issue. More information here.

Selections2.7z

Edited by LarsJ
4 people like this

Share this post


Link to post
Share on other sites



Man, this is impressive. I'm gobsmacked! :blink:

Thanks for sharing, etc. :D


AutoIt.4.Life Clubrooms - Life is like a Donut (secret key)

Make sure brain is in gear before opening mouth!
Remember, what is not said, can be just as important as what is said.

Spoiler

What is the Secret Key? Life is like a Donut

If I put effort into communication, I expect you to read properly & fully, or just not comment.
Ignoring those who try to divert conversation with irrelevancies.
If I'm intent on insulting you or being rude, I will be obvious, not ambiguous about it.
I'm only big and bad, to those who have an over-active imagination.

I may have the Artistic Liesense ;) to disagree with you. TheSaint's Toolbox (be advised many downloads are not working due to ISP screwup with my storage)

userbar.png

Share this post


Link to post
Share on other sites

Very impressive work LarsJ  :thumbsup: .

 

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!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

Share this post


Link to post
Share on other sites

Thank you for comments and likes.

As promised in first post I've added some more documentation. Half were ready last night. I will make the rest finished in the weekend.

Share this post


Link to post
Share on other sites

#5 ·  Posted (edited)

Overview of the program progress

The illustration is an overview of the program sequence with regard to creating the support polygon with the mouse.

Program%20progress%201_zpscx3o9lnt.png

The next illustration shows the details of the creation of the oblique support lines.

Program%20progress%202_zpsw7nxtd3q.png

Note that all calculations here are in screen coordinates relative to the picture control.

The oblique support lines are stored in $aSupportLines. You can find a description of this array in top of SelectPolygon.au3.

The last illustration is creation of the final polygon which can be drawn with a single command: _GDIPlus_GraphicsDrawPolygon.

Program%20progress%203_zps0moflsxm.png

Calculations here are in image coordinates relative to the source image.

Edited by LarsJ

Share this post


Link to post
Share on other sites

#6 ·  Posted (edited)

Horizontal/vertical polygons along support lines

A support line is not allowed to be horizontal or vertical. It has to be oblique. This means that there are only 4 different types of support lines:

Horz-vert%20polygons%201_zpsu2ocowev.png

Two lines with positive slope (1 and 4) and opposite directions. Two lines with negative slope (2 and 3) and opposite directions. Note that on a screen the positive y-axis is from top to bottom.

The directions doesn't matter in regard to calculate the horz/vert polygons along the lines. But the polygons can be calculated on both sides of the lines. There are still 4 possibilities:

image7_zpsart3y7kb.png

The 4 horz/vert polygons are calculated in CalcHorzVertPolygon() in SelectPolygonFunctions2.au3. The function is separated into 4 sections, which calculates the polygon in each of the 4 situations. The code in the 4 sections are almost identical.

Each section starts with initialization code and ends with finalization code. In the middle is a small While loop of 20 lines of code. This loop performs the actual calculations - which are simple. This loop is pretty fast.

Even on an old XP a polygon like this is calculated and drawn immediately.

image8_zpsjtekmuqd.png

Adjustments of polygons near corner points

In the first illustration above there are 4 different types of support lines. If you combine two lines to form a corner point, there are 16 possibilities:

Horz-vert%20polygons%202_zpserh4i5od.png

The numbers refer to the first illustration. "2,1" in upper right corner means that the first line is situation 2 in first illustration, and the second line is situation 1 in first illustration.

Adjustments near corner points is done in AdjustHorzVertPolygons() in SelectPolygonFunctions2.au3. In a corner point the intersection between the two polygons is calculated, and the parts of the polygons on wrong side of intersection are cut off:

image9_zpsd620vpvm.png

The blue and red polygons have 3 intersections near the corner point numbered 3. In order to find the proper intersection the calculation starts at point 2 for the blue polygon, and at point 1 for the red polygon. The parts of the polygons on wrong side of intersection are cut off. The result is shown to the right.

Note that there is one pixel near point 3 which is entirely inside the triangle, and is not included in the selection. This is a consequence of the fact that the first intersection is used, whether there are more intersections or not.

In AdjustHorzVertPolygons() a Select statement is used to handle the 16 possible corner points. Each Case statement contains code to ensure that the calculation starts at the proper end of the polygons. And code to do optimizations. Then the intersection between the two polygons is calculated.

The calculation is done with 6 different functions, FindPolygonIntersectionN(), where N is a number 1 - 6. The 16 possible corner points in the illustration above are divided into 6 groups which matches the 6 functions.

Note that the code in the 16 Case statements are almost identical. And the code in the 6 functions are almost identical. The code in both Case statements and functions is very simple. This is important for speed.

In bottom of AdjustHorzVertPolygons() the parts of the polygons on wrong side of the intersection are cut off (CalcAdjustedPolygons), and the polygons (which now are adjusted in one end) are stored in $aSupportLines (StoreAdjustedPolygons).

For each polygon e.g. the blue polygon two polygons that are adjusted at opposite ends are stored in $aSupportLines.

The total adjusted polygon is formed by combining these two polygons. The half of each polygon that is not adjusted is cut away, and the two remaining halves are combined to form an overall adjusted polygon (CreateAdjustedPolygon).

The functions in SelectPolygonFunctions2.au3 are the most important functions of the entire program.

Optimizations

In order to perform the calculation of the intersection point between two polygons as quickly as possible, we can identify three types of optimizations:

  • 1) Do not recalculate intersection point and adjusted polygons, if no changes are applied to the two support lines for the specific corner point.
  • 2) Do not start the calculation further away than 12 horz/vert line segments from the corner point.
  • 3) Exclude line segments among these 12 segments, which cannot contain the intersection point.
The first optimization is handled in top of AdjustHorzVertPolygons(). When intersection point and adjusted polygons are calculated, a flag is set in $aSupportLines. When a recalculation is needed the flag is cleared. In top of AdjustHorzVertPolygons() it's checked if the flag is set. If this is the case the function returns immediately.

The second optimization is related to the minimum allowable angle between two support lines during validation of the support lines. This angle is set to 22.5 degrees. The number 12 is determined based on specific tests. First a test was done with only 8 line segments. This number was too small. Then a test was done with 12 line segments. This number was sufficient.

For a polygon like this only the line segments between the red marks and the blue end markers are included in the calculation of the intersection point.

image10_zpsah39wnfn.png

If the allowable angle is reduced to 15 degrees, the number of line segments must be increased to 16 or 20 depending on specific tests. When the angle between two support lines is small, there is less space for pixels (squares) between the lines. A pixel will be further away from the intersection of the support lines before there is space for an entire pixel.

The third optimization is seen in this illustration:

image13_zpsfuyazrei.png

To find the intersection between the blue and red polygons, 4 line segments for the blue polygon to the right of the vertical line can be excluded, because the x-values will definitely not match.

And 4 line segments for the red polygon above the horizontal line can be excluded, because the y-values will definitely not match.

Since the loops (outer and inner loop) to find the intersection starts in the ends of the polygons which is furthest away from the corner point, the intersection is found at first loop (both outer and inner loop run once), and rest of the loops are skipped. The search for intersection stops when the first intersection is found, whether there are more intersections or not.

Edited by LarsJ

Share this post


Link to post
Share on other sites

Very impressive work LarsJ  :thumbsup: .

 

Br,

UEZ

I totally agree with UEZ.

mLipok


Signature beginning:   Wondering who uses AutoIT and what it can be used for ?
* GHAPI UDF - modest begining - comunication with GitHub REST API *
ADO.au3 UDF     POP3.au3 UDF     XML.au3 UDF    How to use IE.au3  UDF with  AutoIt v3.3.14.x  for other useful stuff click the following button

Spoiler

Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind. 

My contribution (my own projects): * Debenu Quick PDF Library - UDF * Debenu PDF Viewer SDK - UDF * Acrobat Reader - ActiveX Viewer * UDF for PDFCreator v1.x.x * XZip - UDF * AppCompatFlags UDF * CrowdinAPI UDF * _WinMergeCompare2Files() * _JavaExceptionAdd() * _IsBeta() * Writing DPI Awareness App - workaround * _AutoIt_RequiredVersion() * Chilkatsoft.au3 UDF * TeamViewer.au3 UDF * JavaManagement UDF * VIES over SOAP * WinSCP UDF * GHAPI UDF - modest begining - comunication with GitHub REST API *

My contribution to others projects or UDF based on  others projects: * _sql.au3 UDF  * POP3.au3 UDF *  RTF Printer - UDF * XML.au3 - BETA * ADO.au3 UDF SMTP Mailer UDF *

Useful links: * Forum Rules * Forum etiquette *  Forum Information and FAQs * How to post code on the forum * AutoIt Online Documentation * AutoIt Online Beta Documentation * SciTE4AutoIt3 getting started * Convert text blocks to AutoIt code * Games made in Autoit * Programming related sites * Polish AutoIt Tutorial * DllCall Code Generator * 

Wiki: Expand your knowledge - AutoIt Wiki * Collection of User Defined Functions * How to use HelpFile * Best coding practices * 

IE Related:  * How to use IE.au3  UDF with  AutoIt v3.3.14.x * Why isn't Autoit able to click a Javascript Dialog? * Clicking javascript button with no ID * IE document >> save as MHT file * IETab Switcher (by LarsJ ) * HTML Entities * _IEquerySelectorAll() (by uncommon) * 

I encourage you to read: * Global Vars * Best Coding Practices * Please explain code used in Help file for several File functions * OOP-like approach in AutoIt * UDF-Spec Questions *  EXAMPLE: How To Catch ConsoleWrite() output to a file or to CMD *

"Homo sum; humani nil a me alienum puto" - Publius Terentius Afer
"Program are meant to be read by humans and only incidentally for computers and execute" - Donald Knuth, "The Art of Computer Programming"
:naughty:  :ranting:, be  :) and       \\//_.

Anticipating Errors :  "Any program that accepts data from a user must include code to validate that data before sending it to the data store. You cannot rely on the data store, ...., or even your programming language to notify you of problems. You must check every byte entered by your users, making sure that data is the correct type for its field and that required fields are not empty."

Signature last update: 2017-06-04

Share this post


Link to post
Share on other sites

Calculations related to zoom in/out issues

The illustration shows 4 pixels from an image. In the picture control the image is zoomed in to a factor 3. Each pixel is shown as a 3x3 square. The 2 pixels in the middle are not shown, but the width of the empty space matches 2 pixels. A support line is drawn between the two outermost pixels. The line starts in point (0,0) in the first square, and ends in point (2,2) in the last square.

Zoom%20in-out%203x3_zpsxninupsa.png

If the image is zoomed further in e.g. to a factor 8, which means that a pixel is shown as a 8x8 square, how should the support line then be drawn? How should the (0,0) and (2,2) points in the 3x3 squares be transferred to similar points in the 8x8 squares?

The next illustration shows how the line is drawn with the calculations in the functions in SelectPolygonFunctions1.au3.

Zoom%20in-out%208x8_zpsyxqpaocs.png

With these calculations the 9 points in a 3x3 square are transferred to a 8x8 square in this way:

3x3       8x8
 ---       ---
(0,0) --> (1,1)
(0,1) --> (1,3)
(0,2) --> (1,6)
(1,0) --> (3,1)
(1,1) --> (3,3)
(1,2) --> (3,6)
(2,0) --> (6,1)
(2,1) --> (6,3)
(2,2) --> (6,6)

(0,0) and (2,2) in zoom factor 3 are transferred to (1,1) and (6,6) in zoom factor 8.

The principle of the calculations is that the 8x8 square is divided into 9 equal sized squares. The 9 points in the 3x3 square are positioned in the middle of each of these squares. The coordinates in the 8x8 square are calculated as the integer part of the middle points.

Two functions in SelectPolygonFunctions1.au3 are used for the calculations: PointsInPixelsPerZoomLevel() and CalcAdjustDrawPolygonsOnMoveZoom().

For this example, where the original support line is drawn in the picture control with a zoom factor 3, PointsInPixelsPerZoomLevel() calculates how the two points (0,0) and (2,2) should be transferred to similar points for all 10 zoom levels: 1, 2, 3, 4, 6, 8, 12, 16, 24, 32. For zoom factor 8 the result are the two points (1,1) and (6,6). A total of 20 points are calculated and stored in a table: $aPointsInPixelsPerZoomLevel.

Such a table is created for each support line and is stored in $aSupportLines. The table is created when the support line is drawn and has passed validation without errors.

Using a table instead of calculating the points when you zoom in and out, ensures that the support line is always drawn in the same manner for a given zoom factor. That the points can be read in a table instead of being calculated is also important in regard to performance.

If you zoom in from factor 8 to 12 and back to 8 again, the line is drawn in the same way. If you zoom out from factor 8 to 6 and back to 8 again, the line is drawn in the same way.

When you zoom in/out CalcAdjustDrawPolygonsOnMoveZoom() extracts the points from the table for the current zoom level, and replaces the start/end points of the support line with these points. This is done for each support line. In the bottom of the function CalcAdjustDrawPolygons() is called, which draws the support lines and calculates/adjusts/draws the horz/vert polygons.

There is no guarantee that the horz/vert polygons looks exactly the same in different zoom levels. Only that they always looks the same for a given zoom level. This is a consequence of the fact that we are dealing with real physical pixels on a screen, and not infinite small points in a mathematical sense. It's not a matter of wrong calculations.

If the equation of a straight line is given by y = ax + b, where a is the slope, and b is the intersection with the y-axis, then both a and b will vary a little bit when you zoom in/out caused by integer calculations for pixels.

The problem is seen in this illustration:

image4_zps80w0ujqo.png

The original support triangle is drawn in the middle picture with a zoom factor of 24. Note the two points at the horz/vert polygons named 1 and 2.

At the left the zoom factor is 16 and the calculations yield different results near both points.

At the right the zoom factor is 32 and the calculations yield different results near point 1.

Share this post


Link to post
Share on other sites

#9 ·  Posted (edited)

Final polygon and selected pixels

In View mode the polygon of horz/vert line segments is drawn with a single command: _GDIPlus_GraphicsDrawPolygon. This command takes an array of polygon points as parameter. Points in the array must be in proper order.

The array is calculated in CreateFinalPolygon() in SelectPolygonFunctions1.au3. A lot of the code is about testing and sorting the order of the polygon points.

The points in a horz/vert polygon along a single oblique support line is of course in proper order. But there is no guarantee that the points in two consecutive polygons are in the same order.

At the intersection between two polygons the end point of the first polygon equals the start point of the last polygon. A point should not be stored twice in the array for _GDIPlus_GraphicsDrawPolygon.

In bottom of the function the bounding rectangle of the horz/vert polygon is calculated:

image1_zpsuf9sxgws.png

There are several purposes of the bounding rectangle:

  • Testing if a point is inside bounding rectangle is much easier and faster than testing if a point is inside the horz/vert polygon.
  • The polygons (both the horz/vert polygon and the oblique support polygon) are only drawn if a part of bounding rectangle is visible in picture control.
  • When selected pixels are calculated, the calculation is limited to bounding rectangle.
  • When a selection is copied and pasted, a new image is created with the size of bounding rectangle.
Force empty line after list

Selected pixels

In the illustration above there are 13 horizontal pixel lines in bounding rectangle. The selected pixels in a single horizontal line are the pixels between two consecutive vertical lines in the horz/vert polygon. Because the polygon is a proper closed polygon (if not it cannot be drawn with _GDIPlus_GraphicsDrawPolygon), the vertical line segments always occur in pairs of two segments. In the illustration there are either two or four vertical segments in each horizontal line.

The principle in GetSelectPolygonPixels() in SelectPolygonFunctions1.au3 is that the vertical segments are sorted by x-value and stored in an array. For the selection in the illustration an array of 13 lines and 4 columns is created. For pixel lines with two vertical segments only the first two columns are used.

If x0, x1, x2 and x3 are the x-values in the four columns for a given line, the selected pixels can be calculated as follows:

First  group of pixels: Start = x0, length = x1 - x0
Second group of pixels: Start = x2, length = x3 - x2
Edited by LarsJ

Share this post


Link to post
Share on other sites

An issue

The picture to the left in the illustration shows the issue:

10_zpsip9lnqdn.png

There is no intersection between the two horz/vert polygons, when the corner point of the support lines is located exactly on a grid line, and when the polygons are on the outer side of the corner point.

The problem here is on the vertical grid line. The reason why the corner point is positioned where the grid lines are crossing is only, that it's easier to reproduce the problem. To reproduce the problem you have to be very careful about the position of the three points.

In Scite console you'll see the following error messages:

Error: No intersection for line 0 and 1
Error: No adjusted polygon for line = 0
Error: No adjusted polygon for line = 1

If x is the x-value of the grid line and the corner point, then a calculation of x along the upper support line results in a value that's slightly bigger than x (e.g. x + 0.0001). According to this calculation the corner point is on the right side of the grid line, and the pixel/square to the right of the grid line is included.

A calculation of x along the lower support line results in a value that's slightly smaller than x (e.g. x - 0.0001). According to this calculation the corner point is on the left side of the grid line, and the pixel/square to the right of the grid line is not included.

The problem is, that under some specific circumstances the horz/vert polygons gets too short to create an intersection. This is also the reason why you only see the problem on the outer side of the corner point (the long way around the corner point).

Workaround

If you have been drawing a support polygon or zoomed in/out, and suddenly seen that the horz/vert polygons along two support lines are missing, this issue is the most likely cause of the problem.

Because the issue only appears under specific circumstances (corner point exactly on grid line, values of slopes of support lines that results in calculations of x or y on both sides of the grid line), an easy workaround is to move (shift + drag) the corner point a few pixels. Then these specific circumstances are no longer fulfilled, and the polygons are calculated properly.

Solution

The left picture shows also how to fix the problem: If the first and last line segment of the blue and red polygons are increased with one pixel/square there will be an intersection. This is shown in the middle picture.

The picture to the right shows the adjusted polygons. You clearly sees that both the upper and lower horizontal line segments are increased with one pixel/square compared to the left picture.

Reproduce issue

The easiest way to reproduce the issue is to create a selection like this with many support lines:

11_zpsum9shrtt.png

Note that all start/end points of the oblique support lines are positioned where grid lines are crossing. Note also that the horz/vert polygons are on the outside of the oblique polygon.

If you zoom out several times one by one, the slopes of the oblique lines will change a little bit. Sooner or later the calculations will result in polygons, that are too short to create an intersection.

New zip

I have added a new zip to first post where the issue is fixed. So far I have not deleted the old zip.

The function CalcAdjustDrawPolygons() in top of SelectPolygonFunctions2.au3 checks the issue. IncreasePolygonStartEndLines() is called in case of a problem. It increases the start and end line of the horz/vert polygon with one pixel/square.

In Scite console you'll see these messages:

Error: No intersection for line 0 and 1
Intersection found after extension of polygons

In SelectPolygon.au3 a new flag is added to ensure that a polygon isn't increased more than once.

Share this post


Link to post
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