Skip to content

Instantly share code, notes, and snippets.

@JustinShenk
Last active February 20, 2018 12:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save JustinShenk/478d179952db7625acdb to your computer and use it in GitHub Desktop.
Save JustinShenk/478d179952db7625acdb to your computer and use it in GitHub Desktop.
Hilbert Basis
<!DOCTYPE html>
<meta charset="utf-8">
<html>
<head>
<script src="https://d3js.org/d3.v4.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.2.1/jquery.js"></script>
<style>
body {
padding: 30px;
margin: 0;
font-family: sans-serif;
font-size: 12px;
}
svg>g>line {
stroke: #ddd;
shape-rendering: crispEdges;
}
svg marker {
hidden:
}
svg text {
text-anchor: middle;
}
g line {
stroke: black;
}
.compare line {
stroke-dashArray: 2, 4;
}
.gradings line {
stroke:blue;
stroke-dashArray: 2, 4;
stroke-opacity: 0.0;
}
.handle circle {
fill: yellow;
fill-opacity: 0.2;
stroke: black;
stroke-opacity: 0.15;
}
.basisCircles circle {
fill: none;
fill-opacity: 1.0;
stroke: red;
}
.hilbertSeries circle {
fill-opacity: 0.8;
stroke: blue;
}
.difference {
fill-opacity: 0.4;
}
.noselect {
-webkit-touch-callout: none; /* iOS Safari */
-webkit-user-select: none; /* Safari */
-khtml-user-select: none; /* Konqueror HTML */
-moz-user-select: none; /* Firefox */
-ms-user-select: none; /* Internet Explorer/Edge */
user-select: none; /* Non-prefixed version, currently
supported by Chrome and Opera */
}
</style>
<script>
// Load Hilbert Basis lookup dictionary.
var hilbertBases = {};
$(document).ready(function() {
$.getJSON('https://s3.eu-central-1.amazonaws.com/allpurpose1/bases.json', function(data) {
console.log('bases loaded');
hilbertBases = data;
calculate();
})
});
function drawHilbertBasis(basis) {
console.log(basis);
update();
svg.selectAll("circle.basisCircles").remove();
// svgContainer.selectAll("circle.basisCircles").remove();
if (basis != undefined) {
basis.forEach(function(element) {
basisCircles.append("circle")
.attr("class", "basisCircles")
.attr("r", 4)
.attr("fill", "none")
.attr("stroke", "red")
.attr("fill-opacity", 1.0)
.attr("cx", element[0] * scaleFactor)
.attr("cy", element[1] * -scaleFactor);
});
} else {
console.log("Error: Basis not loaded")
}
}
function calculate() {
if (hilbertBases == undefined) {
$.getJSON('bases.json', function(data) {
console.log('bases loaded');
hilbertBases = data;
})
}
var sourceEnc = escape($("#sourceInput").val());
var compareEnc = escape($("#compareInput").val());
var [sx, sy] = sourceEnc.split('%2C');
var [cx, cy] = compareEnc.split('%2C');
var vectorCombination = '[' + String(sx) + ', ' + String(sy) + '],[' + String(cx) + ', ' + String(cy) + ']';
var output = JSON.stringify(hilbertBases[vectorCombination]);
$("#output").html(output);
sourceVector.datum().x = sx * scaleFactor;
sourceVector.datum().y = -sy * scaleFactor;
compareVector.datum().x = cx * scaleFactor;
compareVector.datum().y = -cy * scaleFactor;
drawHilbertBasis(hilbertBases[vectorCombination]);
};
</script>
<svg>
<defs>
<marker id="arrowhead" class="noselect" viewBox="0 0 10 10" refX="5" refY="5" markerWidth="8" markerHeight="8" orient="auto">
<path d="M0,0L10,5L0,10z" />
</marker>
</defs>
</svg>
<script>
"use strict";
var scaleFactor = 20;
var width = 220,
height = 200;
function drawHilbertSeries(i){
// Find hilbert series of grading `i`
var source = sourceVector.datum(),
compare = compareVector.datum();
// See if point is within cone
var gradingPoints = [];
console.log(source.x,compare.x, source.y,compare.y);
for (var x = 0; x <= i; x++) { // iterate over lattice points along grading
var y = i-x;
var rightOfSourceVector = (x * Math.abs(source.y) - y * source.x) >= 0;
var leftOfCompareVector = (x * Math.abs(compare.y) - y * compare.x) <= 0;
var insideCone = rightOfSourceVector && leftOfCompareVector;
if (insideCone) {
gradingPoints.push([x,y]);
};
};
svg.selectAll("circle.hilbertSeries").remove();
gradingPoints.forEach(function(element) {
hilbertSeries.append("circle")
.attr("class", "hilbertSeries")
.attr("r", 3)
.attr("stroke", "blue")
.attr("fill-opacity", 0.8)
.attr("cx", element[0] * scaleFactor)
.attr("cy", element[1] * -scaleFactor);
});
gradingText
.text(`Hilbert function has value ${gradingPoints.length} for degree ${i}`)
};
function showGrading(d){
var source = sourceVector.datum(),
compare = compareVector.datum();
var sourceLength = Math.sqrt(source.x * source.x + source.y * source.y),
compareLength = Math.sqrt(compare.x * compare.x + compare.y * compare.y);
// The math-y bits
var a2 = Math.atan2(source.y, source.x);
var a1 = Math.atan2(compare.y, compare.x);
var sign = a1 > a2 ? 1 : -1;
var angle = a1 - a2;
var K = -sign * Math.PI * 2;
var angle = (Math.abs(K + angle) < Math.abs(angle)) ? K + angle : angle;
// Clear all gradings
var mousePosition = d;
svg.selectAll(".gradings")
.style('stroke', 'blue')
.style("stroke-opacity",0)
.filter(function(gradingData,i) {
var x = Math.floor((mousePosition[0]-10)/scaleFactor);
var y = Math.floor((190-mousePosition[1])/scaleFactor);
var z = x + y; // grading
if (i === z) drawHilbertSeries(z);
return i === z;
})
.style('stroke-opacity',1);
};
var svg = d3.select("svg")
.attr("width", width)
.attr("height", height)
.on("mousemove", function() {
showGrading(d3.mouse(this))
})
.append("g")
.attr("transform", "translate(20,180)");
var drag = d3.drag()
.on("drag", function(d) {
d.x = d3.event.x;
d.y = d3.event.y;
var windowWidth = 9 * scaleFactor,
windowHeight = 8 * scaleFactor;
if (d.x > windowWidth) {
d.x = windowWidth;
} else if (d.x < 0) {
d.x = 0;
}
if (d.y < -windowHeight) {
d.y = -windowHeight;
} else if (d.y > 0) {
d.y = 0;
}
update();
})
.on("end", function(r) {
var newX = Math.round(d3.event.x / scaleFactor) * scaleFactor;
var newY = Math.round(d3.event.y / scaleFactor) * scaleFactor;
r.x = newX < 9 * scaleFactor ? newX : 9 * scaleFactor;
r.y = newY > -8 * scaleFactor ? newY : -8 * scaleFactor;
if (r.x < 0) r.x = 0;
if (r.y > 0) r.y = 0;
var source = JSON.stringify(d3.select('.source'));
var sx = sourceVector.datum().x;
var sy = sourceVector.datum().y;
var cx = compareVector.datum().x;
var cy = compareVector.datum().y;
if (sx == r.x && sy == r.y) {
$("#sourceInput").val(String(r.x / scaleFactor) + ',' + String(-r.y / scaleFactor));
} else {
$("#compareInput").val(String(r.x / scaleFactor) + ',' + String(-r.y / scaleFactor));
}
update();
calculate();
});
var cone = d3.arc();
// Basis circles
var basisCircles = svg.append("g")
.attr("class", "basisCircles")
.datum({});
var hilbertSeries = svg.append("g")
.attr("class", "hilbertSeries")
.datum({});
var gradings = svg.append("g")
.attr("class", "gradings")
.datum({});
var gradingIntervals = Array.from(new Array(19), (x,i) => i+1);
gradingIntervals.forEach(function(element){
gradings.append("line")
.attr("class","gradings")
.attr("x1", 0)
.attr("x2", element * scaleFactor)
.attr("y1", -element * scaleFactor)
.attr("y2", 0)
});
// Difference
var differenceArc = svg.append("g")
.datum({});
// Origin
svg.append("line")
.attr("y1", -height)
.attr("y2", 20);
svg.append("line")
.attr("x1", -20)
.attr("x2", width);
// Source vector
var sourceVector = svg.append("g")
.attr("class", "source")
.datum({
x: 40,
y: -120
});
// Compare vector
var compareVector = svg.append("g")
.attr("class", "compare")
.datum({
x: 120,
y: -40
});
var gradings = svg.append("g")
.attr("class", "gradings")
.datum({})
var format = d3.format(".2f")
svg.append("circle")
.attr("r", 4);
// Draw background lattice in first quadrant.
var latticeDimensions = [10, 9];
for (var i = 0; i < latticeDimensions[0]; i++) {
for (var j = 0; j < latticeDimensions[1]; j++) {
svg.append("circle")
.attr("r", 1)
.attr("cx", i * scaleFactor)
.attr("cy", j * -scaleFactor)
.attr("class", "noselect");
}
};
var conePath = differenceArc.append("path")
.attr("class", "difference");
var sourceLine = sourceVector.append("line")
.attr("marker-end", "url(#arrowhead)");
var sourceHandle = sourceVector.append("g")
.attr("class", "handle")
.call(drag);
var sourceText = sourceHandle.append("text")
.attr("dy", -15);
sourceHandle.append("circle")
.attr("r", 10);
var compareLine = compareVector.append("line")
.attr("marker-end", "url(#arrowhead)");
var compareHandle = compareVector.append("g")
.attr("class", "handle")
.call(drag);
var compareText = compareHandle.append("text")
.attr("dy", -15);
var gradingText = gradings.append("text")
.attr("dy", 15)
.attr("dx", 90);
compareHandle.append("circle")
.attr("r", 10);
// Update
function update() {
var source = sourceVector.datum(),
compare = compareVector.datum();
var sourceLength = Math.sqrt(source.x * source.x + source.y * source.y),
compareLength = Math.sqrt(compare.x * compare.x + compare.y * compare.y);
// Geometry for cone
var a2 = Math.atan2(source.y, source.x);
var a1 = Math.atan2(compare.y, compare.x);
var sign = a1 > a2 ? 1 : -1;
var angle = a1 - a2;
var K = -sign * Math.PI * 2;
var angle = (Math.abs(K + angle) < Math.abs(angle)) ? K + angle : angle;
sourceLine
.attr("x2", (d) => d.x)
.attr("y2", (d) => d.y);
sourceHandle
.attr("transform", (d) => `translate(${d.x}, ${d.y})`);
sourceText
.text(`${Math.round(source.x/scaleFactor)}, ${Math.round(0-source.y/scaleFactor)}`)
compareLine
.attr("x2", (d) => d.x)
.attr("y2", (d) => d.y);
compareText
.text(`${Math.round(compare.x/scaleFactor)}, ${0-Math.round(compare.y/scaleFactor)}`);
compareHandle
.attr("transform", (d) => `translate(${d.x}, ${d.y})`)
cone
.innerRadius(0)
.outerRadius(20 * 15) // Temp
.startAngle(a2 + Math.PI / 2)
.endAngle(a2 + angle + Math.PI / 2);
conePath
.style("fill", angle > 0 ? "lightgrey" : "magenta")
.attr("d", cone());
};
update();
</script>
<title>Normaliz - Hilbert Basis Visualization</title>
</head>
<body>
<div id="interact" class="container">
<div class="col-md-6 center">
<form id="inputVectors" method="GET">
<!-- Source Vector X: -->
<input id="sourceInput" name="sourceInput" value="2,6" type="hidden">
<!-- Compare Vector: -->
<input id="compareInput" name="compareInput" value="6,2" type="hidden">
<!-- <input type="button" tvalue="Calculate" onclick="calculate()" /> -->
<input type="hidden" tvalue="Calculate" onclick="calculate()" />
</form>
</div>
</div>
</body>
<script type="text/javascript">
$(document).ready(function() {
calculate();
})
</script>
</html>
MIT License
Copyright 2017 University of Osnabrück
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment