PHP Repulsion Polyhedra

[mctrivia]

There is a cool flash app here http://members.ozemail.com.au/~llan/mpol.html that computes a shape with as far apart as possible points(keeping them on the outer plane of a sphere) using the inverse square law and multiple iterations.  Problem is the flash dies if you try to run really high point counts and I wanted to be able to mess with the physics by adding fixed points.

 

 

All i need is the x,y,z cowardinents of each point so I can tell my 3d printer how to print the shape. I tried to convert the script to PHP.  Problem is no matter what I try I get meaningless results out.  My theory was if I map my points on a longitude and latitude grid of a circle of radius 1 I could simplify things a fair bit.  My complete source code is at the bottom but let me break down what I believe each section should do.

 

In forces function it computes the distance between 2 points using the formula:

acos(sin($lat1)*sin($lat2) + cos($lat1)*cos($lat2) * cos($lon2-$lon1));

 

since I went with a gravitational constant of 1 a radius of 1 and a mass for each point of 1 the repulsion force between the points should be:

1/($distance*$distance)

 

direction of this force clockwise from North should be

    $y=sin($lon2-$lon1) * cos($lat2);
    $x=cos($lat1)*sin($lat2)-sin($lat1)*cos($lat2)*cos($lon2-$lon1);

    //invert direction
    $direction=atan2($y,$x)+pi();

 

function addResults splits the force and bearing up into rectangular format so I can add all the vectors easier

 

then function move takes the sum off all the vectors multiplies it by a scaler to limit the points movement and computes the new point.  Problem is it does not work.  I have definitely screwed up. 

 

Any help would greatly be appreciated. 

 

<?php
define("POINT_COUNT",6);

function forces($a,$b,&$force,&$direction) {
  //break up arrays
  $lat1=$a[0];
  $lat2=$b[0];
  $lon1=$a[1];
  $lon2=$b[1];

  //compute distance between points
  $distance=acos(sin($lat1)*sin($lat2) + cos($lat1)*cos($lat2) * cos($lon2-$lon1));

  //compute force direction
  if ($distance==0) {
    $direction=rand(0,2*pi()); //pick random direction
    $distance=0.1;
  } else {
    $y=sin($lon2-$lon1) * cos($lat2);
    $x=cos($lat1)*sin($lat2)-sin($lat1)*cos($lat2)*cos($lon2-$lon1);

    //invert direction
    $direction=atan2($y,$x)+pi();
  }

  $force=1/($distance*$distance)
}

function move($point,$forcex,$forcey,$m) {
  $lat1=$point[0];
  $lon1=$point[1];
  $d=sqrt(pow($forcex*$m,2)+pow($forcey*$m,2));
  if ($forcex==0) {
    $forcex=0.000001;
  }
  $bearing=atan(((0-$forcey)*$m)/((0-$forcex)*$m));
  $lat2=asin(sin($lat1)*cos($d)+cos($lat1)*sin($d)*cos($bearing));
  $lon2=$lon1+atan2(sin($bearing)*sin($d)*cos($lat1),cos($d)-sin($lat1)*sin($lat2));

  return array($lat2,$lon2);
}

function sphereTo3D($point) {
  $lat=$point[0];
  $lon=$point[1];

  //get radius of x/y circle
  $r=cos($lat);

  //get z position
  $z=sin($lat);

  //calculate xy
  if ($r==0) {
    $x=0;
    $y=0;
  } else {
    $x=cos($lon)*$r;
    $y=sin($lon)*$r;
  }

  return array($x,$y,$z);
}

function addResult(&$x,&$y,$force,$theta) {
  $x+=cos($theta)*$force;
  $y+=sin($theta)*$force;
}





//latitude and longitue
$points=array();

//add the number of points needed
for ($i=0; $i<POINT_COUNT; $i++) {
  $points[]=array(deg2rad(rand(0,36000)/100),deg2rad(rand(0,36000)/100));
}

for($i=0;$i<1000;$i++) {
  $m=0.01;

  //compute forces between each point
  $temp=array();
  foreach ($points as $key=>$point) {

    //compute force on point
    $forcex=0;
    $forcey=0;
    foreach ($points as $a=>$b) {
      if ($key!=$a) {
  
        forces($point,$b,$force,$direction);
        addResult($forcex,$forcey,$force,$direction);

      }
    }

    //determine what should do to try and nutralize force
    $temp[]=move($point,$forcex,$forcey,$m);

  }
  $points=$temp;
}


//convert to 3d
foreach ($points as &$point) {
  $point=sphereTo3D($point);
  echo $point[0] . ',' . $point[1] . ',' . $point[2] .'<br>';
}



?>

[mikosiko]

don't know if this could be the only culprit... (syntax error by the end of this function)

function forces($a,$b,&$force,&$direction) {
  //break up arrays
  $lat1=$a[0];
  $lat2=$b[0];
  $lon1=$a[1];
  $lon2=$b[1];

  //compute distance between points
  $distance=acos(sin($lat1)*sin($lat2) + cos($lat1)*cos($lat2) * cos($lon2-$lon1));

  //compute force direction
  if ($distance==0) {
    $direction=rand(0,2*pi()); //pick random direction
    $distance=0.1;
  } else {
    $y=sin($lon2-$lon1) * cos($lat2);
    $x=cos($lat1)*sin($lat2)-sin($lat1)*cos($lat2)*cos($lon2-$lon1);

    //invert direction
    $direction=atan2($y,$x)+pi();
  }

$force=1/($distance*$distance)   // MISSING ; IN THIS LINE
} 

[mctrivia]

the ; got lost from the end of the one line when I copied over.  Not the problem as it is present on my machine.

[mikosiko]

if you check your php log file (if logging is enabled) you will see the parsing error.

[mctrivia]

there is no parsing error.  there is just no edit option to allow me to put the ; back in.  My test system has no internet connection so I just retyped the code out.  I missed 1 ;

[mctrivia]

I ditched this whole version and instead went 3d points.  the pressure pushes the points off the sphere so after each iteration I normalize the distance to the center to 1.  Works perfectly.  will post code later when I find my thumb drive so I don't get typos from retyping.

[mctrivia]

as promised here is some working code.  I am sure there are ways to optimize.  especially when to end(I am using iteration count only).  But it works

 

<?php

define("POINT_COUNT",6);

function lockToSphere($points) {
  $temp=array();

  foreach ($points as $point) {

    //get length
    $length=sqrt($point[0]*$point[0]+$point[1]*$point[1]+$point[2]*$point[2]);

    //normalize to 1
    $temp[]=array($point[0]/$length,$point[1]/$length,$point[2]/$length);
  }

  return $temp;
}




//generate random points in a 1x1x1 cube
$points=array();
for ($i=0;$i<POINT_COUNT;$i++) {
  $points[]=array(rand(1,1000)/1000,rand(1,1000)/1000,rand(1,1000)/1000);
}

//lock points to sphere
$points=lockToSphere($points);
$m=10;
for ($i=0;$i<10000;$i++) {
  
  if ($i%10==0) {
    $m/=1.01;
  }

  foreach ($points as $ka=>$pa) {
    $forces=array(0,0,0);
    foreach ($points as $kb=>$pb) {
      if ($ka!=$kb) {

        //compute difference between 2 points
        $d=array($pb[0]-$pa[0],$pb[1]-$pa[1],$pb[2]-$pa[2]);
        //compute forces
        $distance=sqrt($d[0]*$d[0]+$d[1]*$d[1]+$d[2]*$d[2]);
        $multiplier=1/($distance*$distance*$distance);		//force/distance = 1/distance^3
        $forces[0]-=$d[0]*$multiplier;
        $forces[1]-=$d[1]*$multiplier;
        $forces[2]-=$d[2]*$multiplier;
      }
    }
    //move point by scaled amount
    $temp[$ka]=array($pa[0]+$m*$forces[0],$pa[1]+$m*$forces[1],$pa[2]+$m*$forces[2]);
  }
  $points=lockToSphere($temp);
}


//print points
foreach ($points as $point) {
  echo $point[0] . ',' . $point[1] . ',' . $point[2] . '<br>';
}
?>