Triangolazione
Descrizione del problema:Sia data una poligonale chiusa (convessa o concava) non intrecciata o bucata, individuiamo i segmenti sufficienti a dividere il poligono in triangoli senza aggiungere altri vertici.
In particolare possiamo facilmente constatare che per un poligono di n vertici, occorrono n-3 segmenti per generare n-2 triangoli.
I poligoni possono essere di due tipi:
_ convessi (i più semplici da trattare)
_ concavi
Il mio algoritmo potrebbe non essere il più efficiente ma certamente funziona ed è di semplice comprensione.
I passaggi sono, sostanzialmente, i seguenti:
1) viene presa ciascuna diagonale e sottoposta ad una serie di test che ne valutano l idoneità;
2) vengono riempiti due array, uno con le diagonali "buone" e uno con quelle "cattive";
3) l algoritmo si conclude non appena vengono individuate le n-3 diagonali necessarie.
4) eventuale rappresentazione grafica.
I controlli che una diagonale riceve, prima di essere ritenuta valida, sono i seguenti:
1) i vertici non devono risultare consecutivi (perchè sennò non è una diagonale ma un lato);
2) se una diagonale è già stata trattata (accettata o scartata) non viene presa di nuovo in considerazione;
3) si verifica che la diagonale non intersechi in alcun modo il perimetro (è quel che può succedere con i poligoni concavi);
4) si verifica che la diagonale non intersechi altre diagonali;
5) si verifica che la diagonale non congiunga due vertici passando per l esterno del poligono (anche questo succede solo con i poligoni concavi);
6) se tutti questi controlli vengono superati, la diagonale è dichiarata valida e inserita nell array delle "buone".
<html>
<title>Triangolazione</title>
</head>
<body style="background-color:#000; color:#ccc; font-family:Arial, sans-serif;">
<h1>TRIANGOLAZIONE</h1>
<h2>Disegnare il poligono cliccando sull area gialla e premere il bottone "triangulate"</h2>
<h3>Lo script non lavora con poligoni intrecciati o bucati</h3>
<div><button onclick="triangulate()">triangulate</button> <button onclick="window.location.reload()">clear</button></div><br>
<canvas id="canvas" width="800" height="800" style="border:1px solid #000; background-color:#333;">
Your browser does not support the HTML5 canvas tag.
</canvas>
<div id="text"></div>
<script>
var vert = [];
var good = [];
var bad = [];
var vertSize = 0;
var goodSize = 0;
var badSize = 0;
var str = "";
var canvas;
var ctx;
function init()
{
canvas = document.getElementById("canvas");
ctx = canvas.getContext("2d");
ctx.font = "20px Arial";
ctx.strokeStyle = "#ff0";
ctx.fillStyle = "#ff0";
}
function L(a)
{
return String.fromCharCode(65 + a);
}
function next(a)
{
if(a == vertSize - 1)
{
return 0;
}
else
{
return a + 1;
}
}
function abs(a)
{
if(a < 0)
{
return -a;
}
else
{
return a;
}
}
function min(a, b)
{
if(a < b)
{
return a;
}
else
{
return b;
}
}
function max(a, b)
{
if(a > b)
{
return a;
}
else
{
return b;
}
}
function checkPointInsideRectangle(px, py, ax, ay, bx, by)
{
var mx = min(ax, bx), Mx = max(ax, bx), my = min(ay, by), My = max(ay, by);
var w = (py >= my && py <= My), h = (px >= mx && px <= Mx);
if(ax == bx)
{
return w;
}
else if(ay == by)
{
return h;
}
else
{
return (w && h);
}
}
function checkIntersection(ax, ay, bx, by, cx, cy, dx, dy)
{
var px, py;
var dt = (ax - bx) * (cy - dy) - (ay - by) * (cx - dx);
if(dt == 0)
{
return false;
}
else
{
px = ((ax*by-ay*bx)*(cx-dx)-(ax-bx)*(cx*dy-cy*dx))/dt;
py = ((ax*by-ay*bx)*(cy-dy)-(ay-by)*(cx*dy-cy*dx))/dt;
return checkPointInsideRectangle(px,py,ax,ay,bx,by) && checkPointInsideRectangle(px,py,cx,cy,dx,dy);
}
}
function testAdjacency(a, b)
{
var h = abs(a - b);
if(h == 1 || h == vertSize - 1)
{
str += L(a) + L(b) + ": adjacent<br>";
return true;
}
else
{
return false;
}
}
function testBad(a, b)
{
var h = false;
var i = 0;
while(!h && i < badSize)
{
if((bad[i * 2] == a && bad[i * 2 + 1] == b) || (bad[i * 2] == b && bad[i * 2 + 1] == a))
{
str += L(a) + L(b) + ": already discarted<br>";
h = true;
}
i++;
}
return h;
}
function testGood(a, b)
{
var h = false;
var i = 0;
while(!h && i < goodSize)
{
if((good[i * 2] == a && good[i * 2 + 1] == b) || (good[i * 2] == b && good[i * 2 + 1] == a))
{
str += L(a) + L(b) + ": already recognized<br>";
h = true;
}
i++;
}
return h;
}
function testBorderIntersection(a, b)
{
var i = 0;
var h = false;
while(!h && i < vertSize)
{
var j = next(i);
if(a != i && a != j && b != i && b != j)
{
if(checkIntersection(vert[a * 2], vert[a * 2 + 1], vert[b * 2], vert[b * 2 + 1], vert[i * 2], vert[i * 2 + 1], vert[j * 2], vert[j * 2 + 1]))
{
bad[badSize * 2] = a;
bad[badSize * 2 + 1] = b;
badSize++;
str += L(a) + L(b) + ": border intersection " + L(i) + L(j) + "<br>";
h = true;
}
}
i++;
}
return h;
}
function testDiagonalIntersection(a, b)
{
var i = 0;
var h = false;
while(!h && i < goodSize)
{
var c = good[i * 2], d = good[i * 2 + 1];
if(a != c && a != d && b != c && b != d)
{
if(checkIntersection(vert[a * 2], vert[a * 2 + 1], vert[b * 2], vert[b * 2 + 1], vert[c * 2], vert[c * 2 + 1], vert[d * 2], vert[d * 2 + 1]))
{
str += L(a) + L(b) + ": diagonal intersection " + L(c) + L(d) + "<br>";
h = true;
}
}
i++;
}
return h;
}
function testConcavity(a, b)
{
var mx = (vert[a * 2] + vert[b * 2]) / 2, my = (vert[a * 2 + 1] + vert[b * 2 + 1]) / 2;
var h = 0;
var i;
for(i = 0; i < vertSize - 1; i++)
{
if(checkIntersection(mx, my, mx + 10000, my, vert[i * 2], vert[i * 2 + 1], vert[i * 2 + 2], vert[i * 2 + 3]))
{
h++;
}
}
if(checkIntersection(mx, my, mx + 10000, my, vert[i * 2], vert[i * 2 + 1], vert[0], vert[1]))
{
h++;
}
for(i = 0; i < vertSize; i++)
{
if(my == vert[i * 2 + 1])
{
h--;
}
}
if(h % 2 == 0)
{
bad[badSize * 2] = a;
bad[badSize * 2 + 1] = b;
badSize++;
str += L(a) + L(b) + ": concavity<br>";
return true;
}
else
{
return false;
}
}
function check(a, b)
{
if(!testAdjacency(a, b))
{
if(!testBad(a, b))
{
if(!testGood(a, b))
{
if(!testBorderIntersection(a, b))
{
if(!testDiagonalIntersection(a, b))
{
if(!testConcavity(a, b))
{
good[goodSize * 2] = a;
good[goodSize * 2 + 1] = b;
goodSize++;
str += L(a) + L(b) + ": ok<br>";
}
}
}
}
}
}
}
function draw1()
{
ctx.beginPath();
ctx.moveTo(vert[0], vert[1]);
ctx.fillText("A", vert[0], vert[1]);
for(var i = 1; i < vertSize; i++)
{
ctx.lineTo(vert[i * 2], vert[i * 2 + 1]);
ctx.fillText(L(i), vert[i * 2], vert[i * 2 + 1]);
}
ctx.lineTo(vert[0], vert[1]);
ctx.stroke();
}
function draw2()
{
ctx.beginPath();
for(var i = 0; i < goodSize; i++)
{
ctx.moveTo(vert[good[i * 2] * 2], vert[good[i * 2] * 2 + 1]);
ctx.lineTo(vert[good[i * 2 + 1] * 2], vert[good[i * 2 + 1] * 2 + 1]);
}
ctx.stroke();
}
function clr()
{
ctx.clearRect(0, 0, canvas.width, canvas.height);
}
function triangulate()
{
for(var j = 0; j < vertSize && goodSize < vertSize - 3; j++)
{
for(var k = 0; k < vertSize && goodSize < vertSize - 3; k++)
{
if(j != k)
{
check(j, k);
}
}
}
draw2();
document.getElementById("text").innerHTML = str;
}
function main()
{
clr();
canvas.addEventListener("click", function(event)
{
var x = event.pageX - canvas.offsetLeft, y = event.pageY - canvas.offsetTop;
vert.push(x,y);
vertSize++;
clr();
draw1();
});
}
init();
main();
</script>
</body>
</html>
