Skip to content

Instantly share code, notes, and snippets.

@fabiovalse

fabiovalse/README.md

Last active April 27, 2016 09:55
Show Gist options
  • Save fabiovalse/e7d2d1eba207b0a979ad to your computer and use it in GitHub Desktop.
Save fabiovalse/e7d2d1eba207b0a979ad to your computer and use it in GitHub Desktop.
Download ZIP
Non-overlapping regions through collision detection
Raw
index.css
svg {
/*background: #E0F2F4;*/
}
.leaf_region {
fill: red;
opacity: 0.7;
}
circle {
fill: none;
stroke: brown;
stroke-width: 0.3px;
}
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="http://d3js.org/queue.v1.min.js"></script>
<script src="http://d3js.org/topojson.v1.min.js"></script>
<link rel="stylesheet" type="text/css" href="index.css">
<title>Non-overlapping regions through collision detection</title>
</head>
<body>
<script src="ontology.js"></script>
<script src="index.js"></script>
</body>
</html>
Raw
index.js
var width = 960,
height = 500,
padding = 0.5,
maxRadius = 10,
n = 200,
map = {};
/* Projection
*/
var CELL_RADIUS = 0.1,
SIMPLIFICATION = 15;
dx = CELL_RADIUS * 2 * Math.sin(Math.PI / 3);
dy = CELL_RADIUS * 1.5;
path_generator = d3.geo.path().projection(d3.geo.transform({
point: function(x, y, z) {
if (z >= SIMPLIFICATION) {
return this.stream.point(x * dx / 2, -(y - (2 - (y & 1)) / 3) * dy / 2);
}
}
}));
/* Map drawing
*/
queue()
.defer(d3.json, 'ontology.json')
.defer(d3.json, 'map.topo.json')
.await(function(error, ontology_data, data) {
if(error)
throw error;
ontology.init(ontology_data);
_preprocess(data);
nodes = topojson.feature(data, data.objects.leaf_regions).features;
nodes.forEach(function(d) {
d.cx = d.properties.node.x;
d.cy = d.properties.node.y;
d.x = d.cx;
d.y = d.cy;
d.radius = Math.sqrt(d.properties.node.area);
});
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height)
.attr("viewBox", "-300 -20 600 150");
var zoom_layer = svg.append('g');
svg.call(d3.behavior.zoom().scaleExtent([0.6, 600]).on('zoom', function() {
zoom_layer.attr({
transform: "translate(" + d3.event.translate + ")scale(" + d3.event.scale + ")"
});
}));
var map_layer = zoom_layer.append('g');
/* Regions
*/
var node_drag = d3.behavior.drag()
.on("dragstart", function() {force.stop();})
.on("drag", function(d) {
d.px += d3.event.dx;
d.py += d3.event.dy;
d.x += d3.event.dx;
d.y += d3.event.dy;
tick({alpha: 0}); // this is the key to make it work together with updating both px,py,x,y on d !
})
.on("dragend", function() {});
var region = map_layer.selectAll('.leaf_region')
.data(nodes);
var enter_region = region.enter().append('path')
.attr("class", 'leaf_region')
.attr("d", path_generator)
.call(node_drag);
/* Circles
*/
var circle = map_layer.selectAll("circle")
.data(nodes);
var enter_circle = circle.enter().append("circle")
.attr('class', 'node');
enter_circle
.attr("r", function(d) { return d.radius; })
.attr("cx", function(d) { return d.cx; })
.attr("cy", function(d) { return d.cy; });
var force = d3.layout.force()
.nodes(nodes)
.size([width, height])
.gravity(.02)
.charge(0)
.on('tick', tick)
.on('end', function() {
console.log('File loaded correctly.');
})
.start();
force.alpha(.05);
function tick(e) {
region
.each(gravity(.2 * e.alpha))
.each(collide(.5))
.attr("transform", function(d) {return "translate(" + (d.x - d.cx) + ", " + (d.y - d.cy) + ")";});
circle
.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; });
}
// Resolve collisions between nodes.
function collide(alpha) {
var quadtree = d3.geom.quadtree(nodes);
return function(d) {
var r = d.radius + maxRadius + padding,
nx1 = d.x - r,
nx2 = d.x + r,
ny1 = d.y - r,
ny2 = d.y + r;
quadtree.visit(function(quad, x1, y1, x2, y2) {
if (quad.point && (quad.point !== d)) {
var x = d.x - quad.point.x,
y = d.y - quad.point.y,
l = Math.sqrt(x * x + y * y),
r = d.radius + quad.point.radius + padding;
if (l < r) {
l = (l - r) / l * alpha;
d.x -= x *= l;
d.y -= y *= l;
quad.point.x += x;
quad.point.y += y;
}
}
return x1 > nx2 || x2 < nx1 || y1 > ny2 || y2 < ny1;
});
};
}
// Move nodes toward cluster focus.
function gravity(alpha) {
return function(d) {
d.y += (d.cy - d.y) * alpha;
d.x += (d.cx - d.x) * alpha;
};
}
function print_nodes() {
return nodes.map(function(d) {
return {"id": d.properties.class, "x": d.x, "y": d.y, "cx": d.cx, "cy": d.cy}
});
}
});
_preprocess = function(data) {
var geometries, _merge;
map.leaf_regions = topojson.feature(data, data.objects.leaf_regions).features;
geometries = data.objects.leaf_regions.geometries;
/* parse paths into arrays, and extract the class of each leaf region
*/
map.leaf_regions.forEach(function(f) {
f.properties.path = JSON.parse(f.properties.path);
return f.properties["class"] = f.properties.path[f.properties.path.length - 1];
});
/* presimplify the topologies (compute the effective area (z) of each point)
*/
topojson.presimplify(data);
/* store all leaf_regions into the ontology tree, and store each node within the feature's properties
*/
map.leaf_regions.forEach(function(f) {
var n;
n = ontology.get_node_from_class(f.properties["class"]);
n.leaf_region = f;
return f.properties.node = n;
});
/* compute merged regions from leaf regions
*/
_merge = function(n, depth) {
n.merged_region = topojson.merge(data, geometries.filter(function(g) {
return g.properties.path.length > depth && g.properties.path[depth] === n.name;
}));
if (n.children != null) {
return n.children.forEach(function(c) {
return _merge(c, depth + 1);
});
}
};
_merge(ontology.tree, 0);
/* compute all region centroids
*/
ontology.nodes.forEach(function(n) {
var _ref;
return _ref = path_generator.centroid(n.merged_region), n.x = _ref[0], n.y = _ref[1], _ref;
});
/* compute all region areas
*/
ontology.nodes.forEach(function(n) {
return n.area = path_generator.area(n.merged_region);
});
/* define readable, plural, multiline labels for level one regions
*/
_readable_labels = {};
ontology.nodes.forEach(function(d) {
_readable_labels[d.name] = d.name.split("/").slice(-1)[0].split("_");
});
ontology.levels[1].forEach(function(n) {
return n.readable_label = _readable_labels[n.name];
});
return ontology.leaves.forEach(function(n) {
if (n.depth > 1 && (n.leaf_region != null)) {
return n.readable_label = _readable_labels[n.name];
}
});
};
Display the source blob
Display the rendered blob
Raw
map.topo.json
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Raw
ontology.js
(function() {
window.ontology = {}
var _index = {}
ontology.init = function(data) {
ontology.tree = data;
// Create support structures for using the tree
_create_index = function(n) {
_index[n.name] = n;
if(n.hasOwnProperty('children'))
n.children.forEach(function(c){
_create_index(c);
});
}
_create_index(ontology.tree);
ontology.levels = [];
ontology.nodes = [];
ontology.leaves = [];
_parse_tree = function(n, depth) {
n.depth = depth;
ontology.nodes.push(n);
// create more levels if needed
if(ontology.levels.length <= depth)
ontology.levels.push([]);
ontology.levels[depth].push(n);
if(n.hasOwnProperty('children'))
n.children.forEach(function(c){
c.parent = n;
_parse_tree(c, depth+1);
});
if(!(n.hasOwnProperty('children')) || n.children.length === 0) {
ontology.leaves.push(n);
}
}
_parse_tree(ontology.tree, 0);
}
// Returns the correct path (sequence of classes ordered according to the ontology hierarchy) given a set of classes
ontology.get_path = function(classes) {
//classes = classes.map(function(c) { return c.value.replace("http://dbpedia.org/ontology/", ""); });
path = [];
classes.forEach(function(c){
var new_path = ontology.get_path_from_class(c);
if(new_path.length > path.length) // WARNING this works only because there are no entities with incompatible types (classes from different branches)
path = new_path;
});
return path;
}
// Returns the tree node corresponding to the given class
ontology.get_node_from_class = function(klass) {
return _index[klass];
}
// Returns the path corresponding to the given class
ontology.get_path_from_class = function(klass) {
var node = ontology.get_node_from_class(klass.value);
return ontology.get_path_from_node(node);
}
// Returns the path corresponding to the given node
ontology.get_path_from_node = function(n) {
if(!(n.hasOwnProperty('parent')))
return [n.name];
return ontology.get_path_from_node(n.parent).concat([n.name])
}
}).call(this);
Raw
ontology.json
{"name": "Thing", "children": [{"name": "http://data.linkedmdb.org/resource/movie/performance", "leaf_count": 197271, "children": []}, {"name": "http://data.linkedmdb.org/resource/oddlinker/interlink", "leaf_count": 162199, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film", "leaf_count": 85620, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/actor", "leaf_count": 50603, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_cut", "leaf_count": 45259, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/writer", "leaf_count": 17335, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_crew_gig", "leaf_count": 17237, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/director", "leaf_count": 17156, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_character", "leaf_count": 15752, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_film_distributor_relationship", "leaf_count": 15256, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/producer", "leaf_count": 14882, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/music_contributor", "leaf_count": 4529, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_job", "leaf_count": 4004, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/editor", "leaf_count": 3290, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/cinematographer", "leaf_count": 3263, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/production_company", "leaf_count": 1926, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_location", "leaf_count": 1315, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_subject", "leaf_count": 1249, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/personal_film_appearance", "leaf_count": 1120, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_story_contributor", "leaf_count": 740, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_festival_event", "leaf_count": 685, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_festival", "leaf_count": 566, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_regional_release_date", "leaf_count": 418, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_genre", "leaf_count": 409, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_art_director", "leaf_count": 365, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_costume_designer", "leaf_count": 353, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_company", "leaf_count": 338, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_production_designer", "leaf_count": 293, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_casting_director", "leaf_count": 273, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/country", "leaf_count": 247, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_set_designer", "leaf_count": 206, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_series", "leaf_count": 205, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_distributor", "leaf_count": 169, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_critic", "leaf_count": 152, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_awards_ceremony", "leaf_count": 127, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/dubbing_performance", "leaf_count": 118, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/content_rating", "leaf_count": 107, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_featured_song", "leaf_count": 72, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_festival_sponsor", "leaf_count": 70, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_format", "leaf_count": 57, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/content_rating_system", "leaf_count": 46, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_film_company_relationship", "leaf_count": 36, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_theorist", "leaf_count": 28, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_crewmember", "leaf_count": 25, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_screening_venue", "leaf_count": 23, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_festival_focus", "leaf_count": 13, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/special_film_performance_type", "leaf_count": 11, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_distribution_medium", "leaf_count": 10, "children": []}, {"name": "http://data.linkedmdb.org/resource/oddlinker/linkage_run", "leaf_count": 7, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/personal_film_appearance_type", "leaf_count": 5, "children": []}, {"name": "http://data.linkedmdb.org/resource/movie/film_collection", "leaf_count": 1, "children": []}, {"name": "http://data.linkedmdb.org/resource/untyped", "leaf_count": 28959, "children": []}]}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment