Ok, een voorstel, maar weet dat ik op mijn beurt bitter weinig van programmeren weet :
Mag ik om te beginnen aannemen dat je je punten "kent". Ik bedoel weet jij als je in wijzerzin je punten afloopt welke eerst komen in je n-hoek?
Ik neem aan in wat nu volgt van wel.
Nummer je hoekpunten
\(p_1\)
tot en met
\(p_n\)
Nu werken we recursief, een punt zit "daarin" als ie in de (n-1)-hoek p_1 tot en met
\(p_{n-1} \)
ligt, of in de driehoek met hoekpunten
\(p_1 p_{n-1}\)
en
\(p_{n}\)
Uiteindelijk komt het dus neer op bepalen of een punt in een driehoek ligt. Hoe doe je dat? Laat (a,b) (c,d) en (e,f) de drie coördinaten zijn.
Ga nu na of :
\(e(d-b)+f(c-a)+(a d-bc)\)
hetzelfde teken als
\( x(d-b)+y(c-a)+(a d- b c)\)
heeft
\(c (f-b)+d (e-a)+(a f -b e)\)
hetzelfde teken als
\(x (f -b) +y(e-a) +(a f - b e) \)
heeft
\(a(f- d)+b(e-c)+(c f-d e )\)
hetzelfde teken als
\( x(f-d)+y(e-c)+(c f- d e )\)
heeft
Als alledrie de voorwaarden vervuld zijn, ligt het punt in de driehoek.
Zou moeten werken.
Er is trouwens wel een handige truc om de punten te genereren in de "convexe omhullende", namelijk al die barycentrische combinaties van de gegeven punten met positieve gewichten.
