POV-Ray : Newsgroups : povray.binaries.images : in polygon tests : in polygon tests Server Time15 Jul 2024 19:15:06 EDT (-0400)
 in polygon tests
 From: Bald Eagle 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: