6 svar · 350 visningar · startad av spango
OK. Anta att jag har en rektangel vars hörn finns på (5,0), (0,5) (10,5) och (10,10). Hur kan jag då avgöra om en punkt finns inom denna rektangel? (Se bildexempel om ni är för korkade att haja ;) Hur avgör jag programmatiskt att de gröna punkterna finns i rektangeln och de röda inte gör det?)
Tro om denna länk kan hjälpa dig något.
Endera jmfr du koordinaterna rakt av som tuplar eller så definierar du rektangeln som en region med inbyggd funktionalitet för koordinatjämförelse (vilket iofs blir att jämföra tuplar, men på ett snyggare sätt).
Engine^ » Been there, done that, bought the t-shirt... har inte kollat igenom alla länkar men jag tror inte att svaret finns där.
PeW » Hm, jag hänger inte med helt, men jag tar det som att det inte finns någon "snygg" formel (=konstant tid) för att avgöra om en punkt ligger i en rektangel med godtycklig orientering? Så man får kolla punkt för punkt i stället (ev. listigt beskuret)?
Men du har ju tuplar som definierar koordinaterna i hörnen på rektangeln och du har tuplar som definierar punkter. Så du behöver knappast kolla alla koordinater i rektangeln (vilket suger cpu om rektangeln är stor), utan det bör räcka att kolla mot de intervall som hörn mot hörn definierar. Dvs:
- Är punkten ovan för rektangelns övre linje (hörn->hörn)?
- Är punkten under rektangelns nedre linje (hörn->hörn)?
...o.s.v
PeW » Hm, jag hänger inte med helt, men jag tar det som att det inte finns någon "snygg" formel (=konstant tid) för att avgöra om en punkt ligger i en rektangel med godtycklig orientering? Så man får kolla punkt för punkt i stället (ev. listigt beskuret)?
Nja. Det beror på vilken abstraktionsnivå du menar. Till en del högnivåspråk som exempelvis haskell, tcl/tk m.fl finns det grafikrutiner som inkluderar en enkelhet i form av regioner och shapes som ger detta. Men i botten är det ju ungefär som jag ovan skrev.
OK... hm. Ska försöka smälta det här lite (all min C-matte har runnit rakt ut ur skallen). Återkommer med en statusrapport...
Jaha... när man tittar bort har naturligtvis kollegan löst det hela genom att skita i att göra en snygg lösning och kollar bara bounding boxen, vilket är avsevärt enklare och ger en himla massa false positives vilket i vårt fall är odelat positivt :)
