Keskustelu: Ohjelmointikysymykset: C: Monikulmion keskipiste

tällainen geometrian kysymys.
2d tasossa on monikulmio, miten lasken sen keskipisteen?

ajattelin näin että rajaan reunapisteistä suorakaiteen
ja puolitan sitten sivujen pituudet, menikö oikein?

vedät jokaisesta kulmasta viivan vastakkaiseen kulmaan niin viivojen leikkauspisteen pitäisi olla keskipiste.

Sanokaa joku jos olen väärässä.

Edit: mitään laskukaavaa en kyllä tiedä.

njoo, tarkennetaan tätä että kyseessä ei ole mikään säännöllinen monikulmio , vaan 3d meshi, jonka haluan keskittää

Tuo tapa on aikas vaikea ja hidas tapa, eikä edes toimi kaikissa tapauksissa.
Miten olisi tämmäinen koodi: (javalle)

public Point getMedianPoint(final Polygon p)
{
   final int numVerts = p.npoints;
   int cx = 0, cy = 0;

   for(int i = 0;i < numVerts;i++)
   {
      cx += p.xpoints[i];
      cy += p.ypoints[i];
   }
   cx/=numVerts;
   cy/=numVerts;

   return new Point(cx,cy);
}

En nyt ehtynyt katso tarkimmin sitä, mutta kokeile. Tuo on kylläkin vain mediaani piste.

Eikös se silti hae sen keskipisteen oli sitten minkämuotoinen tahansa? Mutta joo...

tuo näyttää ihan keskiarvon laskulta.
pitää varmaan väsätä joku testiohjelma ihan tätä ongelmaa varten
siinä menee taas yksi ilta..

Huomioi että tuo on MEDIAANIPISTE, ei keskipiste.
Tästä kuvasta huomaat eron: http://img228.imageshack.us/my.php?image­=mediaanipisteed0.png
Vihreä piste on mediaanipiste ja sininen keskipiste.

Yksi tapa laskea keskipiste voisi olla laskea suorakulmion keskipiste, niin että suorakulmio olisi juuri polygonin kokoinen. En ole aivan varma onko tämä juurikin se tarkka keskipiste kaikissa tapauksissa.

Point getCenterPoint(Polygon p)
{
   int xMax, xMin, yMax, yMin;
   // Haetaan suurimmat ja pienimmät x:n ja y:n arvot ja lasketaan niiden keskiarvo

   for(int i = 0;i < p.npoints;i++)
   {
      xMax = MAX(xMax, p.xpoints[i])
      xMin = MIN(xMin, p.xpoints[i])
      yMax = MAX(yMax, p.ypoints[i])
      yMin = MIN(yMin, p.ypoints[i])
   }

   return new Point((xMax+xMin)/2, (yMax+yMin)/2);
}

edit: neliö > suorakulmio

Eikös tämä onnistu yksinkertaisesti laskemalla kaikkien pisteiden keskiarvo? Joskus kehittelin tällaisia pikkujuttuja, ja paperilla testaillessa se vaikutti toimivan aivan niin.

kray, meinaatkos siis että

monikulmio ABCDEF jossa
{ A(2,3), B(3,2), C(3,4), D(-6,-5), E(1,1), F(0,0) }

keskipisteen koordinaatit olisivat:
x=[2+3+3+(-6)+1+0]/6 = 3/6 && y=[3+2+4+(-5)+1+0]/6 = 5/6

näinkö siis tarkoitit vai ymmärsinkö väärin?

noniiin,
tesmin tuon mediaanin se näytti olevan suht keskellä, varmaksi en voi mennä vannomaan.
petrinm kertoi neliöstä,
tuossa alkuperäisessä ajatuksessani puhuin suorakaiteesta jonka sivut puolitetaan
ja tuo petrimin koodi tekee juuri sen..( huomaa suorakaide ei neliö )

mutta vielä on auki onko se the oikea keskipiste?

Tason alueilla ei normaalisti ole mitään yleispätevää keskipistettä kuten esimerkiksi ympyröillä. Yrität varmaankin löytää kuvion painopisteen

(x₀, y₀) = (Integraali alueen yli (x,y) dA) / (Integraali alueen yli dA),

jota et siis löydä millään yllä esitetyistä kaavoista. Painopisteen voi käytännössä laskea esimerkiksi jakamalla monikulmion kolmoihin ja laskemalla näiden painopisteiden keskiarvon painotettuna kolmoiden pinta-alalla.

1 vielä mainitsematon tapa on myös laskea suurimmat ja pienimmät x,y arvot ja laskea niiden keskiarvo:

keskiX = (suurinX+pieninX)/2
keskiY = (suurinY+pieninY)/2

Edit: eikun tämä olikin jo petrinm kommentissa.

miten olisi jos rajaisi mahdollisimman pienen ympyrän,
josta katsoisi keskipisteen?

Sama tulos kuin suorakulmion kanssa, mutta paljon pitempien laskujen kautta.

petrinm kirjoitti:

Sama tulos kuin suorakulmion kanssa, mutta paljon pitempien laskujen kautta.

Ei, ei tule sama. Tämän voi todeta vaikkapa tasasivuisella kolmiolla. Mutta ei tuosta olennaisesti parempi tule.

Tee aivan oman mielesi mukaan, turha sitä on täällä kysellä. Oikean vastauksen sait jo os:lta: integroi.

Metabolix kirjoitti:

Oikean vastauksen sait jo os:lta: integroi.

Minun on kyllä vaikea kuvitella miten tuon integroinnin saisi käytännössä tehtyä helpommin kuin kolmioihin hajottamisen, jonka os myös ehdotti (joka sekään ei ole maailman yksinkertaisin juttu).

Itse en ehkä tekisi kuitenkaan sinänsä jakamalla kolmioihin vaan yksinkertaistamalla kulma kerrallaan ja laskemalla näin muodostuvia yli ja ali jääviä kolmioita.

Samaa integrointia se niinkin on, siinä vain helpotetaan laskuja hyödyntämällä valmista tietoa kolmion keskipisteestä. Integraalihan on oikeastaan vain summa äärettömästä joukosta, ja kolmioiden avulla voidaan korvata summasta kunkin kolmion pisteet ja pisteiden peittämät alat suoraan välituloksella, kolmion keskipisteellä ja kolmion alalla. (Kukapa sitä suoraa y=x lähtisi ensi töikseen "oikeasti" integroimaan, kun määrätyn integraalin saa suoraan pinta-alana?)

Vielä jos on tosiaan kyse 3D-meshistä, niin sehän ei keskity vain tuolla, että keskitetään sen jokin poikkileikkaus tai projektio yhdessä (tai edes kolmessa) tasossa. Siinä tämän integraalilaskennallisen kolmion korvaa tetraedri, ja mallin jakaminen tetraedreiksi tapahtuu aivan vastaavalla algoritmilla kuin polygonin jakaminen kolmioiksi.

Jos on jo olemassa hyvät algoritmit tarkistukseen, onko tietty piste mallin sisällä tai leikkaako tietty jana mallin, niin yksi approksimaatiokeino on käydä läpi tietyt pisteet (säännöllisesti tai arpomalla) mallia ympäröivästä laatikosta ja laskea sisään osuneiden pisteiden keskiarvo. Pienellä pistemäärällä tämä kuitenkin on epätarkkaa ja suurella hidasta.

Metabolix kirjoitti:

Samaa integrointia se niinkin on, siinä vain helpotetaan laskuja hyödyntämällä valmista tietoa kolmion keskipisteestä.

Tietenkin lopputulos on sama riippumatta siitä mitä (toimivaa) menetelmää käytetään.

Itse tulkitsin kuitenkin tuon integroinnin terminä tarkoittamaan sitä, että tehdään esim X:n osalta kuvion korkeutta x:n funktiona kuvaava funktio joka sitten integroidaan. Kommentillani tarkoitin, että mielestäni tällainen menetelmä olisi hankalahko.

Ja tosiaan, tässähän kysyttiin 3D meshistä. Olen ymmärtänyt, että mesh on pintamuoto, ei siis täytetty objekti. Näin ollen sen painopisteen laskemiseen käytetään mielestäni edelleen kolmioita eikä tetraedrejä. Eikös mesh-malli yleensä kolmioista (faces) joten mielestäni painopisteen laskeminen pitäisi sujua ihan triviaalisti tosiaan laskemalla kolmioiden painopisteet ja niiden pinta-alalla painotettu keskiarvo.

Monenlaista määritelmää keskipisteelle... Toimisiko tämä?

koo kirjoitti:

Monenlaista määritelmää keskipisteelle... Toimisiko tämä?

Tuosta on varmaankin hyötyä kysyjälle. Huomauttaisin vielä että tuolla linkittämälläsi sivulla on puhe nimenomaan painopistettä (centroid) eli "massakeskispisteestä" ja sen määritelmä onkin ihan yksiselitteinen. Keskipiste terminä voi taas tarkoittaa vaikka mitä.

koo kirjoitti:

Monenlaista määritelmää keskipisteelle... Toimisiko tämä?

Sieltähän se vastaus löytyi. Yllättäen taas Paul Bourken sivuilta :)