Distinguishing exterior rings from holes

[xaviergonz]

How can I distinguish exterior rings from holes in the results?

As an idea, the library could use a GeoJson alike format of polygons+multipolygons inputs/outputs to handle this case.

[velipso]

The algorithm doesn't actually output polygons with holes. This isn't intentional, but a nice side-effect of the chaining process.

If you look at the demo here:

https://rawgit.com/voidqk/polybooljs/master/dist/demo.html

In the first demo ("1. Assorted Polygons"), it looks like the output has holes in it -- but if you step through the animation towards the end, where the segments are being chained together and turning green, you'll notice that the final result doesn't actually have any holes.

This screenshot is one step before the final result (i.e., hit the "Prev" button twice under "Animation:").

The "hole" is made by two polygons that touch at similar points, but it isn't an actual hole in a single polygon.

As far as GeoJson goes, I'm not sure what that is, or how it will help. Maybe you could explain that further.

[xaviergonz]

Hi, thanks for replying.

Basically my final idea is to pass the resulting polygon to render it to screen. At first I thought of using a non-zero filling rule, but that requires results with certain constraints, namely:

• External shell polygons to have a counter-clockwise winding
• Holes to have a clockwise winding.

After a bit more thought I think I could simply use a even-odd filling rule, which doesn't take into account the polygon winding, is this right?

--

As for GeoJson (https://en.wikipedia.org/wiki/GeoJSON) it is some sort of semi-standard way to serialize geometric figures (points, lines, etc). That page on wikipedia have nice examples on the format of each one, but basically I'd say that the input and output of this lib are basically either Polygons or Multipolygons, only that the current output format doesn't allow distinguishing outer shells from holes inside those outer shells, making the conversion costly.

You may see here for a related discussion on a similar library: w8r/martinez#5

[velipso]

Ah, now I see what you mean when you talk about holes!

You can see how I perform a fill on the demo page:

function drawRegions(regions, offset){
	regions.forEach(function(region, i){
		if (region.length <= 0)
			return;
		ctx.moveTo(scaleX(region[0][0]), scaleY(region[0][1]) + offset);
		for (var i = 1; i < region.length; i++)
			ctx.lineTo(scaleX(region[i][0]), scaleY(region[i][1]) + offset);
		ctx.closePath();
	});
}

function polyStroke(result, offset){
	ctx.beginPath();
	drawRegions(result.regions, offset);
	ctx.stroke();
}

function polyFill(result, rect1, rect2, offset){
	ctx.beginPath();
	if (result.inverted){
		ctx.moveTo(rect1[0], rect1[1] + offset);
		ctx.lineTo(rect1[0], rect2[1] + offset);
		ctx.lineTo(rect2[0], rect2[1] + offset);
		ctx.lineTo(rect2[0], rect1[1] + offset);
		ctx.closePath();
	}
	drawRegions(result.regions, offset);
	ctx.fill('evenodd');
}

Clockwise and counter-clockwise don't matter -- only the fact that it's an even/odd rule.

--

As for the GeoJSON Polygon, here is the spec:

https://tools.ietf.org/html/rfc7946#section-3.1.6

If I'm understanding this correctly, then a polybooljs polygon should be able to be converted to a GeoJSON Polygon (and vice-versa)... it would simply be a matter of embedding the inverted flag into the winding of the result.

So in theory, that should be possible. Off the top of my head, I don't know exactly how to do that though. You would have to find the outer-most polygon, and change its winding to match the inverted flag, and then alternate windings for polygons inside it..?

I would be open to including utility functions in polybooljs to perform these conversions. But I'm too busy to research and write them myself at the moment.

[velipso]

Also, I just thought of this: GeoJSON must enforce a coordinate system (is positive Y up or down?), in order to define winding. Polybooljs doesn't care about the direction of positive Y.

[velipso]

GeoJSON support was just pushed for v1.2.0, let me know what you think in Issue #7.