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.

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.

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

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.

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.

https://github.com/d3/d3-polygon#polygonContains has a broken link to https://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

https://web.archive.org/web/20161116163747/https://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

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.

this would be so cool! in the C# world i have used the excellent CLIPPER library: http://www.angusj.com/delphi/clipper.php

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.

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.)

The test below shows that the expected result is clockwise, not counterclockwise as mention in the documentation.

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 ?

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?

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;
}

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.

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.

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.

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;

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!

Wouldn’t it make more sense to have clockwise polygons be positive? I can’t remember why we chose this convention.