saifuddin778/README.md

## README.md

      
    Raw
  

              README.md
            
          
    A different approach towards implementing quadtree without d3's inherent quadtree. Also, hovering over each point reflects its k nearest neighbors (k=10).

  
## index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
    body {
        text-align: center;
    }
    svg {
        background: none;
    }
    .rect {
        fill: rgba(30, 130, 76, 0.1);
        stroke: gray;
        stroke-width: 1;
        shape-rendering: crispEdges;
    }
</style>
<script src="http://code.jquery.com/jquery-1.8.3.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
<body>
    <script>
        d3.selection.prototype.moveToFront = function() {
            return this.each(function() {
                this.parentNode.appendChild(this);
            });
        };

        function get_mp(p1, p2) {
            return [(p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2];
        }

        function get_range_points(quad, n_) {
            var min_x = quad[0][0];
            var max_x = quad[3][0];

            var min_y = quad[1][1];
            var max_y = quad[3][1];

            var proceed = false;
            var ncount = 0;

            d3.selectAll(".node").filter(function(d) {
                return (d.x > min_x && d.x < max_x) && (d.y > min_y && d.y < max_y);
            }).each(function(u) {
                if (u.p in reg) {
                    reg[u.p].push(n_);
                } else {
                    reg[u.p] = [n_];
                }
                ncount += 1;
            });

            if (ncount > 4) {
                proceed = true;
            }
            return proceed;
        }


        function get_polygon_points(points) {
            //concatenates quadrant coordinate points as a polygon points string
            var pts = "";
            for (var i = 0; i < points.length; i++) {
                for (var j = 0; j < points[i].length; j++) {
                    if (i < points.length - 1) {
                        pts += points[i][j] + ",";
                    } else {
                        pts += points[i][j] + " ";
                    }
                }
                pts += " "
            }
            return pts;
        }

        function get_wh(points) {
            return {
                w: points[0],
                h: points[1]
            };
        }

        function get_quadrants(quadrants) {
            //returns all 4 quadrants (along with their respective centroids)
            //of the rectangular space, based on its coordinates.
            var pp = {};
            for (var i = 0; i < quadrants.length; i++) {
                pp[i] = get_wh(quadrants[i]);
            }
            var quads = [{
                c: get_mp([pp[0].w, pp[0].h], [(pp[0].w + pp[3].w) / 2, (pp[0].h + pp[1].h) / 2]),
                p: [

                    [pp[0].w, pp[0].h],
                    [pp[0].w, (pp[0].h + pp[1].h) / 2],
                    [(pp[0].w + pp[3].w) / 2, (pp[0].h + pp[1].h) / 2],
                    [(pp[0].w + pp[3].w) / 2, pp[0].h],

                ]
            }, {
                c: get_mp([pp[0].w, (pp[0].h + pp[1].h) / 2], [(pp[1].w + pp[2].w) / 2, pp[1].h]),
                p: [
                    [pp[0].w, (pp[0].h + pp[1].h) / 2],
                    [pp[1].w, pp[1].h],
                    [(pp[1].w + pp[2].w) / 2, pp[1].h],
                    [(pp[0].w + pp[3].w) / 2, (pp[0].h + pp[1].h) / 2],
                ]
            }, {
                c: get_mp([(pp[0].w + pp[3].w) / 2, (pp[0].h + pp[1].h) / 2], [pp[2].w, pp[2].h]),
                p: [
                    [(pp[0].w + pp[3].w) / 2, (pp[0].h + pp[1].h) / 2],
                    [(pp[1].w + pp[2].w) / 2, pp[1].h],
                    [pp[2].w, pp[2].h],
                    [pp[2].w, (pp[2].h + pp[3].h) / 2]
                ]
            }, {
                c: get_mp([(pp[0].w + pp[3].w) / 2, pp[0].h], [pp[2].w, (pp[2].h + pp[3].h) / 2]),
                p: [
                    [(pp[0].w + pp[3].w) / 2, pp[0].h],
                    [(pp[0].w + pp[3].w) / 2, (pp[0].h + pp[1].h) / 2],
                    [pp[2].w, (pp[2].h + pp[3].h) / 2],
                    [pp[3].w, pp[3].h]
                ]
            }];
            return quads;
        }

        var width = 960;
        var height = 500;
        var reg = {};
        var n_points = 1200;
        var n_ = 0;
        var rand = Math.random;

        var points = d3.range(n_points).map(function(d, i) {
            return {
                x: rand() * width,
                y: rand() * height,
                p: i,
                color: "crimson",
            };
        });

        var svg = d3.select('body').append('svg').attr('width', width).attr('height', height);
        svg.selectAll("circle").data(points).enter()
            .append("circle")
            .attr("class", "node")
            .attr("cx", function(d) {
                return d.x
            })
            .attr("cy", function(d) {
                return d.y
            })
            .attr("r", 2)
            .attr("p", function(d) {
                return d.p
            })
            .style("fill", function(d) {
                return d.color
            })
            .style("stroke", "black")
            .style("stroke-width", 0.5)
            .on("mouseover", function(d) {
                highlight_neighbors(d);
            })
            .on("mouseout",
                disable_highlight
            );

        var quadrants = [
            [
                [0, height],
                [0, 0],
                [width, 0],
                [width, height]
            ]
        ];

        for (var i = 0; i < quadrants.length; i++) {
            var quads = get_quadrants(quadrants[i]);
            for (var j = 0; j < quads.length; j++) {
                var proceed = get_range_points(quads[j].p, n_);
                if (proceed) {
                    quadrants.push(quads[j].p);
                }
                append_(quads[j].p, quads[j].c, n_);
                n_ += 1;
            }
        }

        //move points to front, sir.
        d3.selectAll('circle').moveToFront();

        function append_(ppoints, c, n_) {
            var pts_ = get_polygon_points(ppoints);
            svg.append("polygon").attr("class", "rect").attr("points", pts_).attr("n_", n_);
            svg.append("text").attr("x", c[0]).attr("y", c[1]).text(n_).style("font-size", "6px");
            return;
        }

        function euc_(p1, p2) {
            return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
        }

        function highlight_neighbors(d) {
            points
                .sort(function(a, b) {
                    return euc_(a, d) - euc_(b, d)
                })
                .slice(0, 10)
                .map(function(g, i) {
                    d3.selectAll('.node').filter(function(u) {
                        return u.p == g.p;
                    }).style("fill", "black")
                });

            var all_rect = $('.rect');
            var rects = reg[+d.p];
            for (var i = 0; i < rects.length; i++) {
                $(all_rect[rects[i]])
                    .css("stroke-width", 1.5)
                    .css("fill", "rgba(30, 130, 76, 0.3)");
            }
            d3.event.stopPropagation();
            return;
        }

        function disable_highlight() {
            d3.selectAll(".node").style("fill", function(d) {
                return d.color;
            })
            d3.selectAll(".rect")
                .style("stroke", "gray")
                .style("stroke-width", 1)
                .style("fill", "rgba(30, 130, 76, 0.1)");
            d3.event.stopPropagation();
            return;
        }
    </script>
</body>

## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!DOCTYPE html>
	<meta charset="utf-8">
	<style>
	body {
	text-align: center;
	}
	svg {
	background: none;
	}
	.rect {
	fill: rgba(30, 130, 76, 0.1);
	stroke: gray;
	stroke-width: 1;
	shape-rendering: crispEdges;
	}
	</style>
	<script src="http://code.jquery.com/jquery-1.8.3.min.js"></script>
	<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
	<body>
	<script>
	d3.selection.prototype.moveToFront = function() {
	return this.each(function() {
	this.parentNode.appendChild(this);
	});
	};

	function get_mp(p1, p2) {
	return [(p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2];
	}

	function get_range_points(quad, n_) {
	var min_x = quad[0][0];
	var max_x = quad[3][0];

	var min_y = quad[1][1];
	var max_y = quad[3][1];

	var proceed = false;
	var ncount = 0;

	d3.selectAll(".node").filter(function(d) {
	return (d.x > min_x && d.x < max_x) && (d.y > min_y && d.y < max_y);
	}).each(function(u) {
	if (u.p in reg) {
	reg[u.p].push(n_);
	} else {
	reg[u.p] = [n_];
	}
	ncount += 1;
	});

	if (ncount > 4) {
	proceed = true;
	}
	return proceed;
	}


	function get_polygon_points(points) {
	//concatenates quadrant coordinate points as a polygon points string
	var pts = "";
	for (var i = 0; i < points.length; i++) {
	for (var j = 0; j < points[i].length; j++) {
	if (i < points.length - 1) {
	pts += points[i][j] + ",";
	} else {
	pts += points[i][j] + " ";
	}
	}
	pts += " "
	}
	return pts;
	}

	function get_wh(points) {
	return {
	w: points[0],
	h: points[1]
	};
	}

	function get_quadrants(quadrants) {
	//returns all 4 quadrants (along with their respective centroids)
	//of the rectangular space, based on its coordinates.
	var pp = {};
	for (var i = 0; i < quadrants.length; i++) {
	pp[i] = get_wh(quadrants[i]);
	}
	var quads = [{
	c: get_mp([pp[0].w, pp[0].h], [(pp[0].w + pp[3].w) / 2, (pp[0].h + pp[1].h) / 2]),
	p: [

	[pp[0].w, pp[0].h],
	[pp[0].w, (pp[0].h + pp[1].h) / 2],
	[(pp[0].w + pp[3].w) / 2, (pp[0].h + pp[1].h) / 2],
	[(pp[0].w + pp[3].w) / 2, pp[0].h],

	]
	}, {
	c: get_mp([pp[0].w, (pp[0].h + pp[1].h) / 2], [(pp[1].w + pp[2].w) / 2, pp[1].h]),
	p: [
	[pp[0].w, (pp[0].h + pp[1].h) / 2],
	[pp[1].w, pp[1].h],
	[(pp[1].w + pp[2].w) / 2, pp[1].h],
	[(pp[0].w + pp[3].w) / 2, (pp[0].h + pp[1].h) / 2],
	]
	}, {
	c: get_mp([(pp[0].w + pp[3].w) / 2, (pp[0].h + pp[1].h) / 2], [pp[2].w, pp[2].h]),
	p: [
	[(pp[0].w + pp[3].w) / 2, (pp[0].h + pp[1].h) / 2],
	[(pp[1].w + pp[2].w) / 2, pp[1].h],
	[pp[2].w, pp[2].h],
	[pp[2].w, (pp[2].h + pp[3].h) / 2]
	]
	}, {
	c: get_mp([(pp[0].w + pp[3].w) / 2, pp[0].h], [pp[2].w, (pp[2].h + pp[3].h) / 2]),
	p: [
	[(pp[0].w + pp[3].w) / 2, pp[0].h],
	[(pp[0].w + pp[3].w) / 2, (pp[0].h + pp[1].h) / 2],
	[pp[2].w, (pp[2].h + pp[3].h) / 2],
	[pp[3].w, pp[3].h]
	]
	}];
	return quads;
	}

	var width = 960;
	var height = 500;
	var reg = {};
	var n_points = 1200;
	var n_ = 0;
	var rand = Math.random;

	var points = d3.range(n_points).map(function(d, i) {
	return {
	x: rand() * width,
	y: rand() * height,
	p: i,
	color: "crimson",
	};
	});

	var svg = d3.select('body').append('svg').attr('width', width).attr('height', height);
	svg.selectAll("circle").data(points).enter()
	.append("circle")
	.attr("class", "node")
	.attr("cx", function(d) {
	return d.x
	})
	.attr("cy", function(d) {
	return d.y
	})
	.attr("r", 2)
	.attr("p", function(d) {
	return d.p
	})
	.style("fill", function(d) {
	return d.color
	})
	.style("stroke", "black")
	.style("stroke-width", 0.5)
	.on("mouseover", function(d) {
	highlight_neighbors(d);
	})
	.on("mouseout",
	disable_highlight
	);

	var quadrants = [
	[
	[0, height],
	[0, 0],
	[width, 0],
	[width, height]
	]
	];

	for (var i = 0; i < quadrants.length; i++) {
	var quads = get_quadrants(quadrants[i]);
	for (var j = 0; j < quads.length; j++) {
	var proceed = get_range_points(quads[j].p, n_);
	if (proceed) {
	quadrants.push(quads[j].p);
	}
	append_(quads[j].p, quads[j].c, n_);
	n_ += 1;
	}
	}

	//move points to front, sir.
	d3.selectAll('circle').moveToFront();

	function append_(ppoints, c, n_) {
	var pts_ = get_polygon_points(ppoints);
	svg.append("polygon").attr("class", "rect").attr("points", pts_).attr("n_", n_);
	svg.append("text").attr("x", c[0]).attr("y", c[1]).text(n_).style("font-size", "6px");
	return;
	}

	function euc_(p1, p2) {
	return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
	}

	function highlight_neighbors(d) {
	points
	.sort(function(a, b) {
	return euc_(a, d) - euc_(b, d)
	})
	.slice(0, 10)
	.map(function(g, i) {
	d3.selectAll('.node').filter(function(u) {
	return u.p == g.p;
	}).style("fill", "black")
	});

	var all_rect = $('.rect');
	var rects = reg[+d.p];
	for (var i = 0; i < rects.length; i++) {
	$(all_rect[rects[i]])
	.css("stroke-width", 1.5)
	.css("fill", "rgba(30, 130, 76, 0.3)");
	}
	d3.event.stopPropagation();
	return;
	}

	function disable_highlight() {
	d3.selectAll(".node").style("fill", function(d) {
	return d.color;
	})
	d3.selectAll(".rect")
	.style("stroke", "gray")
	.style("stroke-width", 1)
	.style("fill", "rgba(30, 130, 76, 0.1)");
	d3.event.stopPropagation();
	return;
	}
	</script>
	</body>