jdfekete/README.md

## README.md

      
    Raw
  

              README.md
            
          
    D3 plugin to compute antipodal pairs of a convex polygon, as well as its diameter.
Useful for several things. In particular to align a graph along its longest axis.

  
## antipodalpairs.js
(function() {
// unsigned area * 2
function area2(i1, i2, i3, v) {
    var a = v[i1], b = v[i2], c = v[i3];
    return Math.abs(  a[0]*b[1] - a[1]*b[0]
                      + a[1]*c[0] - a[0]*c[1]
                      + b[0]*c[1] - c[0]*b[1]);
}

function next(p, poly) {
    p = p+1;
    if (p >= poly.length)
        return 0;
    return p;
}

function distance2(p1, p2) {
    var dx = (p1[0]-p2[0]),
        dy = (p1[1]-p2[1]);
    return dx*dx+dy*dy;
}

/**
 * @param convex polygon vertices [[x1, y1], [x2, y2], …]
 * @returns all antipodal pairs along the convex polygon [[[x1, y1], [x2, y2]], …]
 * Algorithm from "F.P. Preparata and M.I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, 1985."
 * with enhacements from Hormoz Pirzadeh http://cgm.cs.mcgill.ca/~orm/rotcal.html
 */
d3.geom.antipodalPairs = function(poly) {
    var ret = [],
        p = poly.length-1,
        q = 0; //next(p, poly),

    while (  area2(p, next(p, poly), next(q, poly), poly)
           > area2(p, next(p, poly), q, poly)) {
        q = next(q, poly);
    }
    var q0 = q,
        p0 = 0;

    while (q != p0) {
        p = next(p, poly);
        ret.push([poly[p], poly[q]]);
        while (  area2(p, next(p, poly), next(q, poly), poly)
               > area2(p, next(p, poly), q, poly)) {
            q = next(q, poly);
            if ((p != q0) || (q != p0))
                ret.push([poly[p], poly[q]]);
            else
                return ret;
        }
        if (   area2(p, next(p, poly), next(q, poly), poly)
            == area2(p, next(p, poly), q, poly)) {
            // parallel case
            if ((p != q0) || (q != poly.length-1))
                ret.push([poly[p], poly[next(q, poly)]]);
            else {
                ret.push([poly[next(p, poly)], poly[q]]);
                return ret;
            }
        }
    }

    return ret;
};

/**
 * @param convex polygon vertices [[x1, y1], [x2, y2], …]
 * @returns the longest pair
 */
d3.geom.diameter = function(hull) {
    var d = 0,
        pair = -1,
        rc = d3.geom.antipodalPairs(hull);

    for (var i = 0; i < rc.length; i++) {
        var c = rc[i],
            len = distance2(c[0],c[1]);
        if (len > d) {
            d = len;
            pair = i;
        }
    }
    if (pair == -1)
        return null; // ??
    return rc[pair];
};

})();

## index.html
<!DOCTYPE html>
<html>
<head>
<style type="text/css">
    circle {
    fill: black;
    }
    .hull {
	stroke: #f00;
	stroke-width: 2px;
	fill: none;
    }

    .diameter {
	stroke: #0f0;
	stroke-width: 4px;
	fill: none;
    }
    .rc {
	stroke: #aaa;
	stroke-width: 1px;
	fill: none;
    }
</style>

<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="antipodalpairs.js"></script>
<script>

var width = 500,
    height = 200,
    off = 100;

  var points = [];
  var angle = Math.PI / 5,
      c = Math.cos(angle),
      s = Math.sin(angle);

  for (var i = 0; i < 100; i++) {
      var v = [c * Math.random()*width/2 + width/2 + off, s*Math.random()*height + height/2 + off];
      points.push(v);
  }

  var svg = d3.select("body").append("svg")
    .attr("width", width+2*off)
    .attr("height", width+2*off);

  svg.selectAll("circle")
    .data(points)
    .enter().append("circle")
    .attr("cx", function(d) { return d[0]; })
    .attr("cy", function(d) { return d[1]; })
    .attr("r", 5);

var hull = d3.geom.hull(points);
var line = d3.svg.line()
    .interpolate("linear-closed")
    .x(function(d) { return d[0]; })
    .y(function(d) { return d[1]; });

svg.selectAll(".hull")
    .data([hull])
  .enter()
  .append("path")
  .attr("class", "hull")
  .attr("d", line);

var rc = d3.geom.antipodalPairs(hull),
    dia = d3.geom.diameter(hull);

function distance2(p1, p2) {
    var dx = (p1[0]-p2[0]),
        dy = (p1[1]-p2[1]);
    return dx*dx+dy*dy;
}

rc = rc.map(function(v) { v.push(distance2(v[0], v[1])); return v; });

var pairs = svg.selectAll(".rc")
  .data(rc)
  .enter().append("line")
    .attr("class", "rc")
    .attr("x1", function(d) { return d[0][0]; })
    .attr("y1", function(d) { return d[0][1]; })
    .attr("x2", function(d) { return d[1][0]; })
    .attr("y2", function(d) { return d[1][1]; })
  .append("title").text(function(d) { return "len:"+d[2]; });


svg.selectAll(".diameter")
  .data([dia])
  .enter().append("line")
    .attr("class", "diameter")
    .attr("x1", function(d) { return d[0][0]; })
    .attr("y1", function(d) { return d[0][1]; })
    .attr("x2", function(d) { return d[1][0]; })
    .attr("y2", function(d) { return d[1][1]; });

</script>
</body>
</html>
	(function() {
	// unsigned area * 2
	function area2(i1, i2, i3, v) {
	var a = v[i1], b = v[i2], c = v[i3];
	return Math.abs( a[0]b[1] - a[1]b[0]
	+ a[1]c[0] - a[0]c[1]
	+ b[0]c[1] - c[0]b[1]);
	}

	function next(p, poly) {
	p = p+1;
	if (p >= poly.length)
	return 0;
	return p;
	}

	function distance2(p1, p2) {
	var dx = (p1[0]-p2[0]),
	dy = (p1[1]-p2[1]);
	return dxdx+dydy;
	}

	/**
	* @param convex polygon vertices [[x1, y1], [x2, y2], …]
	* @returns all antipodal pairs along the convex polygon [[[x1, y1], [x2, y2]], …]
	* Algorithm from "F.P. Preparata and M.I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, 1985."
	* with enhacements from Hormoz Pirzadeh http://cgm.cs.mcgill.ca/~orm/rotcal.html
	*/
	d3.geom.antipodalPairs = function(poly) {
	var ret = [],
	p = poly.length-1,
	q = 0; //next(p, poly),

	while ( area2(p, next(p, poly), next(q, poly), poly)
	> area2(p, next(p, poly), q, poly)) {
	q = next(q, poly);
	}
	var q0 = q,
	p0 = 0;

	while (q != p0) {
	p = next(p, poly);
	ret.push([poly[p], poly[q]]);
	while ( area2(p, next(p, poly), next(q, poly), poly)
	> area2(p, next(p, poly), q, poly)) {
	q = next(q, poly);
	if ((p != q0) \|\| (q != p0))
	ret.push([poly[p], poly[q]]);
	else
	return ret;
	}
	if ( area2(p, next(p, poly), next(q, poly), poly)
	== area2(p, next(p, poly), q, poly)) {
	// parallel case
	if ((p != q0) \|\| (q != poly.length-1))
	ret.push([poly[p], poly[next(q, poly)]]);
	else {
	ret.push([poly[next(p, poly)], poly[q]]);
	return ret;
	}
	}
	}

	return ret;
	};

	/**
	* @param convex polygon vertices [[x1, y1], [x2, y2], …]
	* @returns the longest pair
	*/
	d3.geom.diameter = function(hull) {
	var d = 0,
	pair = -1,
	rc = d3.geom.antipodalPairs(hull);

	for (var i = 0; i < rc.length; i++) {
	var c = rc[i],
	len = distance2(c[0],c[1]);
	if (len > d) {
	d = len;
	pair = i;
	}
	}
	if (pair == -1)
	return null; // ??
	return rc[pair];
	};

	})();
	<!DOCTYPE html>
	<html>
	<head>
	<style type="text/css">
	circle {
	fill: black;
	}
	.hull {
	stroke: #f00;
	stroke-width: 2px;
	fill: none;
	}

	.diameter {
	stroke: #0f0;
	stroke-width: 4px;
	fill: none;
	}
	.rc {
	stroke: #aaa;
	stroke-width: 1px;
	fill: none;
	}
	</style>

	<body>
	<script src="http://d3js.org/d3.v3.min.js"></script>
	<script src="antipodalpairs.js"></script>
	<script>

	var width = 500,
	height = 200,
	off = 100;

	var points = [];
	var angle = Math.PI / 5,
	c = Math.cos(angle),
	s = Math.sin(angle);

	for (var i = 0; i < 100; i++) {
	var v = [c * Math.random()width/2 + width/2 + off, sMath.random()*height + height/2 + off];
	points.push(v);
	}

	var svg = d3.select("body").append("svg")
	.attr("width", width+2*off)
	.attr("height", width+2*off);

	svg.selectAll("circle")
	.data(points)
	.enter().append("circle")
	.attr("cx", function(d) { return d[0]; })
	.attr("cy", function(d) { return d[1]; })
	.attr("r", 5);

	var hull = d3.geom.hull(points);
	var line = d3.svg.line()
	.interpolate("linear-closed")
	.x(function(d) { return d[0]; })
	.y(function(d) { return d[1]; });

	svg.selectAll(".hull")
	.data([hull])
	.enter()
	.append("path")
	.attr("class", "hull")
	.attr("d", line);

	var rc = d3.geom.antipodalPairs(hull),
	dia = d3.geom.diameter(hull);

	function distance2(p1, p2) {
	var dx = (p1[0]-p2[0]),
	dy = (p1[1]-p2[1]);
	return dxdx+dydy;
	}

	rc = rc.map(function(v) { v.push(distance2(v[0], v[1])); return v; });

	var pairs = svg.selectAll(".rc")
	.data(rc)
	.enter().append("line")
	.attr("class", "rc")
	.attr("x1", function(d) { return d[0][0]; })
	.attr("y1", function(d) { return d[0][1]; })
	.attr("x2", function(d) { return d[1][0]; })
	.attr("y2", function(d) { return d[1][1]; })
	.append("title").text(function(d) { return "len:"+d[2]; });



	svg.selectAll(".diameter")
	.data([dia])
	.enter().append("line")
	.attr("class", "diameter")
	.attr("x1", function(d) { return d[0][0]; })
	.attr("y1", function(d) { return d[0][1]; })
	.attr("x2", function(d) { return d[1][0]; })
	.attr("y2", function(d) { return d[1][1]; });

	</script>
	</body>
	</html>