Skip to content

Instantly share code, notes, and snippets.

@gousiosg
Created October 7, 2013 17:16
Show Gist options
  • Save gousiosg/6871500 to your computer and use it in GitHub Desktop.
Save gousiosg/6871500 to your computer and use it in GitHub Desktop.
The teapot in PHP!
<?php
class Triangle
{
var $colors = array("yellowgreen", "tomato", "plum");
var $vertices;
function Triangle($vertices)
{
assert(sizeof($vertices) == 3);
$this->vertices = $vertices;
}
function is_right()
{
return $this->has_horizontal_leg() && $this->has_vertical_leg();
}
function has_horizontal_leg()
{
return sizeof(array_unique(array_map(function ($x) { return round($x->y, 4);}, $this->vertices))) < 3;
}
function has_vertical_leg()
{
return sizeof(array_unique(array_map(function ($x) { return round($x->x, 4);}, $this->vertices))) < 3;
}
function area()
{
return abs(
(($this->vertices[0]->x - $this->vertices[2]->x) * ($this->vertices[1]->y - $this->vertices[0]->y) -
($this->vertices[0]->x - $this->vertices[1]->x) * ($this->vertices[2]->y - $this->vertices[0]->y)) * 0.5
);
}
function max_x()
{
return max(array_map(function ($x) { return $x->x; }, $this->vertices));
}
function max_y()
{
return max(array_map(function ($x) { return $x->y; }, $this->vertices));
}
function min_x()
{
return min(array_map(function ($x) {return $x->x; }, $this->vertices));
}
function min_y()
{
return min(array_map(function ($x) { return $x->y; }, $this->vertices));
}
function vertical_cross_lines()
{
return array_map(function ($x) {
return new Line(new Point($x->x, $this->min_y()), new Point($x->x, $this->max_y()));
}, $this->vertices);
}
function horizontal_cross_lines()
{
return array_map(function ($x) {
return new Line(new Point($this->min_x(), $x->y), new Point($this->max_x(), $x->y));
}, $this->vertices);
}
function select_crossline()
{
function comp1($a, $b)
{
if ($a->a->x > $b->a->x) {
return 1;
} elseif ($a->a->x < $b->a->x) {
return -1;
} else {
return 0;
}
}
function comp2($a, $b)
{
if ($a->a->y > $b->a->y) {
return 1;
} elseif ($a->a->y < $b->a->y) {
return -1;
} else {
return 0;
}
}
if ($this->has_horizontal_leg()) {
$lines = $this->vertical_cross_lines();
usort($lines, "comp1");
} else {
$lines = $this->horizontal_cross_lines();
usort($lines, "comp2");
}
return $lines[1];
}
function split_triangle()
{
$crossline = $this->select_crossline();
assert(!is_null($crossline));
$split_vertex = array_values(array_filter($this->vertices, function ($x) use ($crossline) {
return $crossline->is_online($x);
}));
$other_vertices = array_values(array_filter($this->vertices, function ($x) use ($crossline) {
return !$crossline->is_online($x);
}));
assert(sizeof($split_vertex) == 1);
assert(sizeof($other_vertices) == 2);
assert($other_vertices[0] != $other_vertices[1]);
$cross_point = (new Line($other_vertices[0], $other_vertices[1]))->intersection_point($crossline);
$first = new Triangle(array($split_vertex[0], $cross_point, $other_vertices[0]));
$second = new Triangle(array($split_vertex[0], $cross_point, $other_vertices[1]));
return array($first, $second);
}
function svg()
{
return sprintf("<polygon points='%f,%f %f,%f %f,%f' style='fill:%s;stroke:white'/>",
$this->vertices[0]->x, $this->vertices[0]->y,
$this->vertices[1]->x, $this->vertices[1]->y,
$this->vertices[2]->x, $this->vertices[2]->y,
$this->colors[array_rand($this->colors, 1)]
);
}
}
class Point
{
var $x = 0;
var $y = 0;
function Point($x, $y)
{
$this->x = $x;
$this->y = $y;
}
}
class Line
{
var $EPSILON = 0.0001;
var $a;
var $b;
function Line($a, $b)
{
$this->a = $a;
$this->b = $b;
}
function length()
{
return (sqrt(pow(($this->b->x - $this->a->x), 2) + pow(($this->b->y - $this->a->y), 2)));
}
function linear_equation()
{
$divisor = ($this->b->x - $this->a->x);
if ($divisor != 0) {
$k = ($this->b->y - $this->a->y) / $divisor;
} else {
$k = INF;
}
$d = $this->a->y - $k * $this->a->x;
return array($k, $d);
}
function is_online($r)
{
list($slope, $intercept) = $this->linear_equation();
if (is_infinite($slope)) {
$error = $this->a->x - $r->x;
} elseif (is_infinite($intercept)) {
$error = $this->a->y - $r->y;
} else {
$error = $r->y - ($slope * $r->x + $intercept);
}
return (abs($error) < $this->EPSILON);
}
function intersection_point($other)
{
list($this_slope, $this_intercept) = $this->linear_equation();
list($other_slope, $other_intercept) = $other->linear_equation();
if (is_infinite($this_slope)) {
$x = $this->a->x;
$y = $other_slope * $x + $other_intercept;
} elseif (is_infinite($other_slope)) {
$x = $other->a->x;
$y = $this_slope * $x + $this_intercept;
} else {
$x = ($other_intercept - $this_intercept) / ($this_slope - $other_slope);
$y = $this_slope * $x + $this_intercept;
}
return new Point($x, $y);
}
}
// Load the data file
function load($file)
{
function get_triangles($acc, $line)
{
$pattern_points = '/"({.*,.*})","({.*,.*})","({.*,.*})"/';
preg_match($pattern_points, $line, $matches);
$points = array_map(function ($x) {
$pattern_point = '/{(.*),(.*)}/';
preg_match($pattern_point, $x, $matches);
return new Point(
($matches[1] * 800) + 600,
($matches[2] * -800) + 1050
);
}, array_slice($matches, 1));
if (sizeof($points) != 3)
return $acc;
$trg = new Triangle($points);
array_push($acc, $trg);
return $acc;
}
return array_reduce(file($file), "get_triangles", array());
}
function split_triangles($t)
{
if ($t->is_right() || $t->area() < 1)
return array($t);
return array_flatten(array_map(function ($trg) {return split_triangles($trg);}, $t->split_triangle()));
}
function array_flatten($arr) {
$arr = array_values($arr);
while (list($k,$v)=each($arr)) {
if (is_array($v)) {
array_splice($arr,$k,1,$v);
next($arr);
}
}
return $arr;
}
function print_err($str){
$stderr = fopen('php://stderr', 'w');
fwrite($stderr, $str);
fclose($stderr);
}
function bench($op) {
$time_start = microtime(true);
$op();
$time_end = microtime(true);
return $time_end - $time_start;
}
$file = "teapot.txt";
$triangles = load($file);
$time_start = microtime(true);
$triangles = load($file);
$time = (microtime(true) - $time_start) * 1000;
print_err("Loaded " . sizeof($triangles) . " triangles in " . $time . " ms\n");
$time_start = microtime(true);
$right_triangles = array_flatten(array_map(function ($trg) {
return split_triangles($trg);
}, $triangles));$time = microtime(true) - $time_start;
$time = (microtime(true) - $time_start) * 1000;
print_err("Generated " . sizeof($right_triangles) . " triangles in " . $time . " ms\n");
print("<svg xmlns='http://www.w3.org/2000/svg' version='1.1'>");
foreach($right_triangles as $triangle)
print($triangle->svg()."\n");
print('</svg>');
@gousiosg
Copy link
Author

gousiosg commented Oct 7, 2013

The input teapot.txt file can be found here

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment