This is not a huge priority to have right now, but I was wondering if you guys have thought about it, or if it is even currently possible to do. Other map products like arcgis js and openlayers have the capability to punch holes into a polygon defined as other internal polygons. I was hoping to find an algorithm that could break up the outer polygon into a subset of polygons that would render together and appear as the outer polygon with holes, but I have not had very much luck with finding something like that. I have heard of a concept of breaking polygon objects into smaller triangles using Delaunay triangulation, but I don’t know if that is what’s needed here. Do you guys have any plans for this or any suggestions?
Hi Jonah,
We handle holes on the server-side when converting Esri Shapefiles to CZML. We are also adding support for this when converting KML to CZML. We use David Eberly’s paper, Triangulation by Ear Clipping:
http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
Here is the current C# code:
It is still being reviewed, and we expect some changes to make the interface more general; however the algorithm is unlikely to change.
It would be a great contribution if you want to port this to JavaScript, and add support to the Polygon primitive. It should be a pretty straightforward port, and modification.
Regards,
Patrick
Hey Patrick, thanks for the help. I’ve converted the algorithms to javascript and also the unit tests. I just put these in the Polygon class, but you guys might want to refactor to a PolygonAlgorithms class like in the czml writer.
The original algorithm is called “eliminateHole” and only works for one hole. I tried to add a while loop to iterate through the rest of the inner rings and keep adding to the outtering the edges needed to remove the holes, but the resulting polygon is not right. I’m not sure how to make it work for multiple inner rings.
Cesium.Polygon.prototype.eliminateHoles = function(outerRing, innerRings){
var /List/ newPolygonVertices;
while (innerRings.length!=0){
newPolygonVertices = new Array();
var innerRingIndex = this.getRightmostRingIndex(innerRings);
var innerRingVertexIndex = this.getRightmostVertexIndex(innerRings[innerRingIndex]);
var /Cartesian/ innerRingVertex = innerRings[innerRingIndex][innerRingVertexIndex];
var /Cartesian/ visibleVertex = this.findMutuallyVisibleVertex(outerRing, innerRings);
var /List/ innerRing = innerRings[innerRingIndex];
for (i = 0; i < outerRing.length; i++) {
if (outerRing[i].equals(visibleVertex)) {
newPolygonVertices.push(visibleVertex);
var innerVertexIndex = 0;
for (j = 0; j < innerRing.length; j++){
if (innerRing[j].equals(innerRingVertex)){
innerVertexIndex = j;
break;
}
}
// If the rightmost inner vertex is not the starting and ending point of the ring,
// then some other point is duplicated in the inner ring and should be skipped once.
if (innerVertexIndex != 0){
for (j = 0; j <= innerRing.length; j++){
var index = (j + innerVertexIndex) % innerRing.length;
if (index != 0){
newPolygonVertices.push(innerRing[index]);
}
}
} else {
for (j = 0; j < innerRing.length; j++) {
newPolygonVertices.push(innerRing[(j + innerVertexIndex) % innerRing.length]);
}
}
}
newPolygonVertices.push(outerRing[i]);
}
innerRings.remove(innerRingIndex);
outerRing = newPolygonVertices;
}
return newPolygonVertices;
}
Cesium.Polygon.prototype.isPointInTriangle = function (/Cartesian/ a, /Cartesian/ b, /Cartesian/ c, /Cartesian/ point){
var /Cartesian/ v0 = c.subtract(a);
var /Cartesian/ v1 = b.subtract(a);
var /Cartesian/ v2 = point.subtract(a);
var dot00 = v0.dot(v0);
var dot01 = v0.dot(v1);
var dot02 = v0.dot(v2);
var dot11 = v1.dot(v1);
var dot12 = v1.dot(v2);
var inverseDenominator = 1 / (dot00 * dot11 - dot01 * dot01);
var u = (dot11 * dot02 - dot01 * dot12) * inverseDenominator;
var v = (dot00 * dot12 - dot01 * dot02) * inverseDenominator;
return (u >= 0) && (v >= 0) && (u + v < 1);
}
Cesium.Polygon.prototype.getRightmostVertexIndex = function(/List/ vertices) {
var maximumX = vertices[0].x;
var rightmostVertexIndex = 0;
for (i = 0; i < vertices.length; i++) {
if (vertices[i].x > maximumX) {
maximumX = vertices[i].x;
rightmostVertexIndex = i;
}
}
return rightmostVertexIndex;
}
Cesium.Polygon.prototype.getRightmostRingIndex = function(/List<List>/ rings) {
var rightmostX = rings[0][0].x;
var rightmostRingIndex = 0;
var maxX = function(positions){
var max;
for (i = 0; i<positions.length;i++){
var vertex = positions[i];
if (!max){
max = vertex.x;
} else {
if (vertex.x>max){
max = vertex.x
}
}
}
return max;
}
for (ring = 0; ring < rings.length; ring++){
//var maximumX = rings[ring].max(vertex => vertex.X);
var maximumX = maxX(rings[ring]);
if (maximumX > rightmostX)
{
rightmostX = maximumX;
rightmostRingIndex = ring;
}
}
return rightmostRingIndex;
}
Cesium.Polygon.prototype.getReflexVertices = function (/List/ polygon) {
var /List/ reflexVertices = new Array();
for (i = 0; i < polygon.length; i++) {
var /Cartesian/ p0 = polygon[(i - 1 + polygon.length) % polygon.length];
var /Cartesian/ p1 = polygon[i];
var /Cartesian/ p2 = polygon[(i + 1) % polygon.length];
var /Cartesian/ v0 = p0.subtract(p1);
var /Cartesian/ v1 = p2.subtract(p1);
var /Cartesian/ v0_perp = new Cesium.Cartesian3(-v0.y, v0.x, 0.0);
var angle = Math.atan2(v0_perp.dot(v1), v0.dot(v1)); // Signed angle from v0 to v1
var perpDotProduct = v0.magnitude() * v1.magnitude() * Math.sin(angle);
if (perpDotProduct < 0) {
reflexVertices.push(p1);
}
}
return reflexVertices;
}
Cesium.Polygon.prototype.isVertex = function(/List/ positions, /Cartesian/ point){
for (i =0; i<positions.length; i++){
var vertex = positions[i];
if (vertex.equals(point)){
return true;
}
}
return false;
}
Cesium.Polygon.prototype.intersectPointWithRing = function(/Cartesian/ point, /List/ ring){
// Intersect point + t(1,0) with all edges of the ring.
var /List/ intersections = new Array();
var /List<Cartesian[]>/ edges = new Array();
for (i = 0; i < ring.length; i++)
{
var /Cartesian/ v1 = ring[i];
var /Cartesian/ v2 = ring[(i + 1) % ring.length];
var m = (v2.y - v1.y) / (v2.x - v1.x);
if (m != 0.0)
{
var x = v1.x + (point.y - v1.y) / m;
// We only care about intersections on edges to the right of the point
if ((x >= point.x))
{
intersections.push(x);
edges.push([ v1, v2 ]);
}
}
}
// Find the closest intersection
var minDistanceIndex = 0;
var minDistance = intersections[0] - point.x;
for (i = 0; i < intersections.length; i++)
{
var distance = intersections[i] - point.x;
if (distance < minDistance)
{
minDistance = distance;
minDistanceIndex = i;
}
}
var edge = edges[minDistanceIndex];
return [new Cesium.Cartesian3(intersections[minDistanceIndex], point.y, 0.0), edge];
}
Cesium.Polygon.prototype.findMutuallyVisibleVertex = function(/List/ outerRing, /List<List>/ innerRings) {
var innerRingIndex = this.getRightmostRingIndex(innerRings);
var /List/ innerRing = innerRings[innerRingIndex];
var innerRingVertexIndex = this.getRightmostVertexIndex(innerRings[innerRingIndex]);
var /Cartesian/ innerRingVertex = innerRings[innerRingIndex][innerRingVertexIndex];
var result = this.intersectPointWithRing(innerRingVertex, outerRing);
var /Cartesian/ intersection = result[0];
var /Cartesian[]/ edge = result[1];
var /Cartesian/ visibleVertex;
if (this.isVertex(outerRing, intersection)){
visibleVertex = intersection;
} else {
// Set P to be the endpoint of maximum x value for this edge
var /Cartesian/ p = (edge[0].x > edge[1].x) ? edge[0] : edge[1];
var /List/ reflexVertices = this.getReflexVertices(outerRing);
var getIndex = function(point, vertices){
for (i =0; i<vertices.length; i++){
var vertex = vertices[i];
if (vertex.equals(point)){
return i;
}
}
}
var index = getIndex(p, reflexVertices);
if (index){
reflexVertices.remove(index); // Do not include p if it happens to be reflex.
}
var /List/ pointsInside = new Array();
for (i = 0; i<reflexVertices.length; i++){
var vertex = reflexVertices[i];
if (this.isPointInTriangle(innerRingVertex, intersection, p, vertex))
{
pointsInside.push(vertex);
}
}
// If all reflexive vertices are outside the triangle formed by points
// innerRingVertex, intersection and P, then P is the visible vertex.
// Otherwise, return the reflex vertex that minimizes the angle between <1,0> and <k, reflex>.
var minAngle = Math.PI;
if (pointsInside.length > 0) {
var /Cartesian/ v1 = new Cesium.Cartesian3(1.0, 0.0, 0.0);
for (i = 0; i < pointsInside.length; i++) {
var /Cartesian/ v2 = pointsInside[i] - innerRingVertex;
var angle = Math.abs(Math.acos(v1.dot(v2) / (v1.magnitude * v2.magnitude)));
if (angle < minAngle){
minAngle = angle;
p = pointsInside[i];
}
}
}
visibleVertex = p;
}
return visibleVertex;
}
// Here are the unit tests
runTests: function(){
this.testisPointInTriangle();
this.testgetRightmostVertexIndex();
this.testgetRightmostRingIndex();
this.testgetReflexVertices();
this.testisVertex();
this.testintersectPointWithRing();
this.testfindMutuallyVisibleVertex();
this.testEliminateHole();
},
testisPointInTriangle: function(){
var polygon = new Cesium.Polygon();
var a = new Cesium.Cartesian3(0, 0, 0);
var b = new Cesium.Cartesian3(0, 1, 0);
var c = new Cesium.Cartesian3(1, 0, 0);
// p is on the boundary of the triangle
var p = new Cesium.Cartesian3(0, 0, 0);
console.log("isPointInTriangle true? "+polygon.isPointInTriangle(a, b, c, p));
// p is inside the triangle
p = new Cesium.Cartesian3(0.5, 0.25, 0);
console.log("isPointInTriangle true? "+polygon.isPointInTriangle(a, b, c, p));
// p is outside the triangle
p = new Cesium.Cartesian3(1, 1, 0);
console.log("isPointInTriangle false? "+polygon.isPointInTriangle(a, b, c, p));
},
testgetRightmostVertexIndex: function(){
var polygon = new Cesium.Polygon();
var ring = [
new Cesium.Cartesian3(0.0, 1.0, 0.0),
new Cesium.Cartesian3(1.0, 2.0, 0.0),
new Cesium.Cartesian3(2.0, 2.0, 0.0),
new Cesium.Cartesian3(3.0, 1.0, 0.0),
new Cesium.Cartesian3(2.0, 0.0, 0.0),
new Cesium.Cartesian3(1.0, 1.0, 0.0)];
var expectedResult = 3;
var result = polygon.getRightmostVertexIndex(ring);
console.log("getRightmostVertexIndex 3? "+result);
},
testgetRightmostRingIndex: function(){
var polygon = new Cesium.Polygon();
var ring0 = [
new Cesium.Cartesian3(0.0, 1.0, 0.0),
new Cesium.Cartesian3(1.0, 2.0, 0.0),
new Cesium.Cartesian3(2.0, 2.0, 0.0),
new Cesium.Cartesian3(3.0, 1.0, 0.0),
new Cesium.Cartesian3(2.0, 0.0, 0.0),
new Cesium.Cartesian3(1.0, 1.0, 0.0)];
var ring1 = [
new Cesium.Cartesian3(4.0, 1.0, 0.0),
new Cesium.Cartesian3(5.0, 2.0, 0.0),
new Cesium.Cartesian3(6.0, 2.0, 0.0),
new Cesium.Cartesian3(7.0, 1.0, 0.0),
new Cesium.Cartesian3(6.0, 0.0, 0.0),
new Cesium.Cartesian3(5.0, 1.0, 0.0)];
var rings = new Array();
rings.push(ring0);
rings.push(ring1);
var result = polygon.getRightmostRingIndex(rings);
console.log("testgetRightmostRingIndex 1? "+result);
},
testgetReflexVertices: function(){
var polygon = new Cesium.Polygon();
var positions = [
new Cesium.Cartesian3(0.0, 2.0, 0.0),
new Cesium.Cartesian3(1.6, 2.0, 0.0), // reflex
new Cesium.Cartesian3(2.0, 3.0, 0.0),
new Cesium.Cartesian3(2.3, 2.0, 0.0), // reflex
new Cesium.Cartesian3(4.0, 2.0, 0.0),
new Cesium.Cartesian3(2.6, 1.0, 0.0), // reflex
new Cesium.Cartesian3(3.0, 0.0, 0.0),
new Cesium.Cartesian3(2.0, 1.0, 0.0), // reflex
new Cesium.Cartesian3(1.0, 0.0, 0.0),
new Cesium.Cartesian3(1.3, 1.0, 0.0)]; // reflex
var contains = function(point, positions){
for (var i = 0; i<positions.length; i++){
if (point.equals(positions[i])){
return true;
}
}
return false;
}
var reflexVertices = polygon.getReflexVertices(positions);
console.log("getReflexVertices true? "+reflexVertices.length == 5);
console.log("getReflexVertices true? "+contains(positions[1], reflexVertices));
console.log("getReflexVertices true? "+contains(positions[3], reflexVertices));
console.log("getReflexVertices true? "+contains(positions[5], reflexVertices));
console.log("getReflexVertices true? "+contains(positions[7], reflexVertices));
console.log("getReflexVertices true? "+contains(positions[9], reflexVertices));
},
testisVertex: function () {
var polygon = new Cesium.Polygon();
var ring = [
new Cesium.Cartesian3(0.0, 0.0, 0.0),
new Cesium.Cartesian3(0.0, 1.0, 0.0),
new Cesium.Cartesian3(1.0, 1.0, 0.0),
new Cesium.Cartesian3(1.0, 0.0, 0.0)]
console.log("isVertex true? "+polygon.isVertex(ring, ring[0]));
console.log("isVertex false? "+polygon.isVertex(ring, new Cesium.Cartesian3(1.0, 1.0, 1.0)));
},
testintersectPointWithRing: function() {
var polygon = new Cesium.Polygon();
var ring = [
new Cesium.Cartesian3(0.0, 0.0, 0.0),
new Cesium.Cartesian3(0.0, 1.0, 0.0),
new Cesium.Cartesian3(1.0, 1.0, 0.0),
new Cesium.Cartesian3(1.0, 0.0, 0.0)];
var point = new Cesium.Cartesian3(0.5, 0.5, 0.0);
var expectedResult = new Cesium.Cartesian3(1.0, 0.5, 0.0);
var result = polygon.intersectPointWithRing(point, ring)[0];
console.log("intersectPointWithRing true? "+result.equals(expectedResult));
},
testfindMutuallyVisibleVertex: function (){
var polygon = new Cesium.Polygon();
var outerRing = [
new Cesium.Cartesian3(0.0, 5.0, 0.0),
new Cesium.Cartesian3(5.0, 10.0, 0.0),
new Cesium.Cartesian3(10.0, 5.0, 0.0),
new Cesium.Cartesian3(5.0, 0.0, 0.0),
new Cesium.Cartesian3(0.0, 5.0, 0.0)];
var innerRing = [
new Cesium.Cartesian3(3.0, 7.0, 0.0),
new Cesium.Cartesian3(3.0, 3.0, 0.0),
new Cesium.Cartesian3(7.0, 3.0, 0.0),
new Cesium.Cartesian3(7.0, 7.0, 0.0),
new Cesium.Cartesian3(3.0, 7.0, 0.0)];
var innerRings = [innerRing];
var expectedResult = outerRing[2];
var result = polygon.findMutuallyVisibleVertex(outerRing, innerRings);
console.log("findMutuallyVisibleVertex true? "+result.equals(expectedResult));
},
testEliminateHole : function() {
var polygon = new Cesium.Polygon();
var outerRing = [
new Cesium.Cartesian3(0.0, 5.0, 0.0),
new Cesium.Cartesian3(5.0, 10.0, 0.0),
new Cesium.Cartesian3(10.0, 5.0, 0.0),
new Cesium.Cartesian3(5.0, 0.0, 0.0),
new Cesium.Cartesian3(0.0, 5.0, 0.0)];
var innerRing = [
new Cesium.Cartesian3(3.0, 7.0, 0.0),
new Cesium.Cartesian3(3.0, 3.0, 0.0),
new Cesium.Cartesian3(7.0, 3.0, 0.0),
new Cesium.Cartesian3(7.0, 7.0, 0.0),
new Cesium.Cartesian3(3.0, 7.0, 0.0)];
var innerRings = [
innerRing
];
var expectedResult = [
outerRing[0], outerRing[1], outerRing[2],
innerRing[2], innerRing[3], innerRing [0], innerRing[1], innerRing[2],
outerRing[2], outerRing[3], outerRing[0]
];
var result = polygon.eliminateHoles(outerRing, innerRings);
for (i = 0; i < result.length; i++) {
console.log("eliminateHoles true? "+result[i].equals(expectedResult[i]));
}
},
Thanks for the contribution Jonah. We’ll organize this in the PolygonPipeline class that does all the polygonal algorithms in Cesium. We should be able to get multiple and nested rings working, and will change the algorithm to work on a tangent plane for better robustness (we are making the same change in czml-writer).
This will fit into some other polygon changes that we are doing for the crossing the International Date Line in 2D and Columbus view.
Patrick
Sounds good, Patrick. I just noticed in the findMutuallyVisibleVertex function, there is a “magnitude” variable that should be “magnitude()”, and a subtraction sign that should be “subtract()”. These changes do not make any difference in the unit tests or the multiple holes problem though. Hopefully these conversions will save you guys some time.
Instead of:
for (i = 0; i < pointsInside.length; i++) {
var /Cartesian/ v2 = pointsInside[i] - innerRingVertex;
var angle = Math.abs(Math.acos(v1.dot(v2) / (v1.magnitude * v2.magnitude)));
if (angle < minAngle){
minAngle = angle;
p = pointsInside[i];
}
}
Should be
for (i = 0; i < pointsInside.length; i++) {
var /Cartesian/ v2 = pointsInside[i].subtract(innerRingVertex);
var angle = Math.abs(Math.acos(v1.dot(v2) / (v1.magnitude() * v2.magnitude())));
if (angle < minAngle){
minAngle = angle;
p = pointsInside[i];
}
}
Hi Jonah,
In addition to not projecting the points onto a tangent plane before calculating mutually visible vertices, there were a number of other small bugs in the previous code. I have since fixed these issues and the shapefiles branch in the czml-writer repository is just about ready to be merged into master. In the meantime, I’ve ported the updated code for eliminating holes in polygons (and the related tests) to JavaScript: https://github.com/AnalyticalGraphicsInc/cesium/tree/eliminatePolygonHoles. Please let us know if the resulting polygon in your example with multiple holes is still not right.
Patrick and I will be discussing how to further integrate all of this into Cesium’s polygon architecture so that it is easier to define polygons with holes. As usual, we would love to hear any of your suggestions or feedback.
Thanks,
Kristian
I am not having much luck getting it to work, Kristian. At first, I had some problems with the “for (var x in array)” loops because sometimes the loop traverses elements that are part of the array object such as prototype member functions and cause the algorithm to crash. After changing those to the standard “for (var i = 0; i<array.length;i++)” loops, there are no more runtime errors, but the output is not correct. I have come across this loop problem many times and since only use the first variation when looping through a javascript object hash “{}” and always use the conventional loop for arrays “”.
At first I tried passing in cartesian points as parameters to the eliminateHole function because that is what your documentation says, but I notice that the first thing you do is loop through the array positions and convert from cartographictocartesian. This makes me think you are expecting cartographic positions as input, so I am currently trying that. I am not sure if it should be in radians or degrees though, but I will try both. Here are my inner and outer rings. I will try to provide a simpler example shortly if passing in cartographic arguments fails to be the solution.
var polygon = new Cesium.Polygon();
var outerRing = [{“x”:-1006769.7041651113,“y”:-5017135.398889454,“z”:3794517.233517488},{“x”:-1006942.2789012031,“y”:-5020967.9728503395,“z”:3789432.8885893007},{“x”:-1006014.8428461703,“y”:-5024895.620927537,“z”:3784503.075600287},{“x”:-1004015.5847215113,“y”:-5028799.002120366,“z”:3779877.578017214},{“x”:-1001005.2576965626,“y”:-5032559.513358359,“z”:3775696.929481954},{“x”:-997075.3326342707,“y”:-5036062.893289052,“z”:3772088.144947742},{“x”:-753760.1487621723,“y”:-5225832.060679198,“z”:3566153.0123906406},{“x”:-748857.2202117816,“y”:-5228603.659720984,“z”:3563142.3888729364},{“x”:-743326.9974695634,“y”:-5230913.671528996,“z”:3560924.134288653},{“x”:-737337.5069450183,“y”:-5232691.908132409,“z”:3559565.639496549},{“x”:-731070.7274346892,“y”:-5233884.339712025,“z”:3559108.175357872},{“x”:-724717.0618468899,“y”:-5234454.736154501,“z”:3559565.639496549},{“x”:-718469.5531019691,“y”:-5234385.767730683,“z”:3560924.134288653},{“x”:-712518.0198139043,“y”:-5233679.531472237,“z”:3563142.3888729364},{“x”:-707043.2897970075,“y”:-5232357.487274507,“z”:3566153.0123906406},{“x”:-702211.7064856841,“y”:-5230459.805689712,“z”:3569864.540464598},{“x”:-698170.075093795,“y”:-5228044.14724833,“z”:3574164.212873372},{“x”:-695041.2020206583,“y”:-5225183.910414326,“z”:3578921.3981913403},{“x”:-692920.163033469,“y”:-5221966.001417991,“z”:3583991.561520447},{“x”:-691871.4136614278,“y”:-5218488.1937288465,“z”:3589220.6549287695},{“x”:-687528.764661453,“y”:-5093382.954304453,“z”:3764291.1624390627},{“x”:-508263.72193033464,“y”:-5114817.901690045,“z”:3763704.196431393},{“x”:-501889.85073337314,“y”:-5115117.696959787,“z”:3764149.0949797505},{“x”:-495643.98772062175,“y”:-5114747.7443082025,“z”:3765470.2747998335},{“x”:-489715.90115123347,“y”:-5113719.28519615,“z”:3767627.5988262356},{“x”:-484285.7061178916,“y”:-5112063.569091064,“z”:3770555.527542634},{“x”:-479518.39265947253,“y”:-5109830.90393016,“z”:3774165.109208207},{“x”:-475558.8130695876,“y”:-5107089.127551307,“z”:3778346.6811861843},{“x”:-472527.2806545287,“y”:-5103921.546536805,“z”:3782973.2004654664},{“x”:-470515.9136653591,“y”:-5100424.405091313,“z”:3787904.1023608716},{“x”:-469585.8355383025,“y”:-5096703.960848754,“z”:3792989.570320052},{“x”:-469765.31660518184,“y”:-5092873.256441477,“z”:3798075.087244146},{“x”:-471048.91386563866,“y”:-5089048.6849062415,“z”:3803006.130128398},{“x”:-473397.63510819414,“y”:-5085346.453265763,“z”:3807632.8654151363},{“x”:-476740.1225462983,“y”:-5081879.051721072,“z”:3811814.7023654967},{“x”:-480974.8201426263,“y”:-5078751.835724849,“z”:3815424.5660088095},{“x”:-485973.058873704,“y”:-5076059.824783143,“z”:3818352.759697625},{“x”:-491582.96624970494,“y”:-5073884.815255604,“z”:3820510.2997315307},{“x”:-497634.08130585507,“y”:-5072292.894891107,“z”:3821831.6205405053},{“x”:-503942.534791297,“y”:-5071332.434634949,“z”:3822276.5680537913},{“x”:-685736.5854164823,“y”:-5049510.278790334,“z”:3822871.892918904},{“x”:-680377.5746191392,“y”:-4933521.105863153,“z”:3971371.7395699183},{“x”:-680357.3871922627,“y”:-4929508.705878025,“z”:3976321.198565247},{“x”:-681441.3672743607,“y”:-4925457.729014859,“z”:3981120.3171709757},{“x”:-683596.5881140276,“y”:-4921491.261496855,“z”:3985623.2703322233},{“x”:-686757.5715387716,“y”:-4917729.822528834,“z”:3989693.2284486564},{“x”:-690828.276606577,“y”:-4914287.702373911,“z”:3993206.516033962},{“x”:-695685.017275073,“y”:-4911269.489599727,“z”:3996056.3709667064},{“x”:-701180.2204980209,“y”:-4908766.89302448,“z”:3998156.1899360963},{“x”:-707146.9105685327,“y”:-4906855.954949393,“z”:3999442.1612848877},{“x”:-713403.7834060097,“y”:-4905594.740382955,“z”:3999875.2050752393},{“x”:-719760.7165084094,“y”:-4905021.572503043,“z”:3999442.161284887},{“x”:-726024.5470157443,“y”:-4905153.868004697,“z”:3998156.1899360963},{“x”:-732004.9421631687,“y”:-4905987.607748605,“z”:3996056.3709667064},{“x”:-737520.1835935134,“y”:-4907497.458812878,“z”:3993206.516033962},{“x”:-742402.6896350252,“y”:-4909637.544246824,“z”:3989693.2284486564},{“x”:-746504.1076483259,“y”:-4912342.83713334,“z”:3985623.2703322233},{“x”:-749699.8216588771,“y”:-4915531.136586321,“z”:3981120.3171709757},{“x”:-751892.738313229,“y”:-4919105.565619238,“z”:3976321.198565247},{“x”:-753016.2361802434,“y”:-4922957.514958946,“z”:3971371.7395699183},{“x”:-758486.6517496574,“y”:-5038913.258937163,“z”:3823110.9166451446},{“x”:-966592.1505423211,“y”:-5002635.384516599,“z”:3823797.7639331156},{“x”:-972911.9439763508,“y”:-5001752.520978138,“z”:3823352.914673462},{“x”:-979165.7009970385,“y”:-5001548.590639769,“z”:3822031.8856398975},{“x”:-985163.3952033273,“y”:-5002029.79124466,“z”:3819874.8220374403},{“x”:-990722.7828652165,“y”:-5003181.502549693,“z”:3816947.274959542},{“x”:-995674.9411349823,“y”:-5004968.7304644985,“z”:3813338.208459141},{“x”:-999869.401122952,“y”:-5007337.170327415,“z”:3809157.2949623493},{“x”:-1003178.7198192807,“y”:-5010214.857009528,“z”:3804531.5813806704},{“x”:-1005502.3519480574,“y”:-5013514.351697327,“z”:3799601.6274085823},{“x”:-1006769.7041651113,“y”:-5017135.398889454,“z”:3794517.233517488}];
var innerRings = [[{“x”:-884111.0956755395,“y”:-5062478.568726861,“z”:3764938.1348537896},{“x”:-760289.3406203464,“y”:-5082852.96461553,“z”:3764530.1709888955},{“x”:-762971.9603048221,“y”:-5157002.1128044715,“z”:3662435.6358900145},{“x”:-884111.0956755395,“y”:-5062478.568726861,“z”:3764938.1348537896}]];
var positions = Cesium.PolygonPipeline.eliminateHole(outerRing, innerRings);
polygon.setPositions(positions);
primitives.add(polygon);
Thanks for catching the ‘for in’ loop error, Jonah. You are also correct that, at least for now, the eliminateHole function expects an array of Cartographic points (the Cartesian documentation was copied/pasted and never updated). I’ve pushed both fixes to the branch on GitHub.
I cannot get either way to work. Here is a much simpler example. It is a triangle with a smaller triangle hole over the united states.
var outerRing = [new Cesium.Cartesian3(-634066.5629045101,-4608738.034138676,4348640.761750969),new Cesium.Cartesian3(-1321523.0597310204,-5108871.981065817,3570395.2500986718),new Cesium.Cartesian3(46839.74837473363,-5303481.972379478,3530933.5841716)];
var innerRings = [[new Cesium.Cartesian3(-646079.44483647,-4811233.11175887,4123187.2266941597),new Cesium.Cartesian3(-1024015.4454943262,-5072141.413164587,3716492.6173834214),new Cesium.Cartesian3(-234678.22583880965,-5189078.820849883,3688809.059214336)]];
var positions = Cesium.PolygonPipeline.eliminateHole(outerRing, innerRings);
Cartesian coordinates do not work as input to the algorithm because they get reconverted to cartesian and come back as "NaN"s.
Here is a similar example in cartographic coordinates.
var outerRing = [new Cesium.Cartographic(-1.7044764400108126,0.7260906671849546,0),new Cesium.Cartographic(-1.8231657047227843,0.579377139769438,0),new Cesium.Cartographic(-1.5809915160268297,0.5791662402064216,0)];
var innerRings = [[new Cesium.Cartographic(-1.7034296185862727,0.6641863517938158,0),new Cesium.Cartographic(-1.7408063702627032,0.6089345145537416,0),new Cesium.Cartographic(-1.665600799706566,0.6058218370427867,0)]];
When I pass in the cartographic coordinates, I get DeveloperError: outerRing must not be empty.
The outer ring is becoming empty on this line.
cartesianOuterRing = (tangentPlane.projectPointsOntoPlane(cartesianOuterRing));
Sorry, I don’t have any time to investigate further for now.
Hi Jonah,
After catching some other errors that were introduced during the port from C# to JavaScript, I was able to get your example (as well as some of my own) to work:
Additionally, to eliminate unnecessary coordinate transformations and remain consistent with the rest of the API, PolygonPipeline.eliminateHole now expects Cartesian coordinates. I’ll open a pull request for this branch after I do some more testing.
Regards,
Kristian
Great work Kristian! When I tried passing multiple holes in the inner rings array though, the algorithm only removed one of them. I was able to loop through the inner rings and continue calling eliminateHole with only one inner ring, and the result of the last call as the outer ring, and it works! Here is my example:
var outerRing = [{“x”:-233232.54623103954,“y”:-5169921.58283831,“z”:3715522.2423877926},{“x”:-165363.78482092632,“y”:-5078114.146059241,“z”:3842723.5377236446},{“x”:-89635.7941046134,“y”:-5080879.682013635,“z”:3841588.0228001624},{“x”:11828.898879860402,“y”:-5082813.513190284,“z”:3840067.32365833},{“x”:17757.797261130596,“y”:-5391366.4104229165,“z”:3396430.39113858},{“x”:18142.512082407342,“y”:-5393601.119652234,“z”:3392902.2620001906},{“x”:19250.06066907997,“y”:-5395762.217458314,“z”:3389481.3534203023},{“x”:21046.786965564366,“y”:-5397784.039725078,“z”:3386271.6052170536},{“x”:23478.095577010125,“y”:-5399605.153984429,“z”:3383370.539757718},{“x”:26470.110953867257,“y”:-5401170.226061077,“z”:3380866.2992992583},{“x”:29931.922236459148,“y”:-5402431.701439133,“z”:3378834.9684506766},{“x”:33758.345531155035,“y”:-5403351.250254946,“z”:3377338.263038184},{“x”:37833.119689032785,“y”:-5403900.932001613,“z”:3376421.6555171856},{“x”:42032.438506934115,“y”:-5404064.044547131,“z”:3376112.9938159646},{“x”:46228.712066958775,“y”:-5403835.631661453,“z”:3376421.6555171856},{“x”:50294.442981448534,“y”:-5403222.633626146,“z”:3377338.263038184},{“x”:54106.0998263059,“y”:-5402243.67634827,“z”:3378834.9684506766},{“x”:57547.870130866606,“y”:-5400928.505387382,“z”:3380866.2992992583},{“x”:60515.17894520063,“y”:-5399317.082096991,“z”:3383370.539757718},{“x”:62917.86611525797,“y”:-5397458.369350881,“z”:3386271.6052170536},{“x”:198327.9134018256,“y”:-5239684.277292231,“z”:3619216.4169472232},{“x”:324953.2182382361,“y”:-5068481.32243273,“z”:3845241.820663788},{“x”:326593.0704948587,“y”:-5066067.079211892,“z”:3848262.8345629047},{“x”:327534.6269544296,“y”:-5063542.371271592,“z”:3851482.593764233},{“x”:327749.274886999,“y”:-5060983.910618402,“z”:3854803.2702825135},{“x”:327230.48775674554,“y”:-5058469.434976678,“z”:3858123.9680166864},{“x”:325994.0240775501,“y”:-5056075.345745973,“z”:3861343.7883067396},{“x”:324077.44915079605,“y”:-5053874.386545305,“z”:3864364.895799214},{“x”:321538.9941502229,“y”:-5051933.432884613,“z”:3867095.491453904},{“x”:318455.78716055205,“y”:-5050311.460128852,“z”:3869452.60231928},{“x”:314921.5098741507,“y”:-5049057.7515039565,“z”:3871364.603249632},{“x”:311043.5511214946,“y”:-5048210.4006006075,“z”:3872773.393867127},{“x”:306939.7437232459,“y”:-5047795.153882969,“z”:3873636.1645418126},{“x”:302734.78383603157,“y”:-5047824.628377138,“z”:3873926.697654523},{“x”:59698.958250299314,“y”:-5053729.918597435,“z”:3877570.0507101},{“x”:54235.45760207743,“y”:-4721529.677678693,“z”:4273379.511903018},{“x”:53850.10113848365,“y”:-4718713.534809574,“z”:4276472.954247601},{“x”:52741.50293350285,“y”:-4715987.631334194,“z”:4279472.423404778},{“x”:50943.343017983425,“y”:-4713434.79310113,“z”:4282286.779382438},{“x”:48510.25447444123,“y”:-4711132.587795397,“z”:4284830.505342213},{“x”:45516.16381480056,“y”:-4709150.967965017,“z”:4287026.306474005},{“x”:42052.04496283897,“y”:-4707550.145402416,“z”:4288807.45916138},{“x”:38223.15506029109,“y”:-4706378.761484208,“z”:4290119.838986899},{“x”:34145.83608439816,“y”:-4705672.409081804,“z”:4290923.565879623},{“x”:29943.979481715633,“y”:-4705452.550971909,“z”:4291194.216344369},{“x”:25745.261283856096,“y”:-4705725.867625214,“z”:4290923.5658796225},{“x”:21677.26216075183,“y”:-4706484.054199865,“z”:4290119.838986899},{“x”:17863.590371761613,“y”:-4707704.072911007,“z”:4288807.45916138},{“x”:14420.125486933224,“y”:-4709348.853104346,“z”:4287026.306474005},{“x”:11451.497072340682,“y”:-4711368.41775208,“z”:4284830.505342213},{“x”:9047.90537808331,“y”:-4713701.402127887,“z”:4282286.779382438},{“x”:7282.380654049953,“y”:-4716276.918498403,“z”:4279472.423404778},{“x”:-129378.66977443818,“y”:-4946964.798329529,“z”:4010366.6211506617},{“x”:-196910.80945475557,“y”:-5047269.194231471,“z”:3881417.035406211},{“x”:-432067.7302632372,“y”:-5029849.636636717,“z”:3884950.9044845034},{“x”:-442851.1035230817,“y”:-4914805.799766857,“z”:4027391.7840400133},{“x”:-460357.6564462329,“y”:-4669933.014146976,“z”:4305288.383612842},{“x”:-461159.26236679504,“y”:-4667083.669596392,“z”:4308271.184076223},{“x”:-462665.3646324092,“y”:-4664331.992818778,“z”:4311069.90009275},{“x”:-464830.2042817644,“y”:-4661761.592806602,“z”:4313599.490054372},{“x”:-467588.0055390721,“y”:-4659450.570934202,“z”:4315783.088688377},{“x”:-470854.9741600315,“y”:-4657469.147757691,“z”:4317554.343168817},{“x”:-474531.8434571281,“y”:-4655877.529237821,“z”:4318859.429852671},{“x”:-478506.8906475735,“y”:-4654724.07723926,“z”:4319658.6902857255},{“x”:-482659.33185229154,“y”:-4654043.839916092,“z”:4319927.836695882},{“x”:-486862.9925471389,“y”:-4653857.4866572935,“z”:4319658.6902857255},{“x”:-490990.1418815082,“y”:-4654170.67996992,“z”:4318859.429852671},{“x”:-494915.3742910302,“y”:-4654973.903395847,“z”:4317554.343168817},{“x”:-498519.42039337516,“y”:-4656242.750694354,“z”:4315783.088688377},{“x”:-501692.77131279284,“y”:-4657938.66750002,“z”:4313599.490054372},{“x”:-504339.00626346446,“y”:-4660010.122910079,“z”:4311069.90009275},{“x”:-506377.72225934546,“y”:-4662394.175386659,“z”:4308271.184076223},{“x”:-507746.97693170235,“y”:-4665018.385374837,“z”:4305288.383612842},{“x”:-587423.0430376469,“y”:-4902814.016252518,“z”:4023540.1833336395},{“x”:-625598.6229849765,“y”:-5007179.402850961,“z”:3887871.042152128},{“x”:-811307.1183209985,“y”:-4978246.964517698,“z”:3890687.6912760143},{“x”:-831141.9329948266,“y”:-4891107.180229724,“z”:3994915.1756475572},{“x”:-876354.5728618251,“y”:-4648112.487204088,“z”:4264402.181139504},{“x”:-876907.4876643645,“y”:-4645229.538897202,“z”:4267408.571352239},{“x”:-878170.4294488021,“y”:-4642380.338000826,“z”:4270229.421241574},{“x”:-880105.0275932486,“y”:-4639651.4563838495,“z”:4272779.016647644},{“x”:-882652.5021636975,“y”:-4637125.8105676565,“z”:4274979.884411219},{“x”:-885735.4496863668,“y”:-4634880.142248985,“z”:4276765.146959219},{“x”:-889260.1949804123,“y”:-4632982.686393398,“z”:4278080.554989119},{“x”:-893119.637596285,“y”:-4631491.097771382,“z”:4278886.136412127},{“x”:-897196.5063525267,“y”:-4630450.698960247,“z”:4279157.411379257},{“x”:-901366.9230419446,“y”:-4629893.103068534,“z”:4278886.136412127},{“x”:-905504.1669673291,“y”:-4629835.253051925,“z”:4278080.554989119},{“x”:-909482.5258550392,“y”:-4630278.906827257,“z”:4276765.146959219},{“x”:-913181.1160689673,“y”:-4631210.583839135,“z”:4274979.884411219},{“x”:-916487.5559874547,“y”:-4632601.974704911,“z”:4272779.016647644},{“x”:-919301.3808822915,“y”:-4634410.801485218,“z”:4270229.421241573},{“x”:-921537.095513947,“y”:-4636582.102428109,“z”:4267408.571352239},{“x”:-923126.7716888934,“y”:-4639049.902131863,“z”:4264402.181139504},{“x”:-924022.1118750608,“y”:-4641739.216357723,“z”:4261301.600892941},{“x”:-989138.3167315628,“y”:-4943834.082397538,“z”:3893402.155444518},{“x”:-1094639.6527969867,“y”:-4920259.313724052,“z”:3895022.1654995424},{“x”:-1104936.751934683,“y”:-4844950.839863676,“z”:3984868.8864418645},{“x”:-1105421.4441195908,“y”:-4842224.325144162,“z”:3988025.988251732},{“x”:-1106614.2815926962,“y”:-4839494.044580853,“z”:3990988.2481890614},{“x”:-1108479.0236719751,“y”:-4836842.956167184,“z”:3993665.655296609},{“x”:-1110959.01284331,“y”:-4834351.612123551,“z”:3995976.8527670563},{“x”:-1113978.8960585222,“y”:-4832095.711330055,“z”:3997851.6105499105},{“x”:-1117446.9142768313,“y”:-4830143.799174841,“z”:3999232.959919377},{“x”:-1121257.6906865973,“y”:-4828555.184716763,“z”:4000078.9250649745},{“x”:-1125295.432868477,“y”:-4827378.138463378,“z”:4000363.7990153674},{“x”:-1129437.451562576,“y”:-4826648.425541974,“z”:4000078.9250649745},{“x”:-1133557.8890660398,“y”:-4826388.218851661,“z”:3999232.959919377},{“x”:-1137531.5439089078,“y”:-4826605.425237317,“z”:3997851.6105499105},{“x”:-1141237.6755298364,“y”:-4827293.445173041,“z”:3995976.8527670563},{“x”:-1144563.67328846,“y”:-4828431.373265369,“z”:3993665.655296609},{“x”:-1147408.4782881632,“y”:-4829984.633486001,“z”:3990988.2481890614},{“x”:-1149685.6540142347,“y”:-4831906.029828305,“z”:3988025.988251732},{“x”:-1151326.0124863468,“y”:-4834137.180453611,“z”:3984868.8864418645},{“x”:-1152279.7161532133,“y”:-4836610.291736726,“z”:3981612.8724247506},{“x”:-1152517.791707118,“y”:-4839250.218289945,“z”:3978356.8794725705},{“x”:-1143134.3000129438,“y”:-4908622.001687264,“z”:3895769.517018683},{“x”:-1247888.4996263105,“y”:-4881739.9392348705,“z”:3897390.2100288547},{“x”:-1252012.322002755,“y”:-4880916.660055767,“z”:3897100.704650063},{“x”:-1256121.630642888,“y”:-4880551.811287492,“z”:3896240.985948921},{“x”:-1260091.5623014425,“y”:-4880656.479453603,“z”:3894837.178808948},{“x”:-1263801.4896193878,“y”:-4881227.484665095,“z”:3892931.941435114},{“x”:-1267138.6866877119,“y”:-4882247.477193098,“z”:3890583.168692483},{“x”:-1270001.7543651348,“y”:-4883685.464636658,“z”:3887862.2323713065},{“x”:-1272303.701249499,“y”:-4885497.753666676,“z”:3884851.8119237623},{“x”:-1273974.5866883644,“y”:-4887629.277724395,“z”:3881643.3816652973},{“x”:-1274963.6455446924,“y”:-4890015.27032072,“z”:3878334.430866315},{“x”:-1275240.830200273,“y”:-4892583.233078259,“z”:3875025.501261341},{“x”:-1274797.723001188,“y”:-4895255.138700876,“z”:3871817.132028589},{“x”:-1273647.7914861934,“y”:-4897949.801917823,“z”:3868806.805077865},{“x”:-1271825.9787077715,“y”:-4900585.346348073,“z”:3866085.9834475187},{“x”:-1269387.6411504939,“y”:-4903081.692320009,“z”:3863737.3327563237},{“x”:-1266406.866559475,“y”:-4905362.990049948,“z”:3861832.2100733267},{“x”:-1262974.2228132046,“y”:-4907359.924248925,“z”:3860428.49643018},{“x”:-1259194.0062405155,“y”:-4909011.820139259,“z”:3859568.8387547606},{“x”:-1255181.07296848,“y”:-4910268.48690153,“z”:3859279.35456998},{“x”:-1138496.5803506162,“y”:-4940046.6618110305,“z”:3857474.7753535006},{“x”:-1115336.3068021636,“y”:-5076814.278024389,“z”:3683904.2570154625},{“x”:-1066850.382063043,“y”:-5297213.735413228,“z”:3377147.272534278},{“x”:-1066197.252735581,“y”:-5299543.261221864,“z”:3373720.1076408722},{“x”:-1064841.1424150805,“y”:-5301875.301421271,“z”:3370504.489253085},{“x”:-1062823.2584490725,“y”:-5304138.997156365,“z”:3367598.1181048406},{“x”:-1060204.914539938,“y”:-5306265.566324157,“z”:3365089.2976688333},{“x”:-1057065.6676036788,“y”:-5308190.39358589,“z”:3363054.2517197942},{“x”:-1053500.9004929066,“y”:-5309854.993745942,“z”:3361554.8089705245},{“x”:-1049618.9240286828,“y”:-5311208.788831963,“z”:3360636.525053231},{“x”:-1045537.6863710174,“y”:-5312210.644875676,“z”:3360327.298835408},{“x”:-1041381.1896713077,“y”:-5312830.12170009,“z”:3360636.5250532315},{“x”:-1037275.7228315576,“y”:-5313048.397744213,“z”:3361554.8089705245},{“x”:-1033346.0247764753,“y”:-5312858.841834836,“z”:3363054.2517197942},{“x”:-1029711.4947566262,“y”:-5312267.214545794,“z”:3365089.2976688333},{“x”:-1026482.5647792547,“y”:-5311291.493041917,“z”:3367598.118104841},{“x”:-1023757.3443508404,“y”:-5309961.324745074,“z”:3370504.489253085},{“x”:-1021618.6394593279,“y”:-5308317.126435858,“z”:3373720.1076408722},{“x”:-1020131.4363732965,“y”:-5306408.8561739735,“z”:3377147.272534278},{“x”:-1019340.9267327464,“y”:-5304294.495356581,“z”:3380681.8540176493},{“x”:-951155.2327489648,“y”:-4996676.840350923,“z”:3835364.0961942123},{“x”:-948023.606200188,“y”:-4982387.883496844,“z”:3854550.729344544},{“x”:-871816.539801427,“y”:-4997189.283202227,“z”:3853387.434943098},{“x”:-853054.4132535241,“y”:-5000648.056094889,“z”:3853101.5520290914},{“x”:-822747.6856930177,“y”:-5116083.93024851,“z”:3706322.1360292253},{“x”:-755492.6351591299,“y”:-5329869.87898662,“z”:3409400.177076284},{“x”:-754007.080970226,“y”:-5332141.021996233,“z”:3406197.9026276907},{“x”:-751864.507017947,“y”:-5334303.699471814,“z”:3403303.5922217257},{“x”:-749130.0157130425,“y”:-5336292.198845563,“z”:3400805.182860468},{“x”:-745886.6930972579,“y”:-5338046.10002729,“z”:3398778.5819715145},{“x”:-742233.0843300154,“y”:-5339512.111304788,“z”:3397285.3616575324},{“x”:-738280.199632643,“y”:-5340645.688625001,“z”:3396370.88847596},{“x”:-734148.1416398869,“y”:-5341412.389049669,“z”:3396062.9455009727},{“x”:-729962.4565939817,“y”:-5341788.917259995,“z”:3396370.88847596},{“x”:-725850.320194573,“y”:-5341763.833315547,“z”:3397285.361657533},{“x”:-721936.6739350536,“y”:-5341337.900169182,“z”:3398778.581971515},{“x”:-718340.4292607871,“y”:-5340524.060388801,“z”:3400805.1828604685},{“x”:-715170.8548313535,“y”:-5339347.042805122,“z”:3403303.5922217257},{“x”:-712524.2566190015,“y”:-5337842.611049694,“z”:3406197.9026276907},{“x”:-710481.0516959609,“y”:-5336056.476827202,“z”:3409400.177076284},{“x”:-709103.3246220254,“y”:-5334042.910950411,“z”:3412813.120291318},{“x”:-623654.2060156316,“y”:-5133263.777188425,“z”:3721284.9558953824},{“x”:-587899.9304467976,“y”:-5041799.0780018605,“z”:3849080.26059686},{“x”:-482523.48222085077,“y”:-5054191.815644208,“z”:3847490.321651172},{“x”:-477525.20139517804,“y”:-5054724.225590656,“z”:3847415.000596161},{“x”:-467584.6088451352,“y”:-5143951.390793032,“z”:3729346.753712819},{“x”:-439137.4091256502,“y”:-5354943.235013528,“z”:3425389.957922652},{“x”:-438219.3020494734,“y”:-5357211.4790449515,“z”:3421982.080089636},{“x”:-436602.5556266001,“y”:-5359398.297611214,“z”:3418784.558394531},{“x”:-434336.2966287156,“y”:-5361437.244731891,“z”:3415894.5437006443},{“x”:-431489.38561876275,“y”:-5363266.367431327,“z”:3413399.8424834376},{“x”:-428148.3244887298,“y”:-5364830.08822095,“z”:3411376.2494965806},{“x”:-424414.6281532513,“y”:-5366080.893857177,“z”:3409885.245445514},{“x”:-420401.74025679345,“y”:-5366980.779054801,“z”:3408972.1295446563},{“x”:-416231.5865863895,“y”:-5367502.4012831235,“z”:3408664.643625943},{“x”:-412030.8708717956,“y”:-5367629.911553444,“z”:3408972.1295446563},{“x”:-407927.22546937194,“y”:-5367359.435954552,“z”:3409885.2454455136},{“x”:-404045.3338282858,“y”:-5366699.193308202,“z”:3411376.2494965806},{“x”:-400503.1424953256,“y”:-5365669.245375925,“z”:3413399.8424834376},{“x”:-397408.2777013126,“y”:-5364300.887215586,“z”:3415894.543700645},{“x”:-394854.77536950866,“y”:-5362635.696221174,“z”:3418784.5583945303},{“x”:-392920.2238814692,“y”:-5360724.268749948,“z”:3421982.080089636},{“x”:-233232.54623103954,“y”:-5169921.58283831,“z”:3715522.2423877926}];
var innerRings = [[{“x”:-398612.37276631227,“y”:-5304846.389739985,“z”:3506774.2752411817},{“x”:-419712.70887312567,“y”:-5143141.894067795,“z”:3736106.4070859123},{“x”:-428993.06240006443,“y”:-5059633.798088292,“z”:3846684.050730237},{“x”:-216974.725398098,“y”:-5075580.643873942,“z”:3843497.8386124396},{“x”:-278142.23030261043,“y”:-5158022.397442363,“z”:3728855.724649285},{“x”:-398612.37276631227,“y”:-5304846.389739985,“z”:3506774.2752411817}],[{“x”:-577225.3048506861,“y”:-5013556.951300249,“z”:3887139.874798813},{“x”:-540705.7115392252,“y”:-4913519.221582091,“z”:4017069.0283701937},{“x”:-500216.60756118514,“y”:-4796350.762975617,“z”:4160382.412246335},{“x”:-490773.64019773004,“y”:-4915584.8106354475,“z”:4020924.734206431},{“x”:-480591.13901035825,“y”:-5024876.497823806,“z”:3885681.8551814426},{“x”:-577225.3048506861,“y”:-5013556.951300249,“z”:3887139.874798813}],[{“x”:-636270.2546018785,“y”:-5035360.662410316,“z”:3849811.468926872},{“x”:-670290.0512054554,“y”:-5122431.212353565,“z”:3728052.208773908},{“x”:-730193.5734325357,“y”:-5265725.658144596,“z”:3512326.9817148875},{“x”:-774938.7987861199,“y”:-5118598.052631229,“z”:3713103.4269473394},{“x”:-803721.3603452999,“y”:-5009395.05692313,“z”:3852350.7771409517},{“x”:-636270.2546018785,“y”:-5035360.662410316,“z”:3849811.468926872}],[{“x”:-866763.5147191804,“y”:-4968225.709289639,“z”:3891532.193042193},{“x”:-941739.8577478391,“y”:-4953655.418277416,“z”:3892676.7768366006},{“x”:-902355.4597655431,“y”:-4771786.9998006765,“z”:4120920.4082188276},{“x”:-878969.7437981971,“y”:-4888086.704133924,“z”:3988413.7180339787},{“x”:-860602.3252128907,“y”:-4969370.698875443,“z”:3891438.284131929},{“x”:-866763.5147191804,“y”:-4968225.709289639,“z”:3891532.193042193}],[{“x”:-1067754.2273934262,“y”:-5082068.262970909,“z”:3690706.4189255745},{“x”:-1089957.4348764666,“y”:-4951568.842458082,“z”:3856727.211137454},{“x”:-995390.8681834716,“y”:-4972575.65030856,“z”:3855275.5883577676},{“x”:-998621.6442623687,“y”:-4987407.1956574535,“z”:3835364.0961942123},{“x”:-1044575.4078495858,“y”:-5195557.094333161,“z”:3537140.0901758103},{“x”:-1067754.2273934262,“y”:-5082068.262970909,“z”:3690706.4189255745}],[{“x”:-89118.7712709775,“y”:-5051572.965463638,“z”:3879800.4287876515},{“x”:-145326.84384950358,“y”:-5049616.526774185,“z”:3880643.2339294287},{“x”:-84161.94364185735,“y”:-4958341.063018081,“z”:3997586.8198991255},{“x”:7177.290260186915,“y”:-4808766.321296478,“z”:4175981.0451473794},{“x”:11299.37312403481,“y”:-5053509.596352048,“z”:3878295.3377023814},{“x”:-89118.7712709775,“y”:-5051572.965463638,“z”:3879800.4287876515}],[{“x”:65014.17229392558,“y”:-5336029.612383772,“z”:3481594.4500682177},{“x”:60208.46930820234,“y”:-5083022.014297575,“z”:3839342.371486929},{“x”:266804.6675910725,“y”:-5078728.3472142,“z”:3836245.760390845},{“x”:156007.64037249165,“y”:-5227336.586415716,“z”:3638956.031151674},{“x”:65014.17229392558,“y”:-5336029.612383772,“z”:3481594.4500682177}]];
Very cool example, Jonah. You’re right that each call to eliminateHole will only remove a single inner ring, which requires looping through them. I usually do something like the following:
while (innerRings.length > 0) {
outerRing = Cesium.PolygonPipeline.eliminateHole(outerRing, innerRings);
}
I added this as an example to the documentation. Continually passing the list of multiple inner rings (instead of one at a time in some sequential order) will ensure that the holes are added in the proper ordered, as described in Eberly’s paper. I plan on opening a pull request for this branch very soon.
Thanks,
Kristian
If the idea is to only remove one inner ring at a time, then why does the function take an array of inner rings as the second parameter?
Good point. I’ve encapsulated this process in the new PolygonPipeline.eliminateHoles to improve usability.
I think that is better. Just one more thing to add. Is it correct that the inner rings ordering should be from right most ring to left most? I didn’t see any mention of ordering being necessary in the jsdocs, but I know you said something about it before.
Users do not have to worry about ordering the inner rings before doing any kind of processing. The eliminateHoles function will automatically sort through the inner rings and add them in the correct order (which, as you mention, is from right to left).