Last active
April 27, 2016 09:55
-
-
Save fabiovalse/e7d2d1eba207b0a979ad to your computer and use it in GitHub Desktop.
Non-overlapping regions through collision detection
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| svg { | |
| /*background: #E0F2F4;*/ | |
| } | |
| .leaf_region { | |
| fill: red; | |
| opacity: 0.7; | |
| } | |
| circle { | |
| fill: none; | |
| stroke: brown; | |
| stroke-width: 0.3px; | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!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> |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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]; | |
| } | |
| }); | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (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); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| {"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