Posted By

nicoptere on 04/06/13

Tagged

Versions (?)

Last Edited at 04/06/13 12:46am

Statistics

Viewed 187 times

Favorited by 0 user(s)

Related snippets

simple polygon triangulator

/ Published in: PHP

this is an ear clipping triangulation algorithm.
original here:
http://forum.unity3d.com/threads/27223-Polygon-triangulation-code
http://www.unifycommunity.com/wiki/index.php?title=Triangulator

Highlighted TextExpand

<?php

//returns an array of ints representing the indices of the triangles

function triangulate( $points )
{

$m_points = array();
	$m_points = $points;
	
	$n = count( $m_points );
	if ( $n < 3 ) return NULL;
	if ( $n == 3 ) return array( 0,1,2 );
	if ( $n == 4 ) return array( 0,1,2, 0,2,3 );
	
	$indices = array();
	
	$v = 0;
	$vertices = array();
	
	if ( get_area( $m_points ) > 0 ) 
	{
		for ( $v = 0; $v < $n; $v++ ) array_push( $vertices, $v );
	}
	else
	{
		for ( $v = 0; $v < $n; $v++ ) array_push( $vertices, ( $n - 1) - $v );
	}
	
	$nv = $n;
	$count = 2 * $nv;
	$m = 0;
	
	for ( $m = 0, $v = $nv - 1; $nv > 2; ) 
	{
		if ( $count-- <= 0) 
		{
			return $indices;
		}
		
		$u = $v;
		if ( $nv <= $u )	$u = 0;
		
		$v = $u + 1;
		if ( $nv <= $v )	$v = 0;
		
		$w = $v + 1;
		if ( $nv <= $w )	$w = 0;
		
		$toto = snip( $u, $v, $w, $nv, $vertices, $m_points );
		
		if ( snip( $u, $v, $w, $nv, $vertices, $m_points ) == 1 ) 
		{
		
			$a; $b; $c; $s; $t;
			
			$a = $vertices[ $u ];
			$b = $vertices[ $v ];
			$c = $vertices[ $w ];
			
			array_push( $indices, $a );
			array_push( $indices, $b );
			array_push( $indices, $c );
			
			$m++;
			for ($s = $v, $t = $v + 1; $t < $nv; $s++, $t++)
			{
				$vertices[ $s ] = $vertices[ $t ];
			}
			$nv--;
			$count = 2 * $nv;
			
		}
	}
	return $indices;
	
}

function get_area( $m_points ) //retourne la surface signÃ©e du triangle
{
	$n = count( $m_points );
	
	$A = 0;
	$p = 0;
	$q = 0;
	
	for ( $p = $n - 1, $q = 0; $q < $n; $p = $q++ ) 
	{
		
		$pval = $m_points[ $p ];
		$qval = $m_points[ $q ];
		$A = $A + ( $pval->x * $qval->y - $qval->x * $pval->y );
		
	}
	return ( $A * 0.5 );
}

function snip( $u, $v, $w, $n, $vertices, $m_points )
{

$A = $m_points[ $vertices[ $u ] ];
	$B = $m_points[ $vertices[ $v ] ];
	$C = $m_points[ $vertices[ $w ] ];
	
	if ( .000000001 > ((($B->x - $A->x) * ($C->y - $A->y)) - (($B->y - $A->y) * ($C->x - $A->x))))	return false;
	
	for ( $p = 0; $p < $n; $p++) 
	{
		
		if (($p == $u) || ($p == $v) || ($p == $w)) continue;
		
		$P = $m_points[ $vertices[ $p ] ];
		
		if ( inside_triangle( $A, $B, $C, $P ) == true )return false;
		
	}
	return true;
	
}

function inside_triangle( $A, $B, $C, $P )
{

$ax; $ay; $bx; $by; $cx; $cy; $apx; $apy; $bpx; $bpy; $cpx; $cpy; $cCROSSap; $bCROSScp; $aCROSSbp;
	
	$ax = $C->x - $B->x; $ay = $C->y - $B->y;
	$bx = $A->x - $C->x; $by = $A->y - $C->y;
	$cx = $B->x - $A->x; $cy = $B->y - $A->y;
	
	$apx = $P->x - $A->x; $apy = $P->y - $A->y;
	$bpx = $P->x - $B->x; $bpy = $P->y - $B->y;
	$cpx = $P->x - $C->x; $cpy = $P->y - $C->y;
	
	$aCROSSbp = $ax * $bpy - $ay * $bpx;
	$cCROSSap = $cx * $apy - $cy * $apx;
	$bCROSScp = $bx * $cpy - $by * $cpx;
	
	return ( ( $aCROSSbp >= 0.0 ) && ($bCROSScp >= 0.0) && ($cCROSSap >= 0.0));
	
}

class point 
{
	var $x = 0;
	var $y = 0;
	
    function point( $_x, $_y )
	{
		$this->x = $_x;
		$this->y = $_y;
    }
}

//input is an ordered polyline made of points and it must not be self intersecting

$points = array( 	new point( 100, 100 ),
					new point( 200, 100 ),
					new point( 200, 200 ),
					new point( 150, 250 ),
					new point( 100, 200 ) );

//compute and dump

var_dump( triangulate( $points ) );

echo '<br/>expected result: 4,0,1,1,2,3,3,4,1';

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.