Barycentric triangulation: valt punt P in driehoek ABC?

[drm]

Ik ben momenteel bezig met HTML5 canvas en hierin teken ik in in de meest basale vorm vakjes (rectangles) die interactief zijn (mouseovers + clickable). Aangezien het niet echt over canvas specifieke dingen gaat (da's immers alleen maar een manier om het te renderen), leek het me wijsheid om het hier te plaatsen.

Aangezien de vakjes gedraaid kunnen zijn, heb ik niet voldoende aan een simpele bounding box check, dus ben ik op onderzoek uitgegaan naar hoe je vast kunt stellen of een punt in een willekeurige polygoon voor kan komen. Ik kwam er al snel op uit dat de meest efficiente manier is om te werken met een Barycentric coordinatenstelsel nadat je je polygoon in driehoeken hebt verdeeld. Ik snap de wiskunde erachter nog niet helemaal, maar dat gaat vast nog wel komen... Wie weet door enige uitleg hier

Ik heb in principe wel een werkend beginnetje kunnen maken, en bij wijze van proof of concept wil ik kunnen detecteren of de mouseover een vierkantje oplicht. Een vierkant (of rechthoek) ABCD bestaat immers uit twee driehoeken, ABD en BCD, dus als ik weet of een punt in 1 van die driehoeken zit, dan zit het punt ook in de rechthoek.

Het geval wil echter dat op de diagonaal (BD) een afrondingsfout o.i.d. lijkt op te treden. Ik had gehoopt er op deze manier mee weg te komen en op een later tijdstip nog eens uit te zoeken hoe het precies werkt, maar die vlieger gaat dus niet helemaal op: om het op te lossen moet ik nu wel echt begrijpen hoe het in elkaar steekt

Ik heb een fiddle gemaakt waar ik alle cruft (zoals optimalisaties) weggelaten heb en met vanilla JS het probleem geschetst wordt. Je ziet dat het algoritme (Triangle.contains) in principe redelijk goed werkt, maar bij het vierkant in het midden wordt het probleem duidelijk. Omdat de driehoeken niet overlappen, maar alleen maar aangrenzen, vallen er punten die het lijnstuk BD vormen (van linksonder naar rechtsboven) volgens deze methode in geen van de twee driehoeken. Het effect is dat als je muis op de diagonaal komt, het als een "mouseout" wordt gezien. Of dat alle punten van de diagonaal zijn heb ik nog niet uitgezocht, ook niet of daar een patroon in is te ontdekken, maar wellicht dat iemand met wat meer kennis van zaken daar sowieso al een verklaring voor kan geven...

http://jsfiddle.net/t5Nsb/2/

Ik vraag me af hoe ik er achter kan komen hoe dit is op te lossen, of dat ik misschien wel een hele andere richting op moet. Ik ben benieuwd of iemand hier mee kan helpen

PS: Een reeds bedachte oplossing om met een tweede canvas te werken en van dat canvas de kleuren uit te lezen van de muispositie en elk object aan een middels een unieke kleur te koppelen, maar helaas ondersteunt excanvas, de fallback voor IE <= 9, dat niet Je krijgt daar overigens ook weer een ander probleem bij, namelijk antialiasing

De twee belangrijkste links die ik ernaast gehouden heb zijn:
http://blogs.msdn.com/b/r...nt-in-triangle-tests.aspx
http://www.blackpawn.com/texts/pointinpoly/

[.oisyn]

Wil je het echt op de barycentric coordinate manier oplossen? Want er zijn namelijk veel makkelijkere manieren .

De simpelste manier om te testen of een punt P in een polygoon ligt is door de "winding order" van de driehoeken te bepalen die je maakt van twee aanliggende vertices van de polygoon en P. Als P erin ligt is de order van alle driehoeken gelijk (CW of CCW, afhankelijk van hoe je test).

Een andere mogelijkheid is het punt P te transformeren naar de local space van je rechthoek, waarna je uiteraard simpelweg een bounding rectangle test kunt doen.

[drm]

.oisyn:
Wil je het echt op de barycentric coordinate manier oplossen? Want er zijn namelijk veel makkelijkere manieren .

Neuh, maar dat was, niet gehinderd door enige kennis van zaken, waar ik na wat googlen op uitkwam

De simpelste manier om te testen of een punt P in een polygoon ligt is door de "winding order" van de driehoeken te bepalen die je maakt van twee aanliggende vertices van de polygoon en P. Als P erin ligt is de order van alle driehoeken gelijk (CW of CCW, afhankelijk van hoe je test).

Ik ga s ff op onderzoek uit, thanks

Een andere mogelijkheid is het punt P te transformeren naar de local space van je rechthoek, waarna je uiteraard simpelweg een bounding rectangle test kunt doen.

ja, daar heb ik ook aan gedacht maar dat maakt het wel lastiger om te optimaliseren omdat je die transformatie dan altijd voor elk object uit moet voeren, wat partioning bijv lastig of zelfs onmogelijk kan maken. En dat is wel iets om rekening mee te houden in dit geval

[drm]

Ben overigens niettemin nog steeds wel benieuwd of je een verklaring hebt voor het verschijnsel omschreven in mijn topicpost.

[MSalters]

Een afrondverschijnsel van je UV transformatie, gecombineerd met een niet-inclusieve check u+v<1 ipv <=1. En zoals .oisyn al zei: in UV space is je rechthoek gewoon (0,0),(0,1),(1,1),(1,0) dus dan ben je check op de diagonaal sowieso kwijt. Heb je natuurlijk nog steeds de vraag of je u<0 danwel u<=0 moet doen.

[Soultaker]

.oisyn schreef op maandag 30 december 2013 @ 20:40:
De simpelste manier om te testen of een punt P in een polygoon ligt is door de "winding order" van de driehoeken te bepalen die je maakt van twee aanliggende vertices van de polygoon en P. Als P erin ligt is de order van alle driehoeken gelijk (CW of CCW, afhankelijk van hoe je test).

Dit werkt alleen voor convexe polygonen (daar lijkt drm zich ook toe te beperken, in z'n voorbeeld althans, maar ik zeg het er maar even bij). Voor ingewikkeldere vormen geeft Wikipedia raad.

Een praktische oplossing voor het probleem is om gewoon de isPointInPath() methode van de rendering context zelf te gebruiken. Dat heeft als voordeel dat je je path op dezelfde manier opbouwt als wanneer je 'm rendert. Dat is dus ook makkelijk met debuggen (als je de paths die je test stroket/fillt zie je direct waar de klikbare gebieden zitten).

[.oisyn]

Soultaker schreef op maandag 30 december 2013 @ 22:19:
[...]

Dit werkt alleen voor convexe polygonen (daar lijkt drm zich ook toe te beperken, in z'n voorbeeld althans, maar ik zeg het er maar even bij). Voor ingewikkeldere vormen geeft Wikipedia raad.

Dat was wat ongenuanceerd van mij idd. Nevertheless kun je ook met concave polygonen een vergelijkbaar algoritme gebruiken, waarbij je de totale hoek meet als je langs de verts van de polygoon loopt. Ik meen mij te herinneren dat het letterlijk uitrekenen van de hoek niet eens nodig is, maar dat weet ik niet meer zeker.

[ Voor 9% gewijzigd door .oisyn op 30-12-2013 23:16 ]

[drm]

MSalters:
Een afrondverschijnsel van je UV transformatie, gecombineerd met een niet-inclusieve check u+v<1 ipv <=1.

Inderdaad de inclusive check lost het verschijnsel op: http://jsfiddle.net/t5Nsb/5/

---

Soultaker:
Een praktische oplossing voor het probleem is om gewoon de isPointInPath() methode van de rendering context zelf te gebruiken. Dat heeft als voordeel dat je je path op dezelfde manier opbouwt als wanneer je 'm rendert. Dat is dus ook makkelijk met debuggen (als je de paths die je test stroket/fillt zie je direct waar de klikbare gebieden zitten).

Ja, ik was alweer vergeten dat die ook nog bestond omdat die ook niet ondersteund wordt in excanvas

---

Het zullen inderdaad alleen convexe polygonen zijn, sterker nog, ik denk dat het niet verder zal gaan dan wellicht een vijfhoek, en mogelijk cirkels (maar da's uiteraard veel eenvoudiger), omdat het symbolen zijn.

Dank allen, dit gaat wel lukken.

[drm]

Ik heb het intussen helemaal werkend met zoom, pan en rotate controls, dus dat lijkt me een mooie afsluiter van 't jaar.

Voor het nageslacht nog even een linkje waar ik ook een hoop aan heb gehad: http://geomalgorithms.com/a03-_inclusion.html