POV-Ray : Newsgroups : povray.binaries.images : in polygon tests Server Time
28 Mar 2024 14:47:39 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: <web.6040322ee3a6afa51f9dae300@news.povray.org>
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


Post a reply to this message


Attachments:
Download 'randomdistributions.png' (36 KB)

Preview of image 'randomdistributions.png'
randomdistributions.png


 

From: Bald Eagle
Subject: Re: in polygon tests
Date: 3 Mar 2021 21:15:00
Message: <web.6040423c5fd06191f9dae300@news.povray.org>
(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.


Post a reply to this message


Attachments:
Download 'randomdistributions.png' (37 KB)

Preview of image 'randomdistributions.png'
randomdistributions.png


 

From: Bald Eagle
Subject: Re: in polygon tests
Date: 3 Mar 2021 21:30:00
Message: <web.6040454b5fd06191f9dae300@news.povray.org>
"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....


Post a reply to this message

From: Bald Eagle
Subject: Re: in polygon tests
Date: 3 Mar 2021 22:45:01
Message: <web.6040566f5fd06191f9dae300@news.povray.org>
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)" )


Post a reply to this message

From: Bald Eagle
Subject: Re: in polygon tests
Date: 4 Mar 2021 14:50:11
Message: <web.604139445fd06191f9dae300@news.povray.org>
Fixed the outlining part of the test macro, and now it's looking pretty nice.


Post a reply to this message


Attachments:
Download 'randomdistributions.png' (36 KB)

Preview of image 'randomdistributions.png'
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


Post a reply to this message

From: Bald Eagle
Subject: Re: in polygon tests
Date: 5 Mar 2021 15:20:01
Message: <web.604291c85fd06191f9dae300@news.povray.org>
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


Post a reply to this message


Attachments:
Download 'randomdistributions.png' (124 KB)

Preview of image 'randomdistributions.png'
randomdistributions.png


 

From: Bald Eagle
Subject: Re: in polygon tests
Date: 5 Mar 2021 21:50:00
Message: <web.6042edb75fd06191f9dae300@news.povray.org>
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.
https://www.youtube.com/watch?v=vrk2kAuSyLg

I hope I got it right (it seems to be), and that I covered all of the essential
points.


Post a reply to this message


Attachments:
Download 'halfplanemath.png' (288 KB)

Preview of image 'halfplanemath.png'
halfplanemath.png


 

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.