mIRC Home    About    Download    Register    News    Help

Print Thread
Page 1 of 2 1 2
#262736 25/03/18 03:00 AM
Joined: Dec 2002
Posts: 252
T
Talon Offline OP
Fjord artisan
OP Offline
Fjord artisan
T
Joined: Dec 2002
Posts: 252
a Previous forum bug post back in 2004 for $onpoly() can be read here about dealing with polygons with zero volume.

I'm not sure if $onpoly() by design is supposed to only report if two polygons overlap on any of the linesegments that connect the dots intersect, or also include if a polygon is completely within another polygon without any intersections.

I assumed onpoly was supposed to treat one within another as overlapping. As is now, onpoly only returns true if a polygon inside another polygon has volume. I've setup a simple script to demonstrate these cases.

If this way is wrong, and it's a bug for a polygon to report true if it's completely contained inside another polygon, maybe we need an $insidepoly() test case or a .inside prop for $onpoly()? Can't be $inpoly() since this already exists and is for if a point is within a defined polygon...

I'd actually prefer it if it returned true for these cases for my usage, because in all reality the polygon in question is on the surface of another polygon. To me, two polygons overlap if ANY points within the surface (including it's permiter) of each polygon share the same space. I spent hours debugging a project to find out it's $Onpoly() and not my code smile

Although the simplest solution here is to just check if both endpoints are inside the polygon, this introduces heavy latency, especially with large polygon definitions because now I have to test the same polygon 3 times. once to see if it returns false with $onpoly(), once to see if endpoint A is within $inpoly(), and once to see if endpoint B is within $inpoly().

Definitions about colors here suggest you have'nt altered your mIRC's color pallettes in alt+k, if you have, these distinctions by color may not make sense to you.

If you start up "/onpolytest" when you move the mouse, it tells you if two polygons overlap, and highlights the polygon in orange. It then tries to break down the polygon and report which line segments (polygons with zero volume) are causing the overall polygon to return true.

Points within a polygon are highlighted in green, and linesegments are highlighted in red to show what regions are affected.

Since mIRC is NOT reporting a lineseg polygon as overlapping when it's completely contained within the polygon, these are highlighted in yellow.

Move your mouse around the default test case, and test a "short line" that fits within the mouse's polygon to illustrate.

Furthermore to illustrate that this onpoly test fails, you can right click and change the "Mouse" polygon to line, and put it within the bounds of the main polygon, and the main polygon will NEVER highlight in orange.

You can also test other polygons by changing either the Poly, or the Mouse poly in the right click dropdown menu.

Code:
menu @OnPolyTest {
  mouse {
    var %hw = $window($active).dw / 2 , %hh = $window($active).dh / 2
    var %x = $mouse.x - %hw , %y = $mouse.y - %hh

    tokenize 32 $window($active).title
    var %Poly = $1 , %Mouse = $2

    var %Polygon = $OPT.TranslatePolygon($OPT.Polygons(%Poly),0,0,0,2) , %P44 = $regsubex(%Polygon,/\s/g,$chr(44))
    var %PolyClosed = %Polygon $gettok(%Polygon,1-2,32)
    var %PCount = $numtok(%Polygon,32) , %Points = %PCount / 2    

    var %Cursor = $OPT.TranslatePolygon($OPT.Polygons(%Mouse),0,%x,%y,2) , %C44 = $regsubex(%Cursor,/\s/g,$chr(44))
    var %CCount = $numtok(%Cursor,32) , %CPoints = %CCount / 2    

    .onpolytest
    if ($onpoly(%CPoints,%Points, [ %C44 ] , [ %P44 ] )) {
      drawtext -n $active 0 0 0 *** Bounding Box on polygon
      var %np = $OPT.TranslatePolygon(%Polygon,0,%hw,%hh)
      drawline -n @OnpolyTest 7 1 %np $gettok(%np,1-2,32)

      var %c = 1 , %d = 4
      while (%c <= %PCount) {
        var %Seg = $gettok(%PolyClosed,$+(%c,-,%d),32)
        tokenize 32 %Seg
        if ($onpoly(%CPoints,2, [ %C44 ] , [ $regsubex($1-,/\s/g,$chr(44)) ] )) { drawline -n @OnPolyTest 4 1 $regsubex($1-,/([^ ]+) ([^ ]+)/g,$calc(\1 + %hw) $calc(\2 + %hh)) }
        elseif ($inpoly($1,$2, [ %C44 ] ) || $inpoly($3,$4, [ %C44 ] )) { drawline -n @OnPolyTest 8 3 $regsubex($1-,/([^ ]+) ([^ ]+)/g,$calc(\1 + %hw) $calc(\2 + %hh)) }

        if ($inpoly($1,$2, [ %C44 ] )) { drawdot -n @OnPolyTest 3 4 $calc($1 + %hw) $calc($2 + %hh) }
        if ($inpoly($3,$4, [ %C44 ] )) { drawdot -n @OnPolyTest 3 4 $calc($3 + %hw) $calc($4 + %hh) }
        var %c = %c + 2 , %d = %d + 2
      }
    }
    drawdot @OnPolyTest
  }
  Polygon
  .Box:opt.changepoly 1 box
  .largeRock1:opt.changepoly 1 largeRock1
  .largeRock2:opt.changepoly 1 largeRock2
  .largeRock3:opt.changepoly 1 largeRock3
  .medRock1:opt.changepoly 1 medRock1
  .medRock2:opt.changepoly 1 medRock2
  .medRock3:opt.changepoly 1 medRock3
  .smallRock1:opt.changepoly 1 smallRock1
  .smallRock2:opt.changepoly 1 smallRock2
  .smallRock3:opt.changepoly 1 smallRock3
  Mouse
  .line:opt.changepoly 2 line
  .Box:opt.changepoly 2 box
  .largeRock1:opt.changepoly 2 largeRock1
  .largeRock2:opt.changepoly 2 largeRock2
  .largeRock3:opt.changepoly 2 largeRock3
  .medRock1:opt.changepoly 2 medRock1
  .medRock2:opt.changepoly 2 medRock2
  .medRock3:opt.changepoly 2 medRock3
  .smallRock1:opt.changepoly 2 smallRock1
  .smallRock2:opt.changepoly 2 smallRock2
  .smallRock3:opt.changepoly 2 smallRock3
}
alias onpolytest {
  if (!$window(@OnPolyTest)) { 
    window -dpf @OnPolyTest -1 -1 640 480 
    titlebar @OnPolyTest largeRock1 box
  }
  tokenize 32 $window(@OnPolyTest).title
  var %Poly = $1 , %Mouse = $2
  var %w = $window(@OnPolyTest).dw , %h = $window(@OnPolyTest).dh , %hw = %w / 2 , %hh = %h / 2
  drawrect -nf @OnPolytest 1 1 0 0 %w %h
  var %Poly = $OPT.TranslatePolygon($OPT.Polygons(%Poly),0,%hw,%hh,2)
  drawline -n @OnpolyTest 0 1 %poly $gettok(%poly,1-2,32)

  var %poly = $OPT.TranslatePolygon($OPT.Polygons(%Mouse),0,$Mouse.x,$Mouse.y,2)
  drawline -n @OnpolyTest 0 1 %poly $gettok(%poly,1-2,32)
  if ($show) { drawdot @OnPolyTest }
}
alias -l OPT.changepoly {
  var %target = $1 , %val = $2
  tokenize 32 $window(@OnPolyTest).title
  var %Poly = $1 , %Mouse = $2
  if (%target = 1) { %Poly = %val }
  else { %Mouse = %val }
  titlebar @OnPolyTest %Poly %Mouse
}
alias -l OPT.Polygons {
  if ($1 = line) { return -10 0 10 0 }
  if ($1 = box) { return -10 -10 10 -10 10 10 -10 10 }
  if ($1 = largeRock1) { return -39 -25 -33 -8 -38 21 -23 25 -13 39 24 34 38 7 33 -15 38 -31 16 -39 -4 -34 -16 -39 }
  if ($1 = largeRock2) { return -32 35 -4 32 24 38 38 23 31 -4 38 -25 14 -39 -28 -31 -39 -16 -31 4 -38 22 }
  if ($1 = largeRock3) { return 12 -39 -2 -26 -28 -37 -38 -14 -21 9 -34 34 -6 38 35 23 21 -14 36 -25 }
  if ($1 = medRock1) { return -7 -19 -19 -15 -12 -5 -19 0 -19 13 -9 19 12 16 18 11 13 6 19 -1 16 -17 }
  if ($1 = medRock2) { return 9 -19 18 -8 7 0 15 15 -7 13 -16 17 -18 3 -13 -6 -16 -17 }
  if ($1 = medRock3) { return 2 18 18 10 8 0 18 -13 6 -18 -17 -14 -10 -3 -13 15 }
  if ($1 = smallRock1) { return -8 -8 -5 -1 -8 3 0 9 8 4 8 -5 1 -9 }     
  if ($1 = smallRock2) { return -6 8 1 4 8 7 10 -1 4 -10 -8 -6 -4 0 }
  if ($1 = smallRock3) { return -8 -9 -5 -2 -8 5 6 8 9 6 7 -3 9 -9 0 -7 }
}
alias -l OPT.TranslatePolygon {  
  var %dx = $cos($2).deg , %dy = $sin($2).deg , %ox = $3 , %oy = $4 , %scale = $iif($5,$5,1)
  return $regsubex($1,/([^ ]+) ([^ ]+)/g,$calc(((\1 * %dx + \2 * (%dy * -1)) * %scale) + %ox) $calc(((\1 * %dy + \2 * %dx) * %scale) + %oy))
}




Joined: Dec 2002
Posts: 252
T
Talon Offline OP
Fjord artisan
OP Offline
Fjord artisan
T
Joined: Dec 2002
Posts: 252
Here's the issue visualized:

outside works correctly..


Illustrating not finding a polygon inside another with 0 volume:


Inside working for polygon with volume:


Edge cases working correctly with polys with 0 volume:


again illustrating not finding a poly inside a poly if one has zeo volume:

Joined: Dec 2002
Posts: 5,411
Hoopy frood
Offline
Hoopy frood
Joined: Dec 2002
Posts: 5,411
Thanks for your bug report. I was able to reproduce this issue. It is due to how $onpoly() uses windows regions to determine if polygons are overlapped. A zero area polygon results in an empty combined region which means it cannot be detected using this method. I would need to extend $onpoly() to perform the the end point tests you mentioned specifically to detect this case. This should be in the next beta.

Joined: Dec 2002
Posts: 5,411
Hoopy frood
Offline
Hoopy frood
Joined: Dec 2002
Posts: 5,411
I have re-implemented this feature using two methods: one method still uses regions but checks for endpoints, and the other method avoids using regions entirely. Both methods seem to be working correctly, using your test script, however both methods break your yellow line segment check. Is it possible that the yellow line segment check is based on the current behaviour in v7.52?

Update: on second thought, it might just be easier to release a beta with this change for you to try out :-)

Last edited by Khaled; 26/03/18 05:42 PM.
Joined: Dec 2002
Posts: 252
T
Talon Offline OP
Fjord artisan
OP Offline
Fjord artisan
T
Joined: Dec 2002
Posts: 252
Right, I implemented the yellow just to show the behavior of 7.52 failing and highlighting the fail.

If it's fixed, edge case tests, what once was yellow should now be red, and yellow shouldn't ever happen. (as long as there's an intersection, or it's completely contained within the mouse poly.)

For the last test image, If the mouse poly is lineseg, and completely contained without intersections, the whole polygon should become orange now instead of staying white. (not the mouse poly, mouse poly is always white)

Last edited by Talon; 26/03/18 08:17 PM.
Joined: Dec 2002
Posts: 252
T
Talon Offline OP
Fjord artisan
OP Offline
Fjord artisan
T
Joined: Dec 2002
Posts: 252
I'd love to test out the new beta with these features too, hopefully with both versions in-tact. Let's call them $onpoly() and $onpoly2() It would be interesting to do a speed comparison between both methods, the windows region, and the purely mathematical solution.

I'd assume the windows region method was an earlier method back in the day to circumvent speed issues of doing it purely mathematically. With advancements in processors and their ability to handle mathematics faster, this might now be moot, it may either perform the same, or worse using windows regions smile

Joined: Dec 2002
Posts: 5,411
Hoopy frood
Offline
Hoopy frood
Joined: Dec 2002
Posts: 5,411
The math/region implementations run at about the same speed. However, the region method is now slower for situations were polygons do not overlap because it has to perform extra endpoint checks for zero area polygons. So, overall, the math version is better.

Joined: Dec 2002
Posts: 252
T
Talon Offline OP
Fjord artisan
OP Offline
Fjord artisan
T
Joined: Dec 2002
Posts: 252
Running the new beta, $onpoly() seems to be 100% correct!

The bad news is: $inpoly() is now causing false positives and giving me points that aren't within the mouse's polygon.

Here's a picture of the issue:


Not sure if this helps, but the checks are in grid coordinates, not picwin surface coordinates, so all these checks happen on points a distance away from the origin [0,0] Which gave me the idea, it's almost as if it happens when the absolute value $abs(x & y) would happen to fall inside the mouse's polygon, as the absolute value would be a mirror of where it's at if you think of the center of the screen being [0,0]. it doesn't seem quite perfect for the answer to what's happening but it's close on getting the error to show, especially following around the right-most side of the larger polygon.

Last edited by Talon; 31/03/18 02:38 AM.
Joined: Dec 2002
Posts: 5,411
Hoopy frood
Offline
Hoopy frood
Joined: Dec 2002
Posts: 5,411
Quote:
Running the new beta, $onpoly() seems to be 100% correct!

The bad news is: $inpoly() is now causing false positives and giving me points that aren't within the mouse's polygon.

I noticed this as well when testing your script. However, as $inpoly() is now using the same math routine as $onpoly(), I assumed this was due to your script depending on the previous behaviour. Also, $inpoly() was working correctly in my tests.

I just compared $inpoly() and $onpoly() and it turns out that $onpoly() has some extra code that adjusts the provided polygon to prepare it for use eg. it extends the polygon if it is not completely closed. I have added this code to $inpoly() and am no longer seeing the yellow lines when running your script. This change will be in the next beta.

Joined: Dec 2002
Posts: 252
T
Talon Offline OP
Fjord artisan
OP Offline
Fjord artisan
T
Joined: Dec 2002
Posts: 252
Ah, awesome smile I was used to the old $onpoly() and $inpoly() and had issues with passing fully closed polygons so I always assumed it required a clockwise or counter-clockwise point definition, and not contain any identical points, so it's last check with the last points would be a segment between the last point passed, and the very 1st point passed completing the polygon.

I thought this was by design, so none of my polygons are fully closed, due to the behavior of the old methods. You can see this when I draw the polygons to the screen, I pass the polygon to drawline with also adding the very 1st point from the polygon so drawline draws a completed polygon.

Example:
drawline -n @OnpolyTest 0 1 %poly $gettok(%poly,1-2,32)

Joined: Dec 2002
Posts: 5,411
Hoopy frood
Offline
Hoopy frood
Joined: Dec 2002
Posts: 5,411
Okay, I have just released a new beta that should fix this. If you notice any other issues, let me know.

Joined: Dec 2002
Posts: 252
T
Talon Offline OP
Fjord artisan
OP Offline
Fjord artisan
T
Joined: Dec 2002
Posts: 252
It's close, but still not quite right. Using the mouse polygon "line" and testing some edge cases it misses completely, and now lineseg-to-lineseg doesn't work around the edges, none highlight red if the mouse is "line".

Rather than posting more images illustrating the failures, here's my current purely mSL implementation of $onpoly() and $inpoly().

If you're using "/onpolytest" you must rename any traces of $onpoly and $inpoly to $mslonpoly and $mslinpoly to see the differences between your native identifiers and the mSL ones.

These are coded to behave like the old $onpoly and $inpoly and assumes you only pass the points that make up the polygon (repeating NONE) in a clockwise or counter-clockwise fashion. In order to step around the polygon, it makes a wrap-around by appending the 1st point to the end of the polygon definition.

Picture a square/rectangle. You have 4 points that make up the shape (the corners) we'll call them a, b, c and d.
Code:
a-----b
|     |
|     |
d-----c

In order to step around this shape, we need to trace the points. a-b, b-c, c-d, and lastly d-a. This is why the 1st point is appended to the end.

Code:
alias MslInPoly {
  ;=== setup variables and complete polygon
  var %cn = 0 , %x = $1 , %y = $2 , %size = $0 , %poly = $3- $3-4

  if (%size > 2) { 
    var %i = 0 , %j = %size - 2
    while (%i < %j) {
      var %ax = $gettok(%poly,$calc(%i + 1),32) , %ay = $gettok(%poly,$calc(%i + 2),32) , %bx = $gettok(%poly,$calc(%i + 3),32) , %by = $gettok(%poly,$calc(%i + 4),32)

      ;=== Condition1 = Upward Crossing, Condition2 = downward crossing
      if (%ay <= %y && %by > %y) || (%ay > %y && %by <= %y) { 

        ;=== Compute the actual edge-ray intersect x-coordinage
        var %vt = $calc((%y - %ay) / (%by - %ay))

        ;=== Test for valid crossing
        if (%x < $calc(%ax + %vt * (%bx - %ax))) { inc %cn } 

      }
      inc %i 2
    }
  }
  var %cn = $and(%cn,1)
  if (%cn > 0) { return $true }
}

alias MslOnPoly {
  ;=== Setup variables
  var %s1 = $1 , %s2 = $2 , %p1e = $1 * 2 , %p1 = $gettok($3-,$+(1-,%p1e),32) , %p2 = $gettok($3-,$+($calc(%p1e + 1),-),32)

  ;=== Early escape test, if either polygon is fully contained in the other, any and every point will be inside the other. Knowing this, we don't need to test them all, just one.
  var %p1x = $gettok(%p1,1,32) , %p1y = $gettok(%p1,2,32) , %p2x = $gettok(%p2,1,32) , %p2y = $gettok(%p2,2,32)
  if ($mslInPoly(%p1x,%p1y, [ $regsubex(%p2,/ /g,$chr(44)) ] ) || $mSLInPoly(%p2x,%p2y, [ $regsubex(%p1,/ /g,$chr(44)) ] )) { return $true }

  ;=== Complete the polygons
  var %p1 = %p1 $gettok(%p1,1-2,32) , %p2 = %p2 $gettok(%p2,1-2,32)

  ;=== Else: Iterate line segments and check for intersection
  var %i = 0
  while ($calc(%i / 2) < %s1) {
    var %p1ax = $gettok(%p1,$calc(%i + 1),32) , %p1ay = $gettok(%p1,$calc(%i + 2),32)
    var %p1bx = $gettok(%p1,$calc(%i + 3),32) , %p1by = $gettok(%p1,$calc(%i + 4),32)
    var %j = 0
    while ($calc(%j / 2) < %s2) {
      var %p2ax = $gettok(%p2,$calc(%j + 1),32) , %p2ay = $gettok(%p2,$calc(%j + 2),32)
      var %p2bx = $gettok(%p2,$calc(%j + 3),32) , %p2by = $gettok(%p2,$calc(%j + 4),32)

      ;=== LineSeg to LineSeg intersection test
      if ($intersect(%p1ax,%p1ay,%p1bx,%p1by,%p2ax,%p2ay,%p2bx,%p2by,ll)) { return $true }
      inc %j 2
    }
    inc %i 2
  }
}

Joined: Dec 2002
Posts: 5,411
Hoopy frood
Offline
Hoopy frood
Joined: Dec 2002
Posts: 5,411
Okay, we're getting there :-) I was not clear on what all of the different line colorings in your script represented, so it was difficult to know what to look for. I have made a change that fixes the issue you are describing. The single line now colors line segments red when overlapping. This change will be in the next beta.

Joined: Dec 2002
Posts: 252
T
Talon Offline OP
Fjord artisan
OP Offline
Fjord artisan
T
Joined: Dec 2002
Posts: 252
good deal smile Can't wait! I worded that kinda funny for my msl version, I meant that it's 100% accurate, just that it takes polygon definitions exactly like the old $onpoly and $inpoly.

Re-reading my post it could be interperated as being a clone of the old ones only in mSL with the same exact flaws. This is not the case.

Hope they help in debugging instead of having to keep making small changes and watching this thread to see if it's fixed smile

I tried to heavily comment them so it was easier to follow the logic too, if you're unsure about any portions of it, let me know and I'll elaborate further.

Talon #262818 09/04/18 07:46 PM
Joined: Dec 2002
Posts: 252
T
Talon Offline OP
Fjord artisan
OP Offline
Fjord artisan
T
Joined: Dec 2002
Posts: 252
Better Onpoly test! Now with a legend to represent the colors. Demonstrates Native vs mSL. Tries native 1st, then mSL 2nd if native fails.

You don't want to see the mSL version colors. this is native failing on a condition that should've been true, caught by the mSL version.



Code:
menu @OnPolyTest {
  mouse {
    var %hw = $window($active).dw / 2 , %hh = $window($active).dh / 2
    var %x = $mouse.x - %hw , %y = $mouse.y - %hh

    tokenize 32 $window($active).title
    var %Poly = $1 , %Mouse = $2

    var %Polygon = $OPT.TranslatePolygon($OPT.Polygons(%Poly),0,0,0,2) , %P44 = $regsubex(%Polygon,/\s/g,$chr(44))
    var %PolyClosed = %Polygon $gettok(%Polygon,1-2,32)
    var %PCount = $numtok(%Polygon,32) , %Points = %PCount / 2    

    var %Cursor = $OPT.TranslatePolygon($OPT.Polygons(%Mouse),0,%x,%y,2) , %C44 = $regsubex(%Cursor,/\s/g,$chr(44))
    var %CCount = $numtok(%Cursor,32) , %CPoints = %CCount / 2    

    .onpolytest
    var %a = $onpoly(%CPoints,%Points, [ %C44 ] , [ %P44 ] ) , %b = $mslonpoly(%CPoints,%Points, [ %C44 ] , [ %P44 ] )

    ;==== Test #1

    if (%a || %b) {
      drawtext -n $active 0 0 0 *** Bounding Box on polygon
      var %np = $OPT.TranslatePolygon(%Polygon,0,%hw,%hh)
      drawline -n @OnpolyTest $iif(%a,7,8) 1 %np $gettok(%np,1-2,32)

      var %c = 1 , %d = 4
      while (%c <= %PCount) {
        var %Seg = $gettok(%PolyClosed,$+(%c,-,%d),32)
        tokenize 32 %Seg

        ;==== Test #2

        if ($onpoly(%CPoints,2, [ %C44 ] , [ $regsubex($1-,/\s/g,$chr(44)) ] )) { drawline -n @OnPolyTest 4 1 $regsubex($1-,/([^ ]+) ([^ ]+)/g,$calc(\1 + %hw) $calc(\2 + %hh)) }
        elseif ($mslonpoly(%CPoints,2, [ %C44 ] , [ $regsubex($1-,/\s/g,$chr(44)) ] )) { drawline -n @OnPolyTest 13 4 $regsubex($1-,/([^ ]+) ([^ ]+)/g,$calc(\1 + %hw) $calc(\2 + %hh)) }

        ;==== Test #3

        if ($inpoly($1,$2, [ %C44 ] )) { drawdot -n @OnPolyTest 3 4 $calc($1 + %hw) $calc($2 + %hh) }
        elseif ($mslinpoly($1,$2, [ %C44 ] )) { drawdot -n @OnPolyTest 11 4 $calc($1 + %hw) $calc($2 + %hh) }
        if ($inpoly($3,$4, [ %C44 ] )) { drawdot -n @OnPolyTest 3 4 $calc($3 + %hw) $calc($4 + %hh) }
        elseif ($mslinpoly($3,$4, [ %C44 ] )) { drawdot -n @OnPolyTest 11 4 $calc($3 + %hw) $calc($4 + %hh) }

        var %c = %c + 2 , %d = %d + 2
      }
    }
    drawdot @OnPolyTest
  }
  Polygon
  .Box:opt.changepoly 1 box
  .largeRock1:opt.changepoly 1 largeRock1
  .largeRock2:opt.changepoly 1 largeRock2
  .largeRock3:opt.changepoly 1 largeRock3
  .medRock1:opt.changepoly 1 medRock1
  .medRock2:opt.changepoly 1 medRock2
  .medRock3:opt.changepoly 1 medRock3
  .smallRock1:opt.changepoly 1 smallRock1
  .smallRock2:opt.changepoly 1 smallRock2
  .smallRock3:opt.changepoly 1 smallRock3
  Mouse
  .line:opt.changepoly 2 line
  .Box:opt.changepoly 2 box
  .largeRock1:opt.changepoly 2 largeRock1
  .largeRock2:opt.changepoly 2 largeRock2
  .largeRock3:opt.changepoly 2 largeRock3
  .medRock1:opt.changepoly 2 medRock1
  .medRock2:opt.changepoly 2 medRock2
  .medRock3:opt.changepoly 2 medRock3
  .smallRock1:opt.changepoly 2 smallRock1
  .smallRock2:opt.changepoly 2 smallRock2
  .smallRock3:opt.changepoly 2 smallRock3
}
alias onpolytest {
  if (!$window(@OnPolyTest)) { 
    window -dpf @OnPolyTest -1 -1 640 480 
    titlebar @OnPolyTest largeRock1 box
  }
  tokenize 32 $window(@OnPolyTest).title
  var %Poly = $1 , %Mouse = $2
  var %w = $window(@OnPolyTest).dw , %h = $window(@OnPolyTest).dh , %hw = %w / 2 , %hh = %h / 2
  drawrect -nf @OnPolytest 1 1 0 0 %w %h
  drawtext -np @OnPolyTest 0 0 20 Native: 7Onpoly 4LineSeg onpoly 3Point Inpoly
  drawtext -np @OnPolyTest 0 0 40 $str($chr(140),2) mSL: 8Onpoly 13LineSeg onpoly 11Point Inpoly

  var %Poly = $OPT.TranslatePolygon($OPT.Polygons(%Poly),0,%hw,%hh,2)
  drawline -n @OnpolyTest 0 1 %poly $gettok(%poly,1-2,32)

  var %poly = $OPT.TranslatePolygon($OPT.Polygons(%Mouse),0,$Mouse.x,$Mouse.y,2)
  drawline -n @OnpolyTest 0 1 %poly $gettok(%poly,1-2,32)
  drawtext -np @OnPolyTest 0 0 400 #1. Is MousePoly on the other? (7O,8Y)
  drawtext -np @OnPolyTest 0 0 420 #2. Any polygon linesegs on the mouse poly? (4R,13M)
  drawtext -np @OnPolyTest 0 0 440 #3. Either lineseg point inside the mouse poly? (3G,11B)

  if ($show) { drawdot @OnPolyTest }
}
alias -l OPT.changepoly {
  var %target = $1 , %val = $2
  tokenize 32 $window(@OnPolyTest).title
  var %Poly = $1 , %Mouse = $2
  if (%target = 1) { %Poly = %val }
  else { %Mouse = %val }
  titlebar @OnPolyTest %Poly %Mouse
}
alias -l OPT.Polygons {
  if ($1 = line) { return -10 0 10 0 }
  if ($1 = box) { return -10 -10 10 -10 10 10 -10 10 }
  if ($1 = largeRock1) { return -39 -25 -33 -8 -38 21 -23 25 -13 39 24 34 38 7 33 -15 38 -31 16 -39 -4 -34 -16 -39 }
  if ($1 = largeRock2) { return -32 35 -4 32 24 38 38 23 31 -4 38 -25 14 -39 -28 -31 -39 -16 -31 4 -38 22 }
  if ($1 = largeRock3) { return 12 -39 -2 -26 -28 -37 -38 -14 -21 9 -34 34 -6 38 35 23 21 -14 36 -25 }
  if ($1 = medRock1) { return -7 -19 -19 -15 -12 -5 -19 0 -19 13 -9 19 12 16 18 11 13 6 19 -1 16 -17 }
  if ($1 = medRock2) { return 9 -19 18 -8 7 0 15 15 -7 13 -16 17 -18 3 -13 -6 -16 -17 }
  if ($1 = medRock3) { return 2 18 18 10 8 0 18 -13 6 -18 -17 -14 -10 -3 -13 15 }
  if ($1 = smallRock1) { return -8 -8 -5 -1 -8 3 0 9 8 4 8 -5 1 -9 }     
  if ($1 = smallRock2) { return -6 8 1 4 8 7 10 -1 4 -10 -8 -6 -4 0 }
  if ($1 = smallRock3) { return -8 -9 -5 -2 -8 5 6 8 9 6 7 -3 9 -9 0 -7 }
}
alias -l OPT.TranslatePolygon {  
  var %dx = $cos($2).deg , %dy = $sin($2).deg , %ox = $3 , %oy = $4 , %scale = $iif($5,$5,1)
  return $regsubex($1,/([^ ]+) ([^ ]+)/g,$calc(((\1 * %dx + \2 * (%dy * -1)) * %scale) + %ox) $calc(((\1 * %dy + \2 * %dx) * %scale) + %oy))
}

alias MslInPoly {
  ;=== setup variables and complete polygon
  var %cn = 0 , %x = $1 , %y = $2 , %size = $0 , %poly = $3- $3-4

  if (%size > 2) { 
    var %i = 0 , %j = %size - 2
    while (%i < %j) {
      var %ax = $gettok(%poly,$calc(%i + 1),32) , %ay = $gettok(%poly,$calc(%i + 2),32) , %bx = $gettok(%poly,$calc(%i + 3),32) , %by = $gettok(%poly,$calc(%i + 4),32)

      ;=== Condition1 = Upward Crossing, Condition2 = downward crossing
      if (%ay <= %y && %by > %y) || (%ay > %y && %by <= %y) { 

        ;=== Compute the actual edge-ray intersect x-coordinage
        var %vt = $calc((%y - %ay) / (%by - %ay))

        ;=== Test for valid crossing
        if (%x < $calc(%ax + %vt * (%bx - %ax))) { inc %cn } 

      }
      inc %i 2
    }
  }
  var %cn = $and(%cn,1)
  if (%cn > 0) { return $true }
}

alias MslOnPoly {
  ;=== Setup variables
  var %s1 = $1 , %s2 = $2 , %p1e = $1 * 2 , %p1 = $gettok($3-,$+(1-,%p1e),32) , %p2 = $gettok($3-,$+($calc(%p1e + 1),-),32)

  ;=== Early escape test, if either polygon is fully contained in the other, any and every point will be inside the other
  var %p1x = $gettok(%p1,1,32) , %p1y = $gettok(%p1,2,32) , %p2x = $gettok(%p2,1,32) , %p2y = $gettok(%p2,2,32)
  if ($mslInPoly(%p1x,%p1y, [ $regsubex(%p2,/ /g,$chr(44)) ] ) || $mSLInPoly(%p2x,%p2y, [ $regsubex(%p1,/ /g,$chr(44)) ] )) { return $true }

  ;=== Complete the polygons
  var %p1 = %p1 $gettok(%p1,1-2,32) , %p2 = %p2 $gettok(%p2,1-2,32)

  ;=== Else: Iterate line segments and check for intersection
  var %i = 0
  while ($calc(%i / 2) < %s1) {
    var %p1ax = $gettok(%p1,$calc(%i + 1),32) , %p1ay = $gettok(%p1,$calc(%i + 2),32)
    var %p1bx = $gettok(%p1,$calc(%i + 3),32) , %p1by = $gettok(%p1,$calc(%i + 4),32)
    var %j = 0
    while ($calc(%j / 2) < %s2) {
      var %p2ax = $gettok(%p2,$calc(%j + 1),32) , %p2ay = $gettok(%p2,$calc(%j + 2),32)
      var %p2bx = $gettok(%p2,$calc(%j + 3),32) , %p2by = $gettok(%p2,$calc(%j + 4),32)

      ;=== LineSeg to LineSeg intersection test
      if ($intersect(%p1ax,%p1ay,%p1bx,%p1by,%p2ax,%p2ay,%p2bx,%p2by,ll)) { return $true }
      inc %j 2
    }
    inc %i 2
  }
}

Joined: Dec 2002
Posts: 252
T
Talon Offline OP
Fjord artisan
OP Offline
Fjord artisan
T
Joined: Dec 2002
Posts: 252
had a bug in my MslInPoly, when I checked for a valid crossing, it should've been <= instead of <.

so this line:
;=== Test for valid crossing
if (%x < $calc(%ax + %vt * (%bx - %ax))) { inc %cn }

should be:
;=== Test for valid crossing
if (%x <= $calc(%ax + %vt * (%bx - %ax))) { inc %cn }

and now:



unless inpoly literally is supposed to be points inside the surface of the polygon, and not points that are right on the very edge of the polygon (which is still on the defined surface).

In evaluating this image, you should come to the conclusion that mIRC got 4 out of 6 right, only missing one $inpoly and one $onpoly

Why?
1. mIRC found that the mouse poly was on the other poly
2. mIRC found 2 out of 3 line segments that were on the mouse poly
3. mIRC found 1 out of 2 line segment endpoints that were on the mouse poly.

Joined: Dec 2002
Posts: 252
T
Talon Offline OP
Fjord artisan
OP Offline
Fjord artisan
T
Joined: Dec 2002
Posts: 252
Looks good! new beta working flawlessly for $onpoly(). I haven't been able to break it so far. The only one I've been able to break is $inpoly()

I still get a blue dot if the point is on one of the line segments defining the polygon. Picture a piece of paper cut out in the shape of that polygon. the edges of our piece of paper is stained (symbolizing our drawline outline) Points on this "stained" edge aren't considered "inside" the polygon, as if this very edge is considered a container, and not part of the surface of our polygon definition.

I do know it's rather difficult to get the blue dot to show depending on your mouse's set sensitivity to get small enough movement increments to get this to show.

$onpoly() catches these edge cases and is highlighting the line fine, just $inpoly() is not catching the line segment endpoint.

it does however catch it if I adjust the points to be 1 extra pixel away from the origin [0,0] using $inpoly() so I know it's due to the outline not being considered part of the surface.





=========================================================
Edit:
=========================================================

Further testing outside of this mouse test shows $inpoly() returning true for any random point picked from the polygon definition, so this turns out to be some sort of precision error using a point on a line inbetween the two endpoints on this last screenshot.

Not sure about if it's mSL's limitation of 6 decimal positions causing mine to return differently than mIRC's or not, but I can't ever seem to get a green dot from mIRC when getting a non-axis-aligned linesegment to fall perfectly on a point, so maybe mIRC's $inpoly() epsilon for error adjustment is too fine, and never considering any points between linesegment ends on the same plane from returning true, or it's mSL's precision limit of 6 causing mine to falsely return true.

It's going to take a bit of re-working on the onpolytest because I need to find the linsegment now in the mouse poly that caused $onpoly() to be true, but not $inpoly() for a specific endpoint from a linsegment test.

I can use this simple "equasion ax + by + c = 0" plugging in my endpoint for the x,y and solving. if the return is 0, it's on the line, if it's negative or positive it's on one side or the other of the line and not truely on the line.

Either way this should give me the epsilon threshold between the two methods and see why one returns differently than the other.

My running theory is a point is treated as an INT and not a FLOAT or DOUBLE so there's no decimal places, rounding definately ensures the point's not on the linesegment, since it lost any half-space data (decimal values)

I'll post back my findings and probably make a simpler test just for this specific case.

Last edited by Talon; 14/04/18 05:32 PM.
Joined: Dec 2002
Posts: 252
T
Talon Offline OP
Fjord artisan
OP Offline
Fjord artisan
T
Joined: Dec 2002
Posts: 252
Okay, when this error occurred, I outputted the mouse poly, the line segment, and the endpoint to test. I've tested several of them, but I'll just demonstrate one here since the results are always the same outcome:

Output:
Point: -26 78 Segment: -26 78 48 68 ( -66,58,-26,58,-26,98,-66,98 )

Poly Broken Down to Linsegs:
-66,58,-26,58
-26,58,-26,98
-26,98,-66,98
-66,98,-66,58

stepping through the mouse poly against the linesegment, the second linesegment was the one found intersecting.

echo -a $intersect(-26,78,48,68,-26,58,-26,98,ll)
Output: -26 78 (just so happens to return the same point as our endpoint! more proof it's on the lineseg.)

now we take this linesegment, and our endpoint (not the one from $intersect() although they're both the same here) and follow our equasion and solve it:
Ax + By + C = 0
(y1 – y2)x + (x2 – x1)y + (x1y2 – x2y1) = 0

//tokenize 32 -26 58 -26 98 | var %x = -26 , %y = 78 | echo -a $calc(($2 - $4) * %x + ($3 - $1) * %y + ($1 * $4 - $3 * $2))

Output:
0

Let's shift X by a bit and show what happens with the line test:

//tokenize 32 -26 58 -26 98 | var %x = -26.000001 , %y = 78 | echo -a $calc(($2 - $4) * %x + ($3 - $1) * %y + ($1 * $4 - $3 * $2))

Output:
0.00004 (Not truely on the line)

This point truely is on the linesegment. it's return was 0, not some positive or negative number.

This means it is part of our polygon surface, yet $inpoly() returns false.

//echo -a $inpoly(-26,78,-66,58,-26,58,-26,98,-66,98)
Output:
$false

$onpoly() proved they overlap.

$intersect() proved that one of the mousepoly linesegments intersect with the linesegment from the other polygon, and returned an intersection point identical to the one wer're testing.

Using the line equasion, we proved that the point is truely 100% on the linesegment, not left or right of it.

$inpoly() failed.

Joined: Dec 2002
Posts: 5,411
Hoopy frood
Offline
Hoopy frood
Joined: Dec 2002
Posts: 5,411
I checked the $inpoly() in 7.52, which uses the Windows regions API to create polygon regions and check if a point is inside them, and it returned $false for your $inpoly() test as well. The beta uses mathematics and shows the same result. My guess is that this issue is due to rounding. I am not sure what else I can change in the implementation, which uses doubles, to improve this.

Joined: Dec 2002
Posts: 252
T
Talon Offline OP
Fjord artisan
OP Offline
Fjord artisan
T
Joined: Dec 2002
Posts: 252
Did you read my comment about missing a = sign in my method? If not it has the same flaw. It would've outputted false. It needed to be <= instead of < for the testing for valid crossing.

My paste was too old to allow me to edit in the fix at the time which is why I posted what needed fixed, and opted to show where, since it was just one forgotten character, instead of re-pasting the entire code.

//echo -a $inpoly(-26,78,-66,58,-26,58,-26,98,-66,98)
Output:
$false

//echo -a $mslinpoly(-26,78,-66,58,-26,58,-26,98,-66,98)
Output:
$true

the line that needed changed was:
if (%x < $calc(%ax + %vt * (%bx - %ax))) { inc %cn }

to:
if (%x <= $calc(%ax + %vt * (%bx - %ax))) { inc %cn }

Here it is Copy/Paste friendly, so ya don't have to manually insert the equals sign

Code:
alias MslInPoly {
  ;=== setup variables and complete polygon
  var %cn = 0 , %x = $1 , %y = $2 , %size = $0 , %poly = $3- $3-4

  if (%size > 2) { 
    var %i = 0 , %j = %size - 2
    while (%i < %j) {
      var %ax = $gettok(%poly,$calc(%i + 1),32) , %ay = $gettok(%poly,$calc(%i + 2),32) , %bx = $gettok(%poly,$calc(%i + 3),32) , %by = $gettok(%poly,$calc(%i + 4),32)

      ;=== Condition1 = Upward Crossing, Condition2 = downward crossing
      if (%ay <= %y && %by > %y) || (%ay > %y && %by <= %y) { 

        ;=== Compute the actual edge-ray intersect x-coordinate
        var %vt = $calc((%y - %ay) / (%by - %ay))

        ;=== Test for valid crossing
        if (%x <= $calc(%ax + %vt * (%bx - %ax))) { inc %cn } 

      }
      inc %i 2
    }
  }
  var %cn = $and(%cn,1)
  if (%cn > 0) { return $true }
}

Page 1 of 2 1 2

Link Copied to Clipboard