POV-Ray : Newsgroups : povray.binaries.images : in polygon tests Server Time17 Apr 2021 08:21:32 EDT (-0400)
 in polygon tests (Message 1 to 8 of 8)
 From: Bald Eagle Subject: in polygon tests Date: 3 Mar 2021 20:05:01 Message:
```So, somehow I got 3 methods all coded, and hammered out a macro that loops over
all the iterations, and based on the sign of the iteration argument either
returns all the points (pass/fail) or only returns points that pass the inside
test.

But somehow POV-Ray tests the inside of Friedrich Lohmueller's Insert Menu
polygon example ("Lo") just fine, but the
1. crossing number,
2. winding number
http://geomalgorithms.com/a03-_inclusion.html
and
3. What I was able to convert to SDL from POV-Ray 3.7 stable's source code
/source/backend/shape/polygon.cpp

get the part where the bottom of the L doubles back to start the o, and then
goes diagonally up to make the hole in the o reversed.
And my [inept] conversion of the POV-Ray source code performs the worst, mixing
inside/outside results.  :(

Anyway, for now, here's where I'm at, showing the test scene using "-1000" test
points, which shows all the points generated, be they pass or fail, and using
the crossing number as the test method.

my conversion:

#macro in_polygon (Point, PolygonVertexArray)
#local number = dimension_size (PolygonVertexArray, 1)-1;
#local tx = Point.x;
#local ty = Point.y;
#local n0 = 0;
#local n1 = 1;
#local vtx0 = PolygonVertexArray [n0];
#local vtx1 = PolygonVertexArray [n1];
#local first = vtx0;

#local yflag0 = (vtx0.y >= ty);
#local inside_flag = false;
#for (i, 1, number-1)
#local yflag1 = (vtx1.y >= ty);

#if (yflag0 != yflag1)
#local test = ((vtx1.y-ty) * (vtx0.x-vtx1.x) >= (vtx1.x-tx) *
(vtx0.y-vtx1.y));
#if (test = yflag1)
#local inside_flag = !inside_flag;
#end
#end
/* Move to the next pair of vertices, retaining info as possible. */
#if ((i < number-2) & (vtx1.x = first.x) & (vtx1.y = first.y))
#local n0 = n0+1;
#local n1 = n1+1;
#local vtx0 = PolygonVertexArray [n0];
#local vtx1 = PolygonVertexArray [n1];
#local yflag0 = (vtx0.y >= ty);
#local first = vtx0;
#else
#local vtx0 = vtx1;
#local n1 = n1+1;
#local vtx1 = PolygonVertexArray[n1];
#local yflag0 = yflag1;
#end
#end // end for

inside_flag
#end
```

Attachments:

Preview of image 'randomdistributions.png'

 From: Bald Eagle Subject: Re: in polygon tests Date: 3 Mar 2021 21:15:00 Message:
```(fixed that error in the outlining of the polygon)

And here's the weird mixed results with the converted POV-Ray method.

Maybe there's a clue in there somewhere.
```

Attachments:

Preview of image 'randomdistributions.png'

 From: Bald Eagle Subject: Re: in polygon tests Date: 3 Mar 2021 21:30:00 Message:
```"Bald Eagle" <cre### [at] netscapenet> wrote:

> And here's the weird mixed results with the converted POV-Ray method.
Which, trying out a guess to account for the lack of programming "tricks" in SDL
vs C++, (I added #local n0 = n0+1; in the second part) fixed the difference, and
now all three methods give me same, but clearly wrong results.

....Or partially right results...  :/

And this is why these things take 100 times longer than they should....
```
 From: Bald Eagle Subject: Re: in polygon tests Date: 3 Mar 2021 22:45:01 Message:
```And here we go.
One last ditch effort to get it to work so I could sleep peacefully.  <eye-roll>

The problem lay in "my [inept] conversion of the POV-Ray source code"

The "L" rendered fine by itself, but the "o" by itself showed the same issue as
the whole polygon.  Which pointed to the diagonal line.  The _EXTRA_ diagonal
line.
That's where it jumps from the end of one closed polygon to the beginning of
another.  So I need to skip over it.
Thus, the "Move to the next _pair_ of vertices," part of the source code
comment.

So, I messed up trying to mimic
vtx0 = &points[++i][X];
vtx1 = &points[++i][X];
in SDL

I _think_ it's right now, but I will have to check that I didn't just fix it for
this special case, and it will break somewhere else...

If that all works out, I'll add the change to the outlining part of the testing
algorithm, and then it should be quite nice.

Stay stubborn, my friends.  ;)

(Also, of course, now that I've solved it - I'm getting "Error: Uploading the
attachment failed. (7)" )
```
 From: Bald Eagle Subject: Re: in polygon tests Date: 4 Mar 2021 14:50:11 Message:
```Fixed the outlining part of the test macro, and now it's looking pretty nice.
```

Attachments:

Preview of image 'randomdistributions.png'

 From: Thomas de Groot Subject: Re: in polygon tests Date: 5 Mar 2021 02:30:37 Message: <6041de1d\$1@news.povray.org>
```Op 04/03/2021 om 20:47 schreef Bald Eagle:
> Fixed the outlining part of the test macro, and now it's looking pretty nice.
>

You should do something about those midges.... ;-)

--
Thomas
```
 From: Bald Eagle Subject: Re: in polygon tests Date: 5 Mar 2021 15:20:01 Message:
```Thomas de Groot <tho### [at] degrootorg> wrote:

> You should do something about those midges.... ;-)

I took a cue from Robert and set the fireflies loose on them.   :P
```

Attachments:

Preview of image 'randomdistributions.png'

 From: Bald Eagle Subject: Re: in polygon tests Date: 5 Mar 2021 21:50:00 Message:
```OK, kids.
I wanted to understand how POV-Ray's in_polygon algorithm worked in the source
code.
This took a bit of puzzling over, reading about some similar methods, and
watching a few videos to get a better feel for the geometric implications of the
vector math operations.

This video (at ~34:00) is what put me on the path to seeing what was going on.