# Polygons & Nodal Points...

cabney cabney at cyberpass.net
Mon Jul 16 16:49:38 CDT 2001

```~sdpm~
On Mon, 16 Jul 2001, cabney wrote:

Well, this is just /wrong/... correction below.

> ###
> # Return a set of y-values at \$x of the polygon edges that intersect
> # at x=\$x
> sub slice
> {
> 	my \$x = shift;
> 	my @poly = @_;
>
> 	my @isect;
> 	my @segment = splice ( @poly, 0, 2 );
> 	# for each set of quads (x1,y1,x2,y2) that intersect at x=\$x
> 	while ( 4 == push @segment, splice ( @poly, 0, 2 ) )
> 	{
> 		if (	( \$segment[0] <= \$x && \$x <= \$segment[2] )
> 			  or
> 			( \$segment[2] <= \$x && \$x <= \$segment[0] )
> 		) {
> 			if ( \$segment[0] == \$segment[2] ) {
> 				next;
> 			} else {
> 				# collect the y-values for segments at x=\$x;
> 				push @isect, mx_plus_b(\$x, at segment);
> 			}
> 		}
> 		@segment = splice( @segment ,2 ,2 );
> 	}
> 	return sort {\$a <=> \$b } @isect;
> }

=8<==================================================
#! /usr/bin/perl -w
# CAbney20010715
# I think this assumes Eulerian, cyclic, directed, connected... but
# I'm still picking that stuff up...
# Anyway, something one'd use to create a polygon in a graphics module
# like GD.pm or OpenGL, where the final point coincides with the first.

use strict;

my ( \$x, \$y, @poly ) = @ARGV;
# These must always end where they start
# Otherwise I think they can do wierd things, like crossed edges...
# square with a triangle missing
#my @poly = (	0.0,0.0, 3.0,0.0,
#		3.0,3.0, 0.0,3.0,
#		2.0,1.0, 0.0,0.0);
#wierd polygon
#my @poly = (	0.0,0.0, 3.0,0.0,
#		3.0,4.0, 0.0,4.0,
#		2.0,1.0, 0.0,3.0,
#		0.0,2.0, 2.0,1.0,
#		0.0,0.0);
# starburst
#my @poly = (	0.0,0.0, 5.0,-1.0,
#		5.0,1.0, 0.0,0.0,
#		5.0,2.0, 5.0,3.0,
#		0.0,0.0, 5.0,4.0,
#		5.0,5.0, 0.0,0.0,
#		4.0,5.0, 3.0,5.0,
#		0.0,0.0, 2.0,5.0,
#		1.0,5.0, 0.0,0.0 );
# starburst
#my @poly = (	0.0,0.0, 5.0,-1.0,
#		5.0,1.0, 0.0,0.0,
#		5.0,2.0, 5.0,3.0,
#		0.0,0.0, 5.0,4.0,
#		5.0,5.0, 0.0,0.0,
#		4.0,5.0, 3.0,5.0,
#		0.0,0.0, 2.0,5.0,
#		1.0,5.0, 0.0,0.0,
#		-1.0,5.0, -2.0,5.0,
#		0.0,0.0 );
#cross
@poly = (	2.0,0.0, 4.0,1.0,
4.0,-1.0, 0.0,1.0,
0.0,-1.0, 2.0,0.0,
3.0,2.0, 1.0,2.0,
3.0,-2.0, 1.0,-2.0,
2.0,0.0) unless @poly;

printf "(%f, %f): %s\n", \$x, \$y, in_poly(\$x,\$y, @poly);

###
# is a point x,y inside a polygon defined by @poly?
sub in_poly
{
my ( \$x, \$y, @poly ) = @_;
my \$c = 0;
my @ladder = slice ( \$x, @poly );

{

# special case: we're on the edge
if ( \$y == \$rung ) {
# trailing edge
\$c++ unless \$c % 2;
}
# we know we're on-edge/encompassed-by the polygon
last if ( \$y <= \$rung );

# odd is in, even is out (promote diversity!)
\$c++;
}
return (\$c % 2) ? "hit!" : "miss!";
}

###
# well, probably not necessary to identify this case.
sub is_vert
{
my (\$x, \$y, @poly) = @_;
while ( my (\$next_x,\$next_y) = splice (@poly,0,2))
{
return 1 if ( (\$x == \$next_x) and (\$y == \$next_y) );
}
return 0;
}

###
# given x and two points on a line...
sub mx_plus_b
{
my \$x = shift;
my ( \$x1,\$y1,\$x2,\$y2 ) = @_;
my ( \$m, \$b );

\$m = (\$y2-\$y1)/(\$x2-\$x1);
\$b = \$y1 - \$m*\$x1;
return \$m*\$x+\$b;
}

###
# Return a set of y-values at \$x of the polygon edges that intersect
# at x=\$x
sub slice
{
my \$x = shift;
my @poly = @_;

my @isect;
my @segment = splice ( @poly, 0, 2 );
# for each set of quads (x1,y1,x2,y2) that intersect at x=\$x
while ( 4 == push @segment, splice ( @poly, 0, 2 ) )
{
if (	( \$segment[0] <= \$x && \$x <= \$segment[2] )
or
( \$segment[2] <= \$x && \$x <= \$segment[0] )
) {
unless ( \$segment[0] == \$segment[2] ) {
push @isect, mx_plus_b(\$x, at segment);
}
}
@segment = splice( @segment ,2 ,2 );
}
return sort {\$a <=> \$b } @isect;
}

=8<==================================================

CA
--
There was a time
A wind that blew so young
For this could be the biggest sky
And I could have the faintest idea

~sdpm~

The posting address is: san-diego-pm-list at hfb.pm.org

List requests should be sent to: majordomo at hfb.pm.org

If you ever want to remove yourself from this mailing list,
you can send mail to <majordomo at happyfunball.pm.org> with the following
command in the body of your email message:

unsubscribe san-diego-pm-list

If you ever need to get in contact with the owner of the list,
(if you have trouble unsubscribing, or have questions about the
list itself) send email to <owner-san-diego-pm-list at happyfunball.pm.org> .
This is the general rule for most mailing lists when you need
to contact a human.

```