d3 / d3-polygon Goto Github PK
View Code? Open in Web Editor NEWGeometric operations for two-dimensional polygons.
Home Page: https://d3js.org/d3-polygon
License: ISC License
Geometric operations for two-dimensional polygons.
Home Page: https://d3js.org/d3-polygon
License: ISC License
It might be nice to have a slightly larger module containing d3-hull, d3-quadtree, d3-polygon, d3-voronoi… and whatever else we imagine in the future.
I am working on geo coordinates and needed to check if the point is inside the polygon, what i found is an issue whenever the condition is met the inside flag is flipped in my case it is always showing me false.
https://github.com/d3/d3-polygon/blob/master/src/contains.js#L11
Shouldn't it be like if it matches once it should be considered inside.
Although it’s pretty trivial to take a polygon and render it to a Canvas 2D context or an SVG path string, I wonder if it would be beneficial to make some explicit support for rendering in this package. (Related d3/d3-hexbin#1.) An interesting use case to consider is how to render the output of d3-voronoi.
Wouldn’t it make more sense to have clockwise polygons be positive? I can’t remember why we chose this convention.
d3-polygon currently has d3.polygonHull(points) that returns the convex hull of the specified points. For some applications, it would be handy to calculate the concave hull of a set of points.
Either, the existing method could add a second parameter type (with currently supported values being convex and concave, or, the existing method could be renamed to d3.polygonHullConvex(points) and a new method d3.polygonHullConcave(points) could be added.
Hi,
I'm using d3-polygon
's functions on a large amount of nodes during a force simulation.
The problem is, a point in d3-polygon
is an array [x<Number>, y<Number>]
while a node in d3-force
is {x: <Number>, y: <Number>, ...}
, hence converting nodes to [x, y]
slows down the simulation because of temporary arrays being garbage collected all the time.
As an example, since polygonHull
requires [[x1, y1], [x2, y2], …]
I need to do d3.polygonHull(nodes.map(node => [node.x, node.y]))
.
It would be useful to have x, y accessors to get node.x
and node.y
by reference and eventually avoiding the cost of duplication.
What do you think?
One approach would be to specify x
, y
accessors in all d3-polygon
's functions arguments, but I'd prefer to consume an API similar to the rest of d3:
// data is an array of generic objects
d3.polygon([data])
.x(fn)
.y(fn)
.vertices([data])
.hullOf(data) // calculates the hull and stores the resulting polygon's vertices (not the input points)
.area()
.centroid()
.length()
.contains(point)
If it helps I'm willing to try a PR, basically imitating the voronoi approach.
Thanks!
Hi,
is it planned to include more polygon-algorithms in this library?
For example a circle intersection test like in:
https://bl.ocks.org/mbostock/4218871
I have created a block for you to view which shows the error very clearly here:
http://bl.ocks.org/Anupheaus/f79c12c2cec45caa9dfd1e6466663ef2
Basically, the issue is that when you add a new array of points to the hull data, two of the new points seem to affect the hull before the transition is applied. This only happens if the points being added are to the right of the original point, so if the second point was to the left of the first point, it doesn't happen.
Hello, I am porting an existing code-base that is using an old version of d3 to the new version.
In this old code-base, polygons are generated using d3.geom.polygon
. the package https://www.npmjs.com/package/d3-geom-polygon is being moved to d3-polygon but unfortunately I do not see an equivalent of this function, polygonHull it is accepting points as argument but it is doing something different. What I am looking at, is a function that accepts points and gives me back a polygon.
Since the polygon points are a simple string of "x1,y1 x2,y2, ... xn,yn" in the SVG XML, I found it much simpler to modify your polygonArea function to utilize the string values rather than try to convert to your expected nested arrays. Very minor tweaks adding a few splits, but it seems much more friendly for working with polygons on the fly. Feel free to incorporate them if you find them useful.
var svgDoc = document.getElementById("svg");
var string = d3.event.target.id;
var poly = d3.select(svgDoc).select("polygon#" + string);
var points = poly.attr("points");
var polygon = points.split(" ");
var i = 0,
n = polygon.length - 1,
a,
b = polygon[n].split(","),
area = 0;
while (i++ < n) {
a = b;
b = polygon[i].split(",");
area += a[1] * b[0] - a[0] * b[1];
}
area /= 2;
var d3Polygon = require("d3-polygon")
var unitSquare = [[0,0], [0,1], [1,1], [1,0]];
var polygonContains = d3Polygon.polygonContains;
unitSquare.forEach( p => console.log(`[${p}] in unitSquare : ${polygonContains(unitSquare, p)}`));
>"[0,0] in unitSquare : true"
>"[0,1] in unitSquare : false"
>"[1,1] in unitSquare : false"
>"[1,0] in unitSquare : false"
In Runkit => https://runkit.com/embed/tht1jbzi6iqq
Imho, all the verteces of the polygon should be either inside or outside.
Is it worth having some sort of polygon clipping functionality?
Note: d3-voronoi implements its own clipping of infinite cells. And d3-geo-projection will need to have an equivalent of d3.geo.clipExtent.
According to d3 v3 vs v4 change log, there is no polygon constructor anymore.
However, the d3.geoArea
function take a polygon as an argument (see documentation), and does not work with a list of coordinates.
(I run into this issue because when trying to simplify a multipolygon: I cannot compute the area each of the sub-polygons.)
this would be so cool! in the C# world i have used the excellent CLIPPER library: http://www.angusj.com/delphi/clipper.php
ie. all the points in the 2nd polygon's array are contained in the 1st polygon
or is it so straigthforward there's no point in adding it?
Line Intersection is much simpler than clipping (#4), at least if we don't care for the difficult cases. It would be useful, for example, in quadtree.findInPolygon (d3/d3-quadtree#30 & https://observablehq.com/d/54a6e96b6630b0d9). [EDIT] findInPolygon is not staying.
The test below shows that the expected result is clockwise, not counterclockwise as mention in the documentation.
Line 12 in 1bfcdc8
Is it due to the fact that the y-axis direction of SVGs is going down the screen, and hence inverting some common computation results ?
From d3.geo.clipExtent:
function insidePolygon(p) {
var wn = 0, // the winding number counter
n = polygon.length,
y = p[1];
for (var i = 0; i < n; ++i) {
for (var j = 1, v = polygon[i], m = v.length, a = v[0], b; j < m; ++j) {
b = v[j];
if (a[1] <= y) {
if (b[1] > y && d3_cross2d(a, b, p) > 0) ++wn;
} else {
if (b[1] <= y && d3_cross2d(a, b, p) < 0) --wn;
}
a = b;
}
}
return wn !== 0;
}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.