Polygons & Nodal Points...

cabney cabney at cyberpass.net
Mon Jul 16 15:29:51 CDT 2001


~sdpm~
On Mon, 16 Jul 2001 schoon at amgt.com wrote:

> Hey, thanks! Yes, I did think of this approach - simply check to see if
> my node falls on a line... This will work if all lines are orthoganal,
> but I can't be guaranteed this will be the case. The approach I'm
> thinking of is like this:

Orthogonal? You don't have to check a segment if it's running on x=$x,
because you are already bounded on both ends of the segment by another
vertice (which can be used for the increment.)

> All polygons start at the origin.

Not really necessary.

> Start at origin X=0, Y=0;
> If X == vertice, check for max/min Y and increment Y from min to max.
> Increment X check max/min Y, increment Y from min to max....

You don't even need to mess with min and max, unless you are looking
for bad input. :)

> My thoughts are this would handle angled line segments. What I'm doing
> is creating a mesh within the polygon.... This is discussed somewhat in
> the Mastering Algorithms book, but solving for the case of a node on a
> vertice was out of the books scope.

Collect the edges of the polygon (as quads) that intersect the line
x=$x and calculate their y-values at x=$x.  These are enough to tell you
where you are.

I'm not gonna say this is the right way to do it.  I sorta felt my
way through the properties of the method rather than digging out
a super nice elegant algorithm, so someone else undoubtedly has
a better approach.  But simple approaches are always the easiest
to maintain.:)  There's also a lot of copying going on...
This will also manage simple edge traversals (crossing an edge
with another edge) which probably isn't necessary if you require
a regular polygon, but I'm sure some nasty things could be done
to defeat it:

=8<==================================================
#! /usr/bin/perl -w
# I think this assumes Eulerian, directed, connected, cyclic... 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 ) = @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
my @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);

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 );

	while (@ladder)
	{
		my $rung = shift @ladder;

		# special case: we're on the edge
		if ( $y == $rung ) {
			# trailing edge
			$c++ unless $c % 2;
		}
		# we know we're on-edge/beyond 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] )
		) {
			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<==================================================

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.




More information about the San-Diego-pm mailing list