r-suen/README.md

## README.md

      
    Raw
  

              README.md
            
          
    Rendering Natural Earth populated places by longitude and latitude using D3 quadtree and data joins. A quadtree can significantly reduce the number of data point comparisons. Using longitude and latitude for the quadtree x- and y- coordinates allows for scanning after map projections and zoom behaviors.
The mouse extent searches the quadtree for nearby points. The search extent needs to be adjusted from xy min max to longitude latitude min max coordinates. Scanned points are marked orange. Selected points are marked red.
Press spacebar to toggle all places.

Pan and zoom the map with the mouse.

  
## index.html
<!DOCTYPE html>
<html>
    <head>
        <meta charset='utf-8' />
        <title>Quadtree Longitude Latitude</title>
        <script src='https://cdnjs.cloudflare.com/ajax/libs/d3/4.10.0/d3.min.js'></script>
        <script src='https://cdnjs.cloudflare.com/ajax/libs/topojson/3.0.0/topojson.min.js'></script>
    </head>
        <style>
            body {
                margin: 0;
                overflow: hidden;
            }

            #stats {
                position: absolute;
                top: 10px;
                left: 10px;
                pointer-events: none;
                text-shadow: #fc0 1px 0 10px;
            }

            .hidden {
                display: none;
            }

            .land {
                fill: #ccc;
            }

            .border {
                fill: none;
                stroke: #fff;
            }

            .point {
                fill: blue;
            }

            .scanned.point {
                fill: orange;
                stroke: orange;
                stroke-width: 4px;
            }

            .selected.point {
                fill: red;
                stroke: red;
                stroke-width: 5px;
            }

            .brush {
                fill: #000;
                opacity: 0.4;
            }

        </style>
    <body>
        <div id="container"></div>
        <div id="stats"></div>
    	<script>
            var width = window.innerWidth,
                height = window.innerHeight;

            var svg = d3.select('#container').append('svg')
                .attr('width', width)
                .attr('height', height);

            var g = svg.append('g');

            var brush = svg.append('rect')
                .attr('x', 100)
                .attr('y', 100)
                .attr('width', 100)
                .attr('height', 100)
                .attr('class', 'brush');

            var projection = d3.geoMercator()
                .translate([width / 2, height / 2]);

            var path = d3.geoPath(projection)
                .pointRadius(2);

            var zoom = d3.zoom()
                .scaleExtent([1, 1 << 5])
                .on('zoom', zoomed);

            var transform = d3.zoomTransform(svg.node());

            var land,
                border,
                places;

            var quadtree;

            var spaceKey = false;

            var origin = projection([0, 0]);

            d3.json('world-110m.json', function(error, data) {
                if (error) throw error;

                land = topojson.merge(data, data.objects.countries.geometries);
                border = topojson.mesh(data, data.objects.countries, function(a, b) { return a !== b; });

                g.append('path')
                    .datum(land)
                    .attr('d', path)
                    .attr('class', 'land');

                g.append('path')
                    .datum(border)
                    .attr('d', path)
                    .attr('class', 'border');

                d3.json('places-10m.json', function(error, data) {
                    if (error) throw error;

                    places = topojson.feature(data, data.objects.places);

                    let lnglat = places.features.map(d => d.geometry.coordinates);
                    quadtree = d3.quadtree(lnglat);

                    let point = g.selectAll('.point')
                        .data(places.features)
                      .enter().append('path')
                        .attr('d', path)
                        .attr('class', 'point');

                    svg.call(zoom);
                    svg.on('mousemove', mousemoved);
                });
            });

            document.addEventListener("keydown", keydown, false);

            function mousemoved() {
                if (spaceKey) return;

                let m = d3.mouse(this),
                    bl = [m[0] - 50, m[1] + 50],
                    tr = [m[0] + 50, m[1] - 50],
                    lnglatbl = projection.invert([(bl[0] - transform.x) / transform.k, (bl[1] - transform.y) / transform.k]),
                    lnglattr = projection.invert([(tr[0] - transform.x) / transform.k, (tr[1] - transform.y) / transform.k]);

                // check if brush extent spans across the antimeridian
                if (lnglatbl[0] > lnglattr[0]) {
                    if (m[0] - transform.x >= origin[0]) {
                        lnglattr[0] += 360;
                    } else if (m[0] - transform.x < origin[0]) {
                        lnglatbl[0] -= 360;
                    }
                }

                // brush extent bounding box uses dimensions [[left, bottom], [right, top]]
                brush
                    .attr('x', bl[0])
                    .attr('y', tr[1])
                    .classed('hidden', false);

                let subset = search(quadtree, lnglatbl[0], lnglatbl[1], lnglattr[0], lnglattr[1]);

                let point = g.selectAll('.point')
                    .data(subset, d => d);

                point.enter().append('path')
                    .attr('d', d => path({ "type": "Point", "coordinates": [d[0], d[1]]}))
                    .attr('class', 'point')
                    .classed('scanned', d => d.scanned)
                    .classed('selected', d => d.selected);

                point.classed('scanned', d => d.scanned);
                point.classed('selected', d => d.selected);

                point.exit().remove();

                showStats();
            }

            function search(quadtree, x0, y0, x3, y3) {
                let pts = [];
                quadtree.visit(function(node, x1, y1, x2, y2) {
                    if (!node.length) { // is leaf
                        do {
                            var d = node.data; // node data bound to d.geometry.coordinates
                            d.scanned = true;
                            d.selected = (d[0] >= x0) && (d[0] < x3) && (d[1] >= y0) && (d[1] < y3);
                            if (d.scanned) pts.push(d);
                        } while (node = node.next);
                    }
                    return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0;
                });

                return pts;
            }

            function zoomed() {
                brush.classed('hidden', true);

                transform = d3.zoomTransform(this);
                g.attr('transform', transform);

                d3.selectAll('.border')
                    .attr('stroke-width', 1 / transform.k);
            }

            function showStats() {
                document.getElementById("stats").innerHTML = "Total data points: " + quadtree.size() + "<br>"
                                + "Scanned points: " + d3.selectAll('.scanned').size() + "<br>"
                                + "Selected points: "  + d3.selectAll('.selected').size();
            }

            function keydown(e) {
                if (e.keyCode === 32) { // spacebar key
                    spaceKey = !spaceKey;

                    let point = g.selectAll('.point')
                        .data(places.features)
                      .enter().append('path')
                        .attr('d', path)
                        .attr('class', 'point');
                }

                showStats();
            }

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

## places-10m.json

      
Display the source blob

    
Display the rendered blob

    
    Raw
  

              places-10m.json
            
          
        Loading

      Sorry, something went wrong. Reload?
      Sorry, we cannot display this file.
      Sorry, this file is invalid so it cannot be displayed.
      
          Viewer requires iframe.
      
    
## thumbnail.png

      
    Raw
  

              thumbnail.png
            
          
## world-110m.json

      
    Raw
  

              world-110m.json
            
          
            View raw
              (Sorry about that, but we can’t show files that are this big right now.)
	<!DOCTYPE html>
	<html>
	<head>
	<meta charset='utf-8' />
	<title>Quadtree Longitude Latitude</title>
	<script src='https://cdnjs.cloudflare.com/ajax/libs/d3/4.10.0/d3.min.js'></script>
	<script src='https://cdnjs.cloudflare.com/ajax/libs/topojson/3.0.0/topojson.min.js'></script>
	</head>
	<style>
	body {
	margin: 0;
	overflow: hidden;
	}

	#stats {
	position: absolute;
	top: 10px;
	left: 10px;
	pointer-events: none;
	text-shadow: #fc0 1px 0 10px;
	}

	.hidden {
	display: none;
	}

	.land {
	fill: #ccc;
	}

	.border {
	fill: none;
	stroke: #fff;
	}

	.point {
	fill: blue;
	}

	.scanned.point {
	fill: orange;
	stroke: orange;
	stroke-width: 4px;
	}

	.selected.point {
	fill: red;
	stroke: red;
	stroke-width: 5px;
	}

	.brush {
	fill: #000;
	opacity: 0.4;
	}

	</style>
	<body>
	<div id="container"></div>
	<div id="stats"></div>
	<script>
	var width = window.innerWidth,
	height = window.innerHeight;

	var svg = d3.select('#container').append('svg')
	.attr('width', width)
	.attr('height', height);

	var g = svg.append('g');

	var brush = svg.append('rect')
	.attr('x', 100)
	.attr('y', 100)
	.attr('width', 100)
	.attr('height', 100)
	.attr('class', 'brush');

	var projection = d3.geoMercator()
	.translate([width / 2, height / 2]);

	var path = d3.geoPath(projection)
	.pointRadius(2);

	var zoom = d3.zoom()
	.scaleExtent([1, 1 << 5])
	.on('zoom', zoomed);

	var transform = d3.zoomTransform(svg.node());

	var land,
	border,
	places;

	var quadtree;

	var spaceKey = false;

	var origin = projection([0, 0]);

	d3.json('world-110m.json', function(error, data) {
	if (error) throw error;

	land = topojson.merge(data, data.objects.countries.geometries);
	border = topojson.mesh(data, data.objects.countries, function(a, b) { return a !== b; });

	g.append('path')
	.datum(land)
	.attr('d', path)
	.attr('class', 'land');

	g.append('path')
	.datum(border)
	.attr('d', path)
	.attr('class', 'border');

	d3.json('places-10m.json', function(error, data) {
	if (error) throw error;

	places = topojson.feature(data, data.objects.places);

	let lnglat = places.features.map(d => d.geometry.coordinates);
	quadtree = d3.quadtree(lnglat);

	let point = g.selectAll('.point')
	.data(places.features)
	.enter().append('path')
	.attr('d', path)
	.attr('class', 'point');

	svg.call(zoom);
	svg.on('mousemove', mousemoved);
	});
	});

	document.addEventListener("keydown", keydown, false);

	function mousemoved() {
	if (spaceKey) return;

	let m = d3.mouse(this),
	bl = [m[0] - 50, m[1] + 50],
	tr = [m[0] + 50, m[1] - 50],
	lnglatbl = projection.invert([(bl[0] - transform.x) / transform.k, (bl[1] - transform.y) / transform.k]),
	lnglattr = projection.invert([(tr[0] - transform.x) / transform.k, (tr[1] - transform.y) / transform.k]);

	// check if brush extent spans across the antimeridian
	if (lnglatbl[0] > lnglattr[0]) {
	if (m[0] - transform.x >= origin[0]) {
	lnglattr[0] += 360;
	} else if (m[0] - transform.x < origin[0]) {
	lnglatbl[0] -= 360;
	}
	}

	// brush extent bounding box uses dimensions [[left, bottom], [right, top]]
	brush
	.attr('x', bl[0])
	.attr('y', tr[1])
	.classed('hidden', false);

	let subset = search(quadtree, lnglatbl[0], lnglatbl[1], lnglattr[0], lnglattr[1]);

	let point = g.selectAll('.point')
	.data(subset, d => d);

	point.enter().append('path')
	.attr('d', d => path({ "type": "Point", "coordinates": [d[0], d[1]]}))
	.attr('class', 'point')
	.classed('scanned', d => d.scanned)
	.classed('selected', d => d.selected);

	point.classed('scanned', d => d.scanned);
	point.classed('selected', d => d.selected);

	point.exit().remove();

	showStats();
	}

	function search(quadtree, x0, y0, x3, y3) {
	let pts = [];
	quadtree.visit(function(node, x1, y1, x2, y2) {
	if (!node.length) { // is leaf
	do {
	var d = node.data; // node data bound to d.geometry.coordinates
	d.scanned = true;
	d.selected = (d[0] >= x0) && (d[0] < x3) && (d[1] >= y0) && (d[1] < y3);
	if (d.scanned) pts.push(d);
	} while (node = node.next);
	}
	return x1 >= x3 \|\| y1 >= y3 \|\| x2 < x0 \|\| y2 < y0;
	});

	return pts;
	}

	function zoomed() {
	brush.classed('hidden', true);

	transform = d3.zoomTransform(this);
	g.attr('transform', transform);

	d3.selectAll('.border')
	.attr('stroke-width', 1 / transform.k);
	}

	function showStats() {
	document.getElementById("stats").innerHTML = "Total data points: " + quadtree.size() + "<br>"
	+ "Scanned points: " + d3.selectAll('.scanned').size() + "<br>"
	+ "Selected points: " + d3.selectAll('.selected').size();
	}

	function keydown(e) {
	if (e.keyCode === 32) { // spacebar key
	spaceKey = !spaceKey;

	let point = g.selectAll('.point')
	.data(places.features)
	.enter().append('path')
	.attr('d', path)
	.attr('class', 'point');
	}

	showStats();
	}

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