Skip to content

Instantly share code, notes, and snippets.

@Fil
Last active Oct 31, 2018
Embed
What would you like to do?
Furuti 3 globe clip polygon + martinez [UNLISTED]
license: gpl-3.0

Research for d3-geo's polyhedra projections; issue #86: we need to recreate projection.clipPolygon() at least for this type of polygon.

Polygon coordinates given by adding these lines in src/polyhedra/index.js:

  var polygon = [];
  outline({point: function(λ, φ) { polygon.push([λ, φ]); }}, root);
  polygon.push(polygon[0]);
  console.log(polygon);

Here we exagerated the value of epsilon to show how this works.

With the usual epsilon, the polygon would look like a line, because its “interior” (in purple) covers the whole sphere. The green line is actually the polygon's edge on both sides. The polygon has almost no “exterior” (in white).

forked from mbostock's block: This Is a Globe

forked from Fil's block: Furuti 3 globe clip polygon

forked from Fil's block: Furuti 3 globe clip polygon

(function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){
greinerHormann = require('greiner-hormann');
},{"greiner-hormann":3}],2:[function(require,module,exports){
var Polygon = require('./polygon');
/**
* Clip driver
* @api
* @param {Array.<Array.<Number>>} polygonA
* @param {Array.<Array.<Number>>} polygonB
* @param {Boolean} sourceForwards
* @param {Boolean} clipForwards
* @return {Array.<Array.<Number>>}
*/
module.exports = function(polygonA, polygonB, eA, eB) {
var result, source = new Polygon(polygonA),
clip = new Polygon(polygonB),
result = source.clip(clip, eA, eB);
return result;
};
},{"./polygon":5}],3:[function(require,module,exports){
var clip = require('./clip');
module.exports = {
/**
* @api
* @param {Array.<Array.<Number>|Array.<Object>} polygonA
* @param {Array.<Array.<Number>|Array.<Object>} polygonB
* @return {Array.<Array.<Number>>|Array.<Array.<Object>|Null}
*/
union: function(polygonA, polygonB) {
return clip(polygonA, polygonB, false, false);
},
/**
* @api
* @param {Array.<Array.<Number>|Array.<Object>} polygonA
* @param {Array.<Array.<Number>|Array.<Object>} polygonB
* @return {Array.<Array.<Number>>|Array.<Array.<Object>>|Null}
*/
intersection: function(polygonA, polygonB) {
return clip(polygonA, polygonB, true, true);
},
/**
* @api
* @param {Array.<Array.<Number>|Array.<Object>} polygonA
* @param {Array.<Array.<Number>|Array.<Object>} polygonB
* @return {Array.<Array.<Number>>|Array.<Array.<Object>>|Null}
*/
diff: function(polygonA, polygonB) {
return clip(polygonA, polygonB, false, true);
},
clip: clip
};
},{"./clip":2}],4:[function(require,module,exports){
/**
* Intersection
* @param {Vertex} s1
* @param {Vertex} s2
* @param {Vertex} c1
* @param {Vertex} c2
* @constructor
*/
var Intersection = function(s1, s2, c1, c2) {
/**
* @type {Number}
*/
this.x = 0.0;
/**
* @type {Number}
*/
this.y = 0.0;
/**
* @type {Number}
*/
this.toSource = 0.0;
/**
* @type {Number}
*/
this.toClip = 0.0;
var d = (c2.y - c1.y) * (s2.x - s1.x) - (c2.x - c1.x) * (s2.y - s1.y);
if (d === 0) {
return;
}
/**
* @type {Number}
*/
this.toSource = ((c2.x - c1.x) * (s1.y - c1.y) - (c2.y - c1.y) * (s1.x - c1.x)) / d;
/**
* @type {Number}
*/
this.toClip = ((s2.x - s1.x) * (s1.y - c1.y) - (s2.y - s1.y) * (s1.x - c1.x)) / d;
if (this.valid()) {
this.x = s1.x + this.toSource * (s2.x - s1.x);
this.y = s1.y + this.toSource * (s2.y - s1.y);
}
};
/**
* @return {Boolean}
*/
Intersection.prototype.valid = function() {
return (0 < this.toSource && this.toSource < 1) && (0 < this.toClip && this.toClip < 1);
};
module.exports = Intersection;
},{}],5:[function(require,module,exports){
var Vertex = require('./vertex');
var Intersection = require('./intersection');
/**
* Polygon representation
* @param {Array.<Array.<Number>>} p
* @param {Boolean=} arrayVertices
*
* @constructor
*/
var Polygon = function(p, arrayVertices) {
/**
* @type {Vertex}
*/
this.first = null;
/**
* @type {Number}
*/
this.vertices = 0;
/**
* @type {Vertex}
*/
this._lastUnprocessed = null;
/**
* Whether to handle input and output as [x,y] or {x:x,y:y}
* @type {Boolean}
*/
this._arrayVertices = (typeof arrayVertices === "undefined") ?
Array.isArray(p[0]) :
arrayVertices;
for (var i = 0, len = p.length; i < len; i++) {
this.addVertex(new Vertex(p[i]));
}
};
/**
* Add a vertex object to the polygon
* (vertex is added at the 'end' of the list')
*
* @param vertex
*/
Polygon.prototype.addVertex = function(vertex) {
if (this.first == null) {
this.first = vertex;
this.first.next = vertex;
this.first.prev = vertex;
} else {
var next = this.first,
prev = next.prev;
next.prev = vertex;
vertex.next = next;
vertex.prev = prev;
prev.next = vertex;
}
this.vertices++;
};
/**
* Inserts a vertex inbetween start and end
*
* @param {Vertex} vertex
* @param {Vertex} start
* @param {Vertex} end
*/
Polygon.prototype.insertVertex = function(vertex, start, end) {
var prev, curr = start;
while (!curr.equals(end) && curr._distance < vertex._distance) {
curr = curr.next;
}
vertex.next = curr;
prev = curr.prev;
vertex.prev = prev;
prev.next = vertex;
curr.prev = vertex;
this.vertices++;
};
/**
* Get next non-intersection point
* @param {Vertex} v
* @return {Vertex}
*/
Polygon.prototype.getNext = function(v) {
var c = v;
while (c._isIntersection) {
c = c.next;
}
return c;
};
/**
* Unvisited intersection
* @return {Vertex}
*/
Polygon.prototype.getFirstIntersect = function() {
var v = this._firstIntersect || this.first;
do {
if (v._isIntersection && !v._visited) {
break;
}
v = v.next;
} while (!v.equals(this.first));
this._firstIntersect = v;
return v;
};
/**
* Does the polygon have unvisited vertices
* @return {Boolean} [description]
*/
Polygon.prototype.hasUnprocessed = function() {
var v = this._lastUnprocessed || this.first;
do {
if (v._isIntersection && !v._visited) {
this._lastUnprocessed = v;
return true;
}
v = v.next;
} while (!v.equals(this.first));
this._lastUnprocessed = null;
return false;
};
/**
* The output depends on what you put in, arrays or objects
* @return {Array.<Array<Number>|Array.<Object>}
*/
Polygon.prototype.getPoints = function() {
var points = [],
v = this.first;
if (this._arrayVertices) {
do {
points.push([v.x, v.y]);
v = v.next;
} while (v !== this.first);
} else {
do {
points.push({
x: v.x,
y: v.y
});
v = v.next;
} while (v !== this.first);
}
return points;
};
/**
* Clip polygon against another one.
* Result depends on algorithm direction:
*
* Intersection: forwards forwards
* Union: backwars backwards
* Diff: backwards forwards
*
* @param {Polygon} clip
* @param {Boolean} sourceForwards
* @param {Boolean} clipForwards
*/
Polygon.prototype.clip = function(clip, sourceForwards, clipForwards) {
var sourceVertex = this.first,
clipVertex = clip.first,
sourceInClip, clipInSource;
// calculate and mark intersections
do {
if (!sourceVertex._isIntersection) {
do {
if (!clipVertex._isIntersection) {
var i = new Intersection(
sourceVertex,
this.getNext(sourceVertex.next),
clipVertex, clip.getNext(clipVertex.next));
if (i.valid()) {
var sourceIntersection =
Vertex.createIntersection(i.x, i.y, i.toSource),
clipIntersection =
Vertex.createIntersection(i.x, i.y, i.toClip);
sourceIntersection._corresponding = clipIntersection;
clipIntersection._corresponding = sourceIntersection;
this.insertVertex(
sourceIntersection,
sourceVertex,
this.getNext(sourceVertex.next));
clip.insertVertex(
clipIntersection,
clipVertex,
clip.getNext(clipVertex.next));
}
}
clipVertex = clipVertex.next;
} while (!clipVertex.equals(clip.first));
}
sourceVertex = sourceVertex.next;
} while (!sourceVertex.equals(this.first));
// phase two - identify entry/exit points
sourceVertex = this.first;
clipVertex = clip.first;
sourceInClip = sourceVertex.isInside(clip);
clipInSource = clipVertex.isInside(this);
sourceForwards ^= sourceInClip;
clipForwards ^= clipInSource;
do {
if (sourceVertex._isIntersection) {
sourceVertex._isEntry = sourceForwards;
sourceForwards = !sourceForwards;
}
sourceVertex = sourceVertex.next;
} while (!sourceVertex.equals(this.first));
do {
if (clipVertex._isIntersection) {
clipVertex._isEntry = clipForwards;
clipForwards = !clipForwards;
}
clipVertex = clipVertex.next;
} while (!clipVertex.equals(clip.first));
// phase three - construct a list of clipped polygons
var list = [];
while (this.hasUnprocessed()) {
var current = this.getFirstIntersect(),
// keep format
clipped = new Polygon([], this._arrayVertices);
clipped.addVertex(new Vertex(current.x, current.y));
do {
current.visit();
if (current._isEntry) {
do {
current = current.next;
clipped.addVertex(new Vertex(current.x, current.y));
} while (!current._isIntersection);
} else {
do {
current = current.prev;
clipped.addVertex(new Vertex(current.x, current.y));
} while (!current._isIntersection);
}
current = current._corresponding;
} while (!current._visited);
list.push(clipped.getPoints());
}
if (list.length === 0) {
if (sourceInClip) {
list.push(this.getPoints());
}
if (clipInSource) {
list.push(clip.getPoints());
}
if (list.length === 0) {
list = null;
}
}
return list;
};
module.exports = Polygon;
},{"./intersection":4,"./vertex":6}],6:[function(require,module,exports){
/**
* Vertex representation
*
* @param {Number|Array.<Number>} x
* @param {Number=} y
*
* @constructor
*/
var Vertex = function(x, y) {
if (arguments.length === 1) {
// Coords
if (Array.isArray(x)) {
y = x[1];
x = x[0];
} else {
y = x.y;
x = x.x;
}
}
/**
* X coordinate
* @type {Number}
*/
this.x = x;
/**
* Y coordinate
* @type {Number}
*/
this.y = y;
/**
* Next node
* @type {Vertex}
*/
this.next = null;
/**
* Previous vertex
* @type {Vertex}
*/
this.prev = null;
/**
* Corresponding intersection in other polygon
*/
this._corresponding = null;
/**
* Distance from previous
*/
this._distance = 0.0;
/**
* Entry/exit point in another polygon
* @type {Boolean}
*/
this._isEntry = true;
/**
* Intersection vertex flag
* @type {Boolean}
*/
this._isIntersection = false;
/**
* Loop check
* @type {Boolean}
*/
this._visited = false;
};
/**
* Creates intersection vertex
* @param {Number} x
* @param {Number} y
* @param {Number} distance
* @return {Vertex}
*/
Vertex.createIntersection = function(x, y, distance) {
var vertex = new Vertex(x, y);
vertex._distance = distance;
vertex._isIntersection = true;
vertex._isEntry = false;
return vertex;
};
/**
* Mark as visited
*/
Vertex.prototype.visit = function() {
this._visited = true;
if (this._corresponding !== null && !this._corresponding._visited) {
this._corresponding.visit();
}
};
/**
* Convenience
* @param {Vertex} v
* @return {Boolean}
*/
Vertex.prototype.equals = function(v) {
return this.x === v.x && this.y === v.y;
};
/**
* Check if vertex is inside a polygon by odd-even rule:
* If the number of intersections of a ray out of the point and polygon
* segments is odd - the point is inside.
* @param {Polygon} poly
* @return {Boolean}
*/
Vertex.prototype.isInside = function(poly) {
var oddNodes = false,
vertex = poly.first,
next = vertex.next,
x = this.x,
y = this.y;
do {
if ((vertex.y < y && next.y >= y ||
next.y < y && vertex.y >= y) &&
(vertex.x <= x || next.x <= x)) {
oddNodes ^= (vertex.x + (y - vertex.y) /
(next.y - vertex.y) * (next.x - vertex.x) < x);
}
vertex = vertex.next;
next = vertex.next || poly.first;
} while (!vertex.equals(poly.first));
return oddNodes;
};
module.exports = Vertex;
},{}]},{},[1]);
<!DOCTYPE html>
<meta charset="utf-8">
<body>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://d3js.org/topojson.v1.min.js"></script>
<script src="https://raw.githubusercontent.com/w8r/martinez/master/dist/martinez.min.js"></script>
<script>
var width = 960,
height = 500;
var radius = height / 2 - 20,
scale = radius,
velocity = .015;
var projection = d3.geoOrthographic()
.translate([width / 2, height / 2])
.scale(scale)
.clipAngle(90);
var canvas = d3.select("body").append("canvas")
.attr("width", width)
.attr("height", height);
var context = canvas.node().getContext("2d");
var path = d3.geoPath()
.projection(projection)
.context(context);
d3.json("https://unpkg.com/visionscarto-world-atlas/world/110m.json", function(error, world) {
if (error) throw error;
var land = topojson.feature(world, world.objects.land);
var polygon = /* f3 */
[ [ 89.42139757619105, 34.98933287542549 ],
[ 89.42139757619105, -34.98933287542549 ],
[ 0.5786024238089479, -34.98933287542549 ],
[ 0.5786024238089479, 34.98933287542549 ],
[ -0.5786024238089479, 34.98933287542549 ],
[ -0.5786024238089479, -34.98933287542549 ],
[ 0, -35.81174578592711 ],
[ 90, -35.81174578592711 ],
[ 180, -35.81174578592711 ],
[ -90, -35.81174578592711 ],
[ -89.42139757619105, -34.98933287542549 ],
[ -89.42139757619105, 34.98933287542549 ],
[ -90.57860242380896, 34.98933287542549 ],
[ -90.57860242380896, -34.98933287542549 ],
[ -179.42139757619105, -34.98933287542549 ],
[ -179.42139757619105, 34.98933287542549 ],
[ 179.42139757619105, 34.98933287542549 ],
[ 179.42139757619105, -34.98933287542549 ],
[ 90.57860242380896, -34.98933287542549 ],
[ 90.57860242380896, 34.98933287542549 ],
[ 89.42139757619105, 34.98933287542549 ] ];
var land2 = {type: "MultiPolygon", coordinates: land.features[0].geometry.coordinates
//.slice(0,1)
.map(d => {
return d;
console.log(d)
var a = martinez.intersection([polygon], [d]);
console.log('a', a);
return a
})
}
d3.timer(function(elapsed) {
context.clearRect(0, 0, width, height);
projection.rotate([velocity * elapsed, 0]);
context.beginPath();
path(land2);
context.lineWidth = 1;
context.strokeStyle = 'black';
context.stroke();
context.fillStyle = '#eee';
context.fill();
context.beginPath();
path({type: "Polygon", coordinates: [polygon]});
context.lineWidth = 2.5;
context.strokeStyle = '#3f3';
context.stroke();
context.fillStyle = 'rgba(0,0,100,0.1)';
context.fill();
context.beginPath();
context.arc(width / 2, height / 2, radius, 0, 2 * Math.PI, true);
context.lineWidth = 3;
context.strokeStyle = 'black';
context.stroke();
});
});
//d3.select(self.frameElement).style("height", height + "px");
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment