- Excel Version
- 365
Today I am presenting the gift-wrapping algorithm, which calculates the convex hull for a bidimensional set of points. You can read more about it on the link below.
Here are the main features of the code:
The TS tool I chose to highlight are interfaces; the relevant techniques shown are:
en.wikipedia.org
Here are the main features of the code:
- It will start from scratch and generate an aleatory array of coordinates. If you prefer to use a previously created table, type ”ok” at cell F1.
- The code will find the vertices for the convex hull. The right chain is determined first, and then the left chain. Polar coordinates are employed to perform the calculations.
- Finally, the solution is depicted in graphical form.
The TS tool I chose to highlight are interfaces; the relevant techniques shown are:
- There are optional and read only properties.
- The point interface is a merged one.
- The interfaces at the charting function use index signatures. Also, one is an extension of the other.
Gift wrapping algorithm - Wikipedia
JavaScript:
interface point {
readonly x: number
readonly y: number
}
interface point {
spec?: string
condition: string
}
var points: point[] = []
var start: point
function main(workbook: ExcelScript.Workbook) {
let sht = workbook.getActiveWorksheet();
let tbls = sht.getTables()
if (tbls.length > 0) { tbls[0].convertToRange() }
if (sht.getRange("f1").getValue() != "ok") { // create table
sht.getRange("a2:c50").clear()
let base1 = sht.getRange("b1")
var i = 0
do {
base1 = base1.getOffsetRange(1, 0)
base1.getOffsetRange(0, -1).setValue(i)
base1.setValue(Math.random() * 10)
base1.getOffsetRange(0, 1).setValue(Math.random() * 10)
i++
}
while (i < 40)
}
let lr = sht.getUsedRange().getLastRow().getRowIndex() + 1
let nt = workbook.addTable(sht.getRange("a1:C" + lr), true);
nt.getSort().apply([{ key: 0, ascending: true }]);
let tr = nt.getRange().getRow(1)
for (let i = 0; i < nt.getRowCount(); i++) {
const el: point = {
x: Number(tr.getOffsetRange(i, 0).getColumn(1).getValue()),
y: Number(tr.getOffsetRange(i, 0).getColumn(2).getValue()), spec: "init",
condition: "not used"
};
points.push(el)
}
nt.getSort().apply([{ key: 2, ascending: true }]);
let bottom = tr.getColumn(0).getValue()
points[Number(bottom)].spec = "bottom"
let up = nt.getRange().getLastRow().getColumn(0).getValue()
points[Number(up)].spec = "up"
nt.getSort().apply([{ key: 1, ascending: true }]);
var vert: number[][] = []
start = points[Number(bottom)];
let k = 0;
do {
let res = march(start, true); // right chaim
vert.push([points[res].x, points[res].y])
k++; start = points[res]
}
while (start.spec != "up" && k < 20)
start = points[Number(up)]
k = 0
do {
let res = march(start, false) // left chain
vert.push([points[res].x, points[res].y])
k++
start = points[res]
}
while (start.spec != "bottom" && k < 20)
sht.getRange("g5:h50").clear()
let base = sht.getRange("g5")
let rng = base.getResizedRange(vert.length - 1, 1).setValues(vert)
let rng2 = base.getOffsetRange(vert.length, 0).getResizedRange(0, 1)
rng2.setValues(base.getResizedRange(0, 1).getValues())
cht(workbook, nt.getRangeBetweenHeaderAndTotal().getColumnsAfter(-2), base.getSurroundingRegion().getColumn(0), base.getSurroundingRegion().getColumn(1))
}
function march(curr: point, rchain: boolean) {
let rad = rchain ? 10 : 0
var temp: number
for (let j = 0; j < points.length; j++) {
var boly = points[j].y >= curr.y
if (!rchain) { boly = !boly }
if (points[j].condition != "used" && boly) {
let temp = arcos(curr.x, points[j].x, curr.y, points[j].y)
if (curr.spec === "bottom") {
}
if (rchain ? temp < rad : temp > rad) {
rad = temp
var next = j;
}
}
}
points[next].condition = "used"
return next
}
function arcos(x1: number, x2: number, y1: number, y2: number) {
let x = x2 - x1
let y = y2 - y1
return Math.acos(x / Math.sqrt(x * x + y * y))
}
function cht(workbook: ExcelScript.Workbook, crng: ExcelScript.Range, hrr: ExcelScript.Range, fsr: ExcelScript.Range) {
interface dbn { rel?: { [i: string]: ExcelScript.ChartSeries } }
interface mychart extends dbn {
rel?: { [i: string]: ExcelScript.ChartSeries; }
blo: { [j: string]: ExcelScript.ChartAxis; }
}
let sheet = workbook.getActiveWorksheet();
let chart_3 = sheet.addChart(ExcelScript.ChartType.xyscatter, crng)
chart_3.setLeft(429);
chart_3.setTop(103);
chart_3.setWidth(360);
chart_3.setHeight(216);
chart_3.getTitle().setVisible(false)
const sec = chart_3.addChartSeries();
const col = chart_3.getSeries()
const pb: dbn = { rel: { first: col[0], second: col[1] } }
pb.rel.first.setName("1st")
pb.rel.second.setXAxisValues(hrr);
pb.rel.second.setValues(fsr);
pb.rel.second.setChartType(ExcelScript.ChartType.xyscatterLines)
pb.rel.second.setName("sec")
let cat = chart_3.getAxes().getChartAxis(ExcelScript.ChartAxisType.category)
const lvar: mychart = { blo: { catax: cat, vax: chart_3.getAxes().getValueAxis() } }
lvar.blo.catax.setMinimum(-1)
lvar.blo.catax.getMajorGridlines().setVisible(false)
lvar.blo.catax.setVisible(false)
lvar.blo.vax.setMinimum(-1)
lvar.blo.vax.getMajorGridlines().setVisible(false)
lvar.blo.vax.setVisible(false)
}
