Polygon With Holes
Closed this issue · 6 comments
Hi Floris - I am attempting to calculate the MAT of a path with holes...
More specifically, I am trying to calculate the MAT of a path representing the number zero ('0').
However, the MAT calculation doesn't seem to accommodate the hole, and the output-results are not as expected.
NOTE: Other paths with holes, DO, work (see comments in code).
--- CODE ---
import './style.css'; // Import stylesheets
import {
findMats,
getPathsFromStr,
Mat,
traverseEdges,
toScaleAxis,
} from 'flo-mat';
const NS = 'http://www.w3.org/2000/svg'; // Svg namespace
/**
* Creates and returns an SVG DOM element.
* @param id The dom id to assign to the SVG element, e.g. 1 -> 'svg-1'
*/
function createSvg(id: number) {
let $e = document.createElementNS(NS, 'svg');
$e.setAttributeNS(null, 'id', 'svg' + id);
$e.setAttributeNS(null, 'style', 'width: 100%; display: inline-block');
$e.setAttributeNS(null, 'viewBox', '-1000 -5000 10000 20000');
return $e;
}
/**
* Returns an SVG path string of a line.
* @param ps The line endpoints.
*/
function getLinePathStr(ps: number[][]) {
let [[x0, y0], [x1, y1]] = ps;
return `M${x0} ${y0} L${x1} ${y1}`;
}
/**
* Returns an SVG path string of a quadratic bezier curve.
* @param ps The quadratic bezier control points.
*/
function getQuadBezierPathStr(ps: number[][]) {
let [[x0, y0], [x1, y1], [x2, y2]] = ps;
return `M${x0} ${y0} Q${x1} ${y1} ${x2} ${y2}`;
}
/**
* Returns an SVG path string of a cubic bezier curve.
* @param ps The cubic bezier control points.
*/
function getCubicBezierPathStr(ps: number[][]) {
let [[x0, y0], [x1, y1], [x2, y2], [x3, y3]] = ps;
return `M${x0} ${y0} C${x1} ${y1} ${x2} ${y2} ${x3} ${y3}`;
}
/**
* The SVG path string representing our shape.
*/
// THIS PATH DOES NOT APPEAR TO WORK WITH HOLES
const svgPathStr = `m 156.22344,294.17732 c 56.74809,0 73.7782,111.27897 73.7782,620.21251 0,508.93497 -17.03011,620.21347 -73.7782,620.21347 -56.747396,0 -79.464337,-111.2785 -78.278899,-620.21347 C 79.129384,405.45629 99.476044,294.17732 156.22344,294.17732 Z M 152.42498,0.56763972 c 126.66868,0 151.8074,163.95935028 151.8074,913.83244028 0,749.87302 -41.69863,913.83232 -151.8074,913.83232 C 42.316897,1828.2324 -1.128782,1664.2731 0.6181635,914.40008 2.3652082,164.52699 25.756989,0.56763972 152.42498,0.56763972 Z`;
// THIS PATH APPEARS TO WORK WITH HOLES
// const svgPathStr = 'M 2718 -1090 L 2912 -1090 L 2912 -1216 L 2718 -1216 L 2718 -1661 L 2230 -1661 L 2230 -1920 L 2860 -1920 L 2860 -2049 L 2239 -2049 C 2334 -2179 2442 -2347 2528 -2491 L 2390 -2557 C 2316 -2408 2187 -2192 2086 -2049 L 1136 -2049 L 1136 -1920 L 1585 -1920 L 1585 -1661 L 1182 -1661 L 1182 -1536 L 1585 -1536 L 1585 -1216 L 1093 -1216 L 1093 -1090 L 1585 -1090 L 1585 -768 L 1167 -768 L 1167 -642 L 1529 -642 C 1391 -352 1164 -66 949 80 C 980 105 1026 155 1050 189 C 1241 43 1443 -215 1585 -489 L 1585 270 L 1720 270 L 1720 -642 L 2095 -642 L 2095 267 L 2230 267 L 2230 -505 C 2390 -237 2614 27 2808 174 C 2832 136 2875 90 2909 62 C 2691 -78 2442 -365 2285 -642 L 2718 -642 L 2718 -1090 M 2230 -768 L 2230 -1090 L 2589 -1090 L 2589 -768 L 2230 -768 M 1720 -768 L 1720 -1090 L 2095 -1090 L 2095 -768 L 1720 -768 M 1720 -1536 L 2095 -1536 L 2095 -1216 L 1720 -1216 L 1720 -1536 M 1720 -1920 L 2095 -1920 L 2095 -1661 L 1720 -1661 L 1720 -1920 M 2589 -1536 L 2589 -1216 L 2230 -1216 L 2230 -1536 L 2589 -1536'
/**
* Adds a path to the given SVG element and give it a shape-path class.
*/
function setSvgShapePath($svg: SVGSVGElement, pathStr: string) {
let $path = document.createElementNS(NS, 'path'); // Create SVG path elem.
$path.setAttribute('class', 'shape-path');
$svg.appendChild($path); // Add the path element to the SVG.
document.body.appendChild($svg); // Add the SVG to the document body.
$path.setAttribute('d', svgPathStr);
}
function main() {
// Create and add and SVG element to our HTML page.
let $svg = createSvg(1); // Create SVG element.
setSvgShapePath($svg, svgPathStr);
// Get loops (representing the shape) from some SVG path.
let bezierLoops = getPathsFromStr(svgPathStr);
// We could also just give an array of linear, quadratic or cubic beziers as
// below (all lines in this case). Note that in the below case there is only
// one array of beziers (forming a single loop shape).
/*
bezierLoops = [
[
[[50.000, 95.000],[92.797, 63.905]],
[[92.797, 63.905],[76.450, 13.594]],
[[76.450, 13.594],[23.549, 13.594]],
[[23.549, 13.594],[7.202, 63.90]],
[[7.202, 63.900],[50.000, 95.000]]
]
];
*/
// Get MATs from the loops.
let mats = findMats(bezierLoops, 5);
// Draw the MATs.
drawMats(mats, $svg, 'mat');
// Get the SAT (at scale 1.5) of the MATs (of which there is only 1)
let sats = mats.map((mat) => toScaleAxis(mat, 1.5));
drawMats(sats, $svg, 'sat');
}
/**
* Returns a function that draws an array of MAT curves on an SVG element.
* @param mats An array of MATs to draw.
* @param svg The SVG element on which to draw.
* @param type The type of MAT to draw. This simply affects the class on the
* path element.
*/
function drawMats(mats: Mat[], svg: SVGSVGElement, type: 'mat' | 'sat') {
mats.forEach(f);
/**
* Draws a MAT curve on an SVG element.
*/
function f(mat: Mat) {
let cpNode = mat.cpNode;
if (!cpNode) {
return;
}
let fs = [, , getLinePathStr, getQuadBezierPathStr, getCubicBezierPathStr];
traverseEdges(cpNode, function (cpNode) {
if (cpNode.isTerminating()) {
return;
}
let bezier = cpNode.matCurveToNextVertex;
if (!bezier) {
return;
}
let $path = document.createElementNS(NS, 'path');
$path.setAttributeNS(null, 'd', fs[bezier.length](bezier));
$path.setAttributeNS(null, 'class', type);
svg.appendChild($path);
});
}
}
main();
--- CODE END ---
Thank you for spending the time to create this library.
Any advisement would be appreciated.
Floris, I created other paths with holes, and they seem to work as expected.
For example, this curvy number 8:
M 331.91211 130.57812 C 248.32255 131.45338 165.32755 247.37341 153.43164 321.37891 C 141.34691 396.55908 227.64135 426.26051 236.36914 495.54492 C 245.09693 564.82933 173.82788 653.14046 192.82617 717.39844 C 211.82447 781.65642 253.56947 837.53453 315.1582 843.87695 C 376.74694 850.21938 453.33741 803.91477 476.88281 733.98633 C 500.42821 664.05789 392.00992 574.65108 398.09375 499.69141 C 404.17758 424.73173 501.30846 393.87333 493.4707 319.30469 C 485.63295 244.73603 420.81013 133.48617 335.89258 130.625 C 334.56574 130.58029 333.23893 130.56424 331.91211 130.57812 z M 326.35938 248.45508 C 328.14294 248.43097 329.93854 248.54507 331.74414 248.80859 C 360.63368 253.02492 375.06676 292.92523 373.21289 325.52539 C 371.35902 358.12555 347.49977 418.87155 311.01172 414.68164 C 274.52366 410.49173 262.85339 343.60285 269.54297 311.01172 C 275.81445 280.45753 299.60573 248.81667 326.35938 248.45508 z M 325.52539 578.48047 C 366.8117 578.11416 394.48018 655.38646 389.80078 694.5918 C 385.12139 733.79714 353.53159 775.8076 319.30469 771.30664 C 285.07778 766.80568 271.50509 716.40384 271.61719 680.07812 C 271.7293 643.75241 284.23908 578.8467 325.52539 578.48047 z
So, maybe you can provide some clarity about what's the substantive difference between the non-working number-zero, and the working number eight(?).
Thanks again.
And, final comment, a working number zero path:
M 576.09375 2.1445312 C 97.348593 2.1445313 8.938941 621.83403 2.3359375 3456 C -4.2666911 6290.1657 159.93723 6909.8555 576.09375 6909.8555 C 992.25287 6909.8555 1149.8555 6290.1657 1149.8555 3456 C 1149.8555 621.83403 1054.8415 2.1445312 576.09375 2.1445312 z M 590.45117 1111.8516 C 804.93214 1111.8516 869.29687 1532.4327 869.29688 3455.9609 C 869.29688 5379.4947 804.93214 5800.0762 590.45117 5800.0762 C 375.97282 5800.0762 290.11447 5379.4947 294.59375 3455.9609 C 299.07302 1532.4327 375.97282 1111.8516 590.45117 1111.8516 z
So, what's the difference?
Hi Matthew. Thanks for the feedback. I'll check it out and get back to you.
It turns out the difference is that in the non working version (that I modified a bit to use absolute coordinates so as to make more sense in my own mind):
m 156.22344,294.17732
C 212.97153,294.17732,230.00164,405.45629,230.00164,914.38983
C 230.00164,1423.3247999999999,212.97153,1534.6033,156.22344,1534.6033
C 99.476044,1534.6033,76.75910300000001,1423.3248,77.94454100000002,914.38983
C 79.129384,405.45629 99.476044,294.17732 156.22344,294.17732
Z
M 152.42498,0.56763972
C 279.09366,0.56763972 304.23238,164.52698999999998 304.23238,914.40008
C 304.23238,1664.2730999999999,262.53375,1828.2323999999999,152.42497999999998,1828.2323999999999
C 42.316897,1828.2324 -1.128782,1664.2731 0.6181635,914.40008
C 2.3652082,164.52699 25.756989,0.56763972 152.42498,0.56763972
Z
both 'loops' (the outer and the inner) have the same orientation
If you switch the orientation of for e.g. the inner curve you get:
m 156.22344,294.17732
C 212.97153,294.17732,230.00164,405.45629,230.00164,914.38983
C 230.00164,1423.3247999999999,212.97153,1534.6033,156.22344,1534.6033
C 99.476044,1534.6033,76.75910300000001,1423.3248,77.94454100000002,914.38983
C 79.129384,405.45629 99.476044,294.17732 156.22344,294.17732
Z
M 152.42498,0.56763972
C 25.756989,0.56763972 2.3652082,164.52699 0.6181635,914.40008
C -1.128782,1664.2731 42.316897,1828.2324 152.42497999999998,1828.2323999999999
C 262.53375,1828.2323999999999 304.23238,1664.2730999999999 304.23238,914.40008
C 304.23238,164.52698999999998 279.09366,0.56763972 152.42498,0.56763972
and it works.
This is due to the nonzero orientation rule being used (as opposed to the even-odd rule) which is the default for SVG and most (if not all) font formats in general.
Does that resolve it?
Floris, yes, thank you, for the clarity. That does resolve it.
Before this closes, do you happen to have any insight into the best way to get all 2-prong samples? I noticed it works quite well on your MAT-demo site, but I can't seem to sort out exactly where the information is stored (debug object?).
In any case, thank you.
Apologies for the delay. It was quite a busy few days for me 😳.
The documentation is quite complex so it takes some time to get used to navigating the internals.
There are basically two ways.
Yes, one way is through the debug info as you mentioned. I will not go into details but you could check the source code for some insight.
The second (recommended) way to get all two prong samples would be by traversing the MAT tree. However, there is a convenience method that could also be used called getAllOnLoop. This is probably best explained by an example.
// The basic strategy to get all the maximal circles will be to go around
// the shape and look at each contact point in turn.
const bezierLoops = getPathsFromStr(pathStr);
const mats = findMats(bezierLoops);
let count = 0; // Let's count the number of 2-prongs
// Since there are usually 2 (or more) 'contact points' per maximal
// circle we will set up a hash in order to not count the maximal
// circles twice.
const cpHash = new Set<CpNode>();
for (const mat of mats) { // For each MAT generated by the shape
// Get all the contact points of the current MAT
const cpNodes = mat.cpNode.getAllOnLoop();
for (const cpNode of cpNodes) {
if (cpNode.getRealProngCount() !== 2) {
continue; // It must be specifically a 2-prong
}
// Get all contact points of the maximal circle belonging to the
// current contact point (including the current contact point
// itself)
const cpNodesOnCircle = cpNode.getCpNodesOnCircle();
let circleAlreadySeen = false;
for (let cpNodeOnCircle of cpNodesOnCircle) {
if (cpHash.has(cpNodeOnCircle)) {
circleAlreadySeen = true;
} else {
cpHash.add(cpNodeOnCircle);
}
}
if (circleAlreadySeen) {
continue; // don't count the circle twice if already seen
}
// Some info about the 2-prong that may be of interest:
cpNode.cp.circle.center // medial axis circle center
cpNode.cp.circle.radius // medial axis circle radius
cpNode.cp.pointOnShape.curve.ps; // bezier curve control points
cpNode.cp.pointOnShape.t; // `t` parameter value where the contact point occurs
cpNode.cp.pointOnShape.p; // contact point coordinates
cpNode.isHoleClosing // is it hole-closing?
cpNode.isSharp() // is it a sharp corner
// etc, etc.
// drawCpNode(g, cpNode); // draw the contact point
count++;
}
}
console.log(`Number of 2-prongs: ${count}`);Hope that helps!