Maths puzzle Topic is solved

Get help with using AutoHotkey and its commands and hotkeys
mast4rwang
Posts: 65
Joined: 19 Jul 2017, 09:59

Maths puzzle

21 Nov 2017, 06:45

Hello, I have a really tough assignment to solve. Please help me someone! :headwall:

Task: There is a given area of squares. The size of the area may vary (in the example below we have 11x10 squares, 110 in total). The squares are always numbered from top to down. Each square is 50x50 pixels. Make a script which lists an array of squares, which are crossed by the line connecting two dots placed on chosen coordinates.
Image

I don't even know where to start to solve this :headwall:

Code: [Select all] [Expand] [Download] GeSHi © Codebox Plus

Last edited by mast4rwang on 21 Nov 2017, 12:55, edited 1 time in total.
User avatar
Exaskryz
Posts: 2690
Joined: 17 Oct 2015, 20:28

Re: Maths puzzle

21 Nov 2017, 07:54

This may not be the most efficient way, and I have not tested it in AHK.

Edit: I had to double check my numbers, and I had them wrong initially. Also, the points you gave in the little code box for dotAx and dotAy don't match the diagram above, so we shouldn't use the red AB line you drew to check my answer.

So if A is at (200,200) and B is at (300,450), what we do is calculate a slope. Rise over Run -- That's the ΔY/ΔX. (450-200)/(300-200). So that's 250/100 = 2.5. What's odd about this slope number is because the Y-axis values are inverted, a positive value for the slope here means it slants down from left to right. In grade school you'd think of a positive slope as increasing from left to right, not the case here. I don't know for sure, but I believe the math will all work out anyway. It's an arbitrary distinction which direction the Y axis is going in.

So you want an equation for the line. y=mx+b, essentially. We just found out m, the slope. Now we need b. Let's use coordinate A for the X and Y. 200 = 2.5(200) + b. 200 = 500 + b. b = -300.

Our line equation is y = 2.5x - 300. Now we just need to loop through all the x values and find their y's. Just quickly doing it for a few sample points:

200, 200
220, 250
240, 300
260, 350
280, 400
300, 450

So what do we do with this? Take the X value and find the column it's in. We do this with division by 50, in fact, ceiling should work to round to the correct whole number; we round up so a coordinate of (1,3) would get divided by 50 (something close to 0) and then rounded up to 1. Let's take point 3 for instance. 240/50 = 4.8 ; Ceil(240/50) = 5. We know we're in the 5th column. This means it's 41-50. Algebraically, you want to get to 41. This is done with column (the 5) minus 1, times by 10, add 1. topcell:=(column-1)*10+1 will be 41 when column variable is 5.

We want to start at the top cell because we'll essentially create an offset to get into the correct row. This is done with the Y value. Again, divide by 50 and Ceiling it. 300/50 = 6; Ceil(300/50) = 6. We want the 6th row, which is 5 below the top cell. So do targetcell:=topcell+row-1. This should give the result of 46. Cool, we're almost there.

We do that same process on all the points. Stick each result into an array, or a long string, and we remove the duplicates. If an array, see the first few posts of this thread (it veers off topic): https://autohotkey.com/boards/viewtopic.php?f=5&t=39697 If it's a long string, you can use the Sort command which can remove duplicates for you.

That should give you the answer you need.

You might need to worry about the exact definition of borders though. Are the coordinates a 0-based in your grid? Or are they 1-based? That is, is the top left corner (0,0) or is it (1,1)? If it's 0,0, then the bottom-right corner of the first cell is (49,49); the cell diagonally down and right from it would be (50,50) to (99,99). But if it's 1-based, then coordinates are (1,1) to (50,50) and (51,51) to (100,100). My math assumes it's in 1 base I believe, because I said that the 300//50 = 6th row; If it's 0-based, the Y ranges for each row would be 0-49, 50-99, 100-149, 150-199, 200-249, 250-299, 300-349. Which is actually the 7th row.
User avatar
jeeswg
Posts: 3000
Joined: 19 Dec 2016, 01:58
Location: UK

Re: Maths puzzle

21 Nov 2017, 10:55

- The thing I find useful with this kind of question is this:
- Imagine a horizontal line, underneath the diagonal line, and for each pixel of that horizontal line, get a vertical coordinate in the diagonal line.
- Alternatively, imagine a vertical line, left of the diagonal line, and for each pixel of that vertical line, get a horizontal coordinate in the diagonal line.
- And by one or other of those approaches you acquire a list of coordinates for the diagonal line.
- In my example, I use the horizontal line approach, the X value increases by 1 each time, and the Y value increases by a set amount each time.
- Then you convert the point coordinates to square coordinates by dividing by 50, and you convert those to the square number.

- As Exaskryz mentioned, is this 0-based or 1-based, if we call the top-left point (0,0) then square 1 is (0,0) to (49,49). If we call the top-left point (1,1) then square 1 is (1,1) to (50,50): and so we'd have to subtract 1 before dividing by 50.
- Also as he mentioned, things can be a bit fiddly with whether you consider going downwards as positive or negative.

Here's an attempt at a script.

Code: [Select all] [Expand] [Download] GeSHi © Codebox Plus

mast4rwang
Posts: 65
Joined: 19 Jul 2017, 09:59

Re: Maths puzzle

21 Nov 2017, 12:44

This is even more complex than I imagined, sorry for being not precise.

Starting coordinates are [0:0] and it is enough to calculate for 1 line - I want to understand the script and can later add more lines if I get such task :D Also the start of my script is not related to the example values. It is supposed to be random dots on random sized area, so the most correct starting coordinates in the script could look like this:

Code: [Select all] [Expand] [Download] GeSHi © Codebox Plus



And to test it if it works we could use coordinates like 25;25 and 25;490. That way we would see if the script works when we get values 1,2,3,4,5,6,7,8,9,10. I tried it with @jeeswg script but it doesn't work with other coordinates :(
FanaticGuru
Posts: 802
Joined: 30 Sep 2013, 22:25

Re: Maths puzzle  Topic is solved

22 Nov 2017, 19:06

This was an interesting puzzle.

I approached it from pure geometry math.

Each cell is defined by 4 line segments. So to determine if a transecting line segment intersects any cell you need only to determine if it intersects with any of those 4 line segments.

The below script not only finds all the cells intersected but also the point XY information of where all the intersections occur.

Code: [Select all] [Expand] [Download] (Untitled.ahk)GeSHi © Codebox Plus

The function LineSeg_Intersection might be useful for other uses so I commented it some.

The toughest part for me was the handling of collinear line segments where the segments overlap. The functions LineSeg_Point and Point_Orientation were needed for that. There is probably a better way than looking for each line segment's end points on the other line segment but at the time I thought about returning the overlapping line segment but it made the return object a little cumbersome.

The main function Cells_Intersected allows for any number of columns and rows as well as the ability to set the size of each cell.

I put some example lines that were horizontal and vertical that also fell exactly on the grid line. Those could be problem cases for some solutions.

I had to go out on the internet and study geometry math. I was surprised not to find definitive perfect code out there for how to find the intersection of line segments. Lots of code but many that don't always work. Some fail on parallel lines, some fail on collinear line segments that overlap, some fail on collinear line segments that don't overlap, line segments that intersect at end points, etc.

There might be ways I could simply the algorithms and variables. Handling the points and line segments as objects would probably help to keep all the variables more clear but I was just happy to get it to work. Makes me want to brush up more on my geometry math.

Edit: Added my version of Min/Max functions. Forgot they were not standard AHK functions.

FG
Last edited by FanaticGuru on 23 Nov 2017, 01:02, edited 1 time in total.
Hotkey Help - Help Dialog for Currently Running AHK Scripts

AHK Startup - Consolidate Multiply AHK Scripts with one Tray Icon

Google Search, Dictionary, Thesaurus - Quickly Get Information from Specific Web Resources

[Function] Timer - Create and Manage Timers
Helgef
Posts: 2478
Joined: 17 Jul 2016, 01:02
Contact:

Re: Maths puzzle

22 Nov 2017, 19:27

Nice, FanaticGuru. I took the same approach, that is to check intersections with square borders. I didn't finish it though, still need to handle the vertical line case, yours does I see, very well done. If you want to compare, also, you didn't include min/max functions.
I did it for v2, but I think its ok in v1 if you adjust the msgbox() function :lol:. It doesn't matter for the logic

Code: [Select all] [Expand] [Download] GeSHi © Codebox Plus


I intended mine to work for squares with different sides, not tested.
FanaticGuru
Posts: 802
Joined: 30 Sep 2013, 22:25

Re: Maths puzzle

23 Nov 2017, 01:30

Helgef wrote:Nice, FanaticGuru. I took the same approach, that is to check intersections with square borders. I didn't finish it though, still need to handle the vertical line case, yours does I see, very well done. If you want to compare, also, you didn't include min/max functions.
I did it for v2, but I think its ok in v1 if you adjust the msgbox() function :lol:. It doesn't matter for the logic

I intended mine to work for squares with different sides, not tested.

Definitely interested in comparing your code and seeing how others do the geometry math.

Forgot that Min/Max are not standard functions. Hazards of using a library. I forget what is in it.

Had to change MsgBox, If, and Loop to get your code to work in v1.

I also thought about allowing rectangular cells instead of just squares. Would be pretty trivial in my code to breaking the Size variable into two variables.

FG
Hotkey Help - Help Dialog for Currently Running AHK Scripts

AHK Startup - Consolidate Multiply AHK Scripts with one Tray Icon

Google Search, Dictionary, Thesaurus - Quickly Get Information from Specific Web Resources

[Function] Timer - Create and Manage Timers
mast4rwang
Posts: 65
Joined: 19 Jul 2017, 09:59

Re: Maths puzzle

23 Nov 2017, 05:29

@FanaticGuru

Your script works perfectly with several tests I made! :!:
mast4rwang
Posts: 65
Joined: 19 Jul 2017, 09:59

Re: Maths puzzle

06 Dec 2017, 09:05

FanaticGuru wrote:This was an interesting puzzle.
I approached it from pure geometry math.

Each cell is defined by 4 line segments. So to determine if a transecting line segment intersects any cell you need only to determine if it intersects with any of those 4 line segments.

The below script not only finds all the cells intersected but also the point XY information of where all the intersections occur.
Spoiler
The function LineSeg_Intersection might be useful for other uses so I commented it some.

The toughest part for me was the handling of collinear line segments where the segments overlap. The functions LineSeg_Point and Point_Orientation were needed for that. There is probably a better way than looking for each line segment's end points on the other line segment but at the time I thought about returning the overlapping line segment but it made the return object a little cumbersome.

The main function Cells_Intersected allows for any number of columns and rows as well as the ability to set the size of each cell.

I put some example lines that were horizontal and vertical that also fell exactly on the grid line. Those could be problem cases for some solutions.

I had to go out on the internet and study geometry math. I was surprised not to find definitive perfect code out there for how to find the intersection of line segments. Lots of code but many that don't always work. Some fail on parallel lines, some fail on collinear line segments that overlap, some fail on collinear line segments that don't overlap, line segments that intersect at end points, etc.

There might be ways I could simply the algorithms and variables. Handling the points and line segments as objects would probably help to keep all the variables more clear but I was just happy to get it to work. Makes me want to brush up more on my geometry math.

Edit: Added my version of Min/Max functions. Forgot they were not standard AHK functions.

FG



Your formula from the other thread made this puzzle so easy to solve man, look at how I did it:

Code: [Select all] [Expand] [Download] GeSHi © Codebox Plus




Cheers! :xmas:
FanaticGuru
Posts: 802
Joined: 30 Sep 2013, 22:25

Re: Maths puzzle

06 Dec 2017, 13:55

mast4rwang wrote:Your formula from the other thread made this puzzle so easy to solve man, look at how I did it:

Code: [Select all] [Expand] [Download] GeSHi © Codebox Plus




Cheers! :xmas:
This is taking a more graphically than mathematically approach.

It is important to realize this is only an approximation and is not mathematically accurate.

For example if you use these parameters:

Code: [Select all] [Download] (Untitled.ahk)GeSHi © Codebox Plus

accuracy:=5		;accuracy in pixels
tilew:=50 ;tile width in pixels
mapX:=550 ;grid length in pixels
mapY:=500 ;grid length in pixels
lx:=120 ;start coordinates
ly:=40 ;start coordinates
px:=280 ;goal coordinates
py:=460 ;goal coordinates
Which is your example AB line from original post.

This code will not catch cells 36 and 45 as posted results would expect. Because the AB line goes exactly through the corner point of those two cells. This code does not catch either one of those cells as it basically jumps over that vertex. Just looking at the picture logic would tell you that the line has to touch one or both of those cells to transect across that area. Looking at the expected results you know it has to exactly cross the corner vertex as that is the only point the two cells have in common.

FG
Hotkey Help - Help Dialog for Currently Running AHK Scripts

AHK Startup - Consolidate Multiply AHK Scripts with one Tray Icon

Google Search, Dictionary, Thesaurus - Quickly Get Information from Specific Web Resources

[Function] Timer - Create and Manage Timers
mast4rwang
Posts: 65
Joined: 19 Jul 2017, 09:59

Re: Maths puzzle

06 Dec 2017, 17:01

FanaticGuru wrote:
mast4rwang wrote:Your formula from the other thread made this puzzle so easy to solve man, look at how I did it:

Code: [Select all] [Expand] [Download] GeSHi © Codebox Plus




Cheers! :xmas:
This is taking a more graphically than mathematically approach.

It is important to realize this is only an approximation and is not mathematically accurate.

For example if you use these parameters:

Code: [Select all] [Download] (Untitled.ahk)GeSHi © Codebox Plus

accuracy:=5		;accuracy in pixels
tilew:=50 ;tile width in pixels
mapX:=550 ;grid length in pixels
mapY:=500 ;grid length in pixels
lx:=120 ;start coordinates
ly:=40 ;start coordinates
px:=280 ;goal coordinates
py:=460 ;goal coordinates
Which is your example AB line from original post.

This code will not catch cells 36 and 45 as posted results would expect. Because the AB line goes exactly through the corner point of those two cells. This code does not catch either one of those cells as it basically jumps over that vertex. Just looking at the picture logic would tell you that the line has to touch one or both of those cells to transect across that area. Looking at the expected results you know it has to exactly cross the corner vertex as that is the only point the two cells have in common.

FG


Is it because maths limitation or because I jump several pixels while checking instead of 1? Btw, what would you do to make this script faster? I am looking forward to using it with many other functions in a loop which runs with sleep,1 :?
FanaticGuru
Posts: 802
Joined: 30 Sep 2013, 22:25

Re: Maths puzzle

06 Dec 2017, 19:16

mast4rwang wrote:Is it because maths limitation or because I jump several pixels while checking instead of 1? Btw, what would you do to make this script faster? I am looking forward to using it with many other functions in a loop which runs with sleep,1 :?
It is a math limitation of your code. It is not really about pixels. The grid is defined by math and even if you make your precision variable 1 or .1 or .001, you are not going to hit that vertex exactly. You might be able to add in a fuzziness so that it you get close enough to a cell you are assumed to have intersected it but that is also prone to error in some cases where you really did just barely miss a cell.

There probably is a fuzziness that would give the correct results as long as the coordinates were whole numbers and the max grid size is known.

Cases like a line from 0,49 to 500,51. This line is going to come very close to a lot of cells but will cross the 50 grid line at only one point.

The fuzziness that made those points give the correct solution work would not necessarily work for a line segment from 0,49 to 5000000,51. This very small precision number need for this example will result in a lot of looping in your code.

FG
Last edited by FanaticGuru on 06 Dec 2017, 20:56, edited 1 time in total.
Hotkey Help - Help Dialog for Currently Running AHK Scripts

AHK Startup - Consolidate Multiply AHK Scripts with one Tray Icon

Google Search, Dictionary, Thesaurus - Quickly Get Information from Specific Web Resources

[Function] Timer - Create and Manage Timers
User avatar
jeeswg
Posts: 3000
Joined: 19 Dec 2016, 01:58
Location: UK

Re: Maths puzzle

06 Dec 2017, 19:19

Depending on definitions, a point on a corner might be considered as intersecting 4 squares.
FanaticGuru
Posts: 802
Joined: 30 Sep 2013, 22:25

Re: Maths puzzle

06 Dec 2017, 20:50

jeeswg wrote:Depending on definitions, a point on a corner might be considered as intersecting 4 squares.

Yes, but two of the cells (squares) will be caught by his code as the line travels through two of the cells and intersects the cells' area in many point that he checks (35 and 46 for example) but two of the cells will only be intersected by the line at exactly one point (36 and 45 for example) and it is unlikely the code will check at that exact point and will almost definitely miss this exact point and there by miss that the line intersected those two cells (36 and 45).

Lines that are exactly orthogonal along a grid line are their own problem, unless you are careful with your if/thens you will only get cells along one side of the line and not both.

That is why I took a pure geometry math approach. It is some what complicated but very accurate within the limitations of floating point numbers. If you were really doing precise calculations, you would need to put a fuzziness in even my code to compensate for the inaccuracy of floating point numbers at extremes. Basically if two floating point numbers were close enough you would assume they were equal.

FG
Hotkey Help - Help Dialog for Currently Running AHK Scripts

AHK Startup - Consolidate Multiply AHK Scripts with one Tray Icon

Google Search, Dictionary, Thesaurus - Quickly Get Information from Specific Web Resources

[Function] Timer - Create and Manage Timers
mast4rwang
Posts: 65
Joined: 19 Jul 2017, 09:59

Re: Maths puzzle

07 Dec 2017, 03:58

I noticed it about precision but I also noticed that ahk itself is not precise. For example I typed 49.999999 and it treated it as 50.
So now I want just to optimize its speed as much as possible even if loosing some precision 8-)

Return to “Ask For Help”

Who is online

Users browsing this forum: Odlanir and 53 guests