On esimerkiksi GeoJSON-muodssa olevan polygoni, jonka sisäpuolelta halutaan satunnainen piste.
Saako pisteen arvottua suoraan jollain kaavalla, vai pitääkö arpoa monikulmion "ympärillä" olevasta neliöstä, ja testata onko piste monikulmion sisällä?
Satunnainen koordinaatti monikulmion sisäpuolelta
Anonyymi
13
114
Vastaukset
En keksi mitään ihan helppoa menetelmää, mutta tämä tulee ensimmäisenä mieleen:
1) jaa monikulmio kolmioiksi jollain menetelmällä
katso esim. https://en.wikipedia.org/wiki/Polygon_triangulation
2) valitse satunnainen kolmio painotettuna kolmioiden pinta-aloilla
3) valitse satunnainen piste valitun kolmion sisältä
Tämän voi tehdä vaikka niin että peilaa kolmion suunnikkaaksi ja valitsee satunnaisen pisteen suunnikkaan sisältä.- Anonyymi
Tuota kolmioratkaisua pähkäilin vähän aikaa itsekin, mutta ajattelin menevän liian monimutkaiseksi pilkkomisineen. Täytyy vielä pureskella, jos saisi aikaan "tyylikkään" ratkaisun.
- Anonyymi
Löytyi tuollainen valmis palikka earcut-menetelmään.
https://github.com/mapbox/earcut
var triangles = earcut([10,0, 0,50, 60,60, 70,10]); // returns [1,0,3, 3,2,1]
Pitääköhän tuo paluuarvo tulkita siten, että lukuarvo on indeksi alkuperäiseen kärkipistetaulukkoon?
Eli olisi kolmiot 0,50 - 10,0 - 70,10 ja 70,10 - 60,60 - 0,50. - Anonyymi
Sen verran nyt edistynyt, että saan monikulmion pilkottua kolmioihin, ja laskettua niille pinta-alan ja suhteellisen pinta-alan yhteispinta-alasta prosentteina. Tosin tuota prosenttitietoa ei välttämättä edes tarvita.
Seuraavaksi kehiteltävä tuo satunnaisen kolmion valinta. Teen sen ehkä niin, että järjestän kolmiot ensin suurimmasta pienimpään. Satunnaisluku valitaan väliltä 0 ja yhteispinta-ala. Sitten aletaan vertailemaan ja ynnäilemään jne. Jos luku on pienempi tai yhtä suuri kuin ensimmäinen (suurin) kolmio, niin valitaan se. Jos isompi, niin ynnätään ensimmäisen ja toisen pinta-ala Jos luku on pienempi tai yhtä suuri, niin valitaan toinen kolmio. Jne. - Anonyymi
Näyttäisi noilla ohjeillasi toimivan kohtuu hyvin. Nyt on eka versio tehty, ja koearvottu osumia monikulmioon.
https://ibb.co/JH4ML8p - Anonyymi
Anonyymi kirjoitti:
Näyttäisi noilla ohjeillasi toimivan kohtuu hyvin. Nyt on eka versio tehty, ja koearvottu osumia monikulmioon.
https://ibb.co/JH4ML8pKolmion valinnan tekevää arvontaa pitää vielä viilata. Tein miljardi arvontaa ja jakautuivat näin:
[ 433496725, 433483913, 133019362, 0, 0 ]
Tuossa on pinta-alaltaan suurin ensin ja pienin viimeisenä. Jostain syystä kahteen pienimpään kolmioon ei tule lainkaan osumia. Pinta-alojen suhteet menee tässä tapauksessa näin:
[ 43.35 %, 24.52 %, 24.14 %, 4.08 %, 3.91 % ] - Anonyymi
Anonyymi kirjoitti:
Kolmion valinnan tekevää arvontaa pitää vielä viilata. Tein miljardi arvontaa ja jakautuivat näin:
[ 433496725, 433483913, 133019362, 0, 0 ]
Tuossa on pinta-alaltaan suurin ensin ja pienin viimeisenä. Jostain syystä kahteen pienimpään kolmioon ei tule lainkaan osumia. Pinta-alojen suhteet menee tässä tapauksessa näin:
[ 43.35 %, 24.52 %, 24.14 %, 4.08 %, 3.91 % ]Logiikkavirhe löytyi. Summasin vahingossa saman indeksin pinta-alan kahdesti, kun piti summata aina seuraava. Satatuhatta arvontaa jakautui nyt:
[ 42961, 24790, 24193, 4039, 4017 ] - Anonyymi
Anonyymi kirjoitti:
Logiikkavirhe löytyi. Summasin vahingossa saman indeksin pinta-alan kahdesti, kun piti summata aina seuraava. Satatuhatta arvontaa jakautui nyt:
[ 42961, 24790, 24193, 4039, 4017 ]Nyt arpoo jo melko tasaisesti.
Tampere: https://ibb.co/gm7FsGD
Suomi: https://ibb.co/QNzTvV4 - Anonyymi
Anonyymi kirjoitti:
Nyt arpoo jo melko tasaisesti.
Tampere: https://ibb.co/gm7FsGD
Suomi: https://ibb.co/QNzTvV4Suomi-karttaa kun katsoo, niin ei välttämättä tunnu tuo earcut-menetelmä kaikkein järkevimmältä tavalta pilkkoa monikulmiota kolmioihin. Tekee aika paljon ohuita ja pitkulaisia kolmioita.
- Anonyymi
Kiitos muuten tuosta logiikan kertomisesta! Nopeutti tosi paljon tämän ratkaisemista. En vielä aamupäivällä uskonut saavani tehtyä tätä ilman hukka-arvontoja.
- Anonyymi
Anonyymi kirjoitti:
Sen verran nyt edistynyt, että saan monikulmion pilkottua kolmioihin, ja laskettua niille pinta-alan ja suhteellisen pinta-alan yhteispinta-alasta prosentteina. Tosin tuota prosenttitietoa ei välttämättä edes tarvita.
Seuraavaksi kehiteltävä tuo satunnaisen kolmion valinta. Teen sen ehkä niin, että järjestän kolmiot ensin suurimmasta pienimpään. Satunnaisluku valitaan väliltä 0 ja yhteispinta-ala. Sitten aletaan vertailemaan ja ynnäilemään jne. Jos luku on pienempi tai yhtä suuri kuin ensimmäinen (suurin) kolmio, niin valitaan se. Jos isompi, niin ynnätään ensimmäisen ja toisen pinta-ala Jos luku on pienempi tai yhtä suuri, niin valitaan toinen kolmio. Jne.https://en.wikipedia.org/wiki/Barycentric_coordinate_system
Kolmioiden muodostamisen jälkeen siitä voi valita satunnaispisteen myös baryosentrisillä koordinaateilla. Silloin valittaisiin kolme koordinaattia eli satunnaislukua (p,q, r), ja nopeutetaan laskia valitsemalla että niiden summa on 1. Piste on aina kolmion sisällä, kun kaikki koordinaatit ovat lisäksi positiivisia. Baryosentriset koordinaatit muuttuvat karteesisiksi, kun tiedetään kolmion kärjet A,B ja C
X = p * A q * B r * C
Eli vaikket tunne käsitettä näistä koordinaateista, tällainen yhtälö antaa aina pisteen kolmion sisältä, jos p q r = 1 ja, p ,q ,r > 0 .
- Anonyymi
Kannattaa aloittaa miettimällä, miten todellisen matemaattisen satunnaisuuden saa aikaan. Ei riitä, että kuvittelee ja toivoo jonkun olevan satunnaista.
Sitten pitää määritellä vaadittu tarkkuus ja nopeus. Jos tuota ei pysty tekemään, ei kannata jatkaa. Tärkein vaihe. Tietokoneet tekevät hommia tyhmällä tavalla erittäin nopeasti ja muistia riittää lähes rajattomasti.
Jos piirrät monikulmiosi millimetripaperille (tai tietokoneella rasteriin) ja numeroit jokaisen kokonaisen ja yli puolikkaan ruudun, voit päästä aika lähelle satunnaisuutta. Mulla tavoilla loputtomat ohjelmavirheet sotkevat kaiken. Helpot erikoistapaukset ovat tietysti helppoja miten vain. Vaikeita tapauksia ei pysty aina edes kuvittelamaan eikä oikeellisuutta pysty helposti varmistamaan.- Anonyymi
Minua kiinnosti lähinnä ratkaista pulma. En tosin käyttänyt JavaScriptin omaa satunnaisfunktiota, vaan lisäkirjastoa https://www.npmjs.com/package/random-js
Muistia ei ole muuten läheskään rajattomasti. Huomasin sen ajaessani miljardin satunnaispaikan testiä. Se lisäsi jokaisen paikan koordinaatit taulukkoon, kuten varsinaisessa sovelluksessa pitääkin, ja muistihan siinä loppui. Piti kommentoida kyseinen rivi pois, koska tarkoitus oli vain laskea kuinka monta arvontaa osui viidelle eri vaihtoehdolle.
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Purran tuhoja tuskin saadaan koskaan korjatuksikaan
Purra on aiheuttanut Suomen taloudelle karmaisevat tuhot. Sen lisäksi Purra on ajanut myös suuren osan Suomen kansasta k17510704Marinin tuhojen korjaaminen kestää kahdeksan vuotta
Nyt on vasta neljännes mennyt ja ensimmäiset korjausliikkeet saatu liikkeelle. Innokkaimmat olivat odottaneet että jo t907525Aamun Riikka: työttömyydessä lähestytään viime laman synkintä vaihetta
Nopeasti mentiiin upean Marinin hallituksen ennätystyöllisyydestä toiseen ääripäähän, kohti Suomen historian kurjimpia t297379Se oli Orpo joka rynni Eagle S -alukselle
Vastoin kaikkia kansainvälisen merenkäynnin sääntöjä. Kunpa olisi ollut purjehtija Harkimo Suomen johdossa silloin. ht37376Demarikultin uhri kertoo
Demarikultin uhri kertoo: “En saanut mennä edes suihkuun ilman lupaa” – Seksuaalisen hyväksikäytön uhri kertoo vuosistaa885753Miksi vasemmistolaiset eivät omista yhtään firmaa?
Vasemmistolaiset eivät omista yhtään firmaa joka työllistäisi ihmisiä. Miksi? No siksi, että jos vasemmistolainen perus525228Sanna valittiin Euroopan huonoimmaksi pääministeriksi
Sannan kaudella Suomi oli ainut maa missä bkt laski. Kannattaa huomata, että luvut valitsi Sannan huonoimmaksi. Ihmiset314976Giorgia Meloni vs Riikka Purra
Kyllä Italian pääministeri on kauniimpi ja seksikkäämpi, kuin Suomen valtiovarainministeri Riikka Purra. Mitä jotkut näk124801Suomen velka kasvoi ennätysvauhtia - Mäkynen repostelee
– Velka kasvoi eniten tilaston historiassa, Mäkynen kirjoittaa. – Vuoden 2025 toisella neljänneksellä selvästi eniten k32142Ei muuta kun kylärinkiä ajamaan!!!
Huomenta! Tuossa ku kylän pinnassa asunu koko iän, nii viime vuosina nii harmittanu ku viikonloppusin niin hiljasta, sil361583