Pripadnost tačke mnogouglu

Pripadnst tačke mnogouglu ili poligonu je problem koji se često sreće u računarskoj grafici, a suština je određivanje pripadnosti proizvoljne tačke površini obuhvaćenoj datim mnogouglom. Tokom vremena razvijeno je više algoritama koji pristupaju ovom problemu. Uglavnom se njegova deklaracija svodi na dat uređeni skup tačaka, koje predstavljju mnogougao, i još jednu tačku, za koju treba proveriti pripadnost datom mnogouglu.

Metoda zraka

Ilustracija metode.

Pripadnost temena stranicama mnogougla, raspoređenih prema indeksima.

Primer prolaska zraka kroz dva temena, od kojih prvo ne treba da bude računato jer mu se i prethodno i sledeće teme nalaze sa iste strane zraka, dok drugo treba.

Metod zraka polazi od činjenice da zrak (poluprava) pri svakom presecanju granice mnogougla ili ulazi ili izlazi iz njega. Tako bi pri se pri povlačenju zraka iz date tačke i brojanjem njegovih preseka sa tim mnogouglom dalo ustanoviti da li je tačka (početak zraka) unutar mnogougla ili ne:

• Neparan broj preseka: tačka je u mnogouglu
• Paran broj preseka: tačka je van mnogougla

Zrak može imati bilo koji smer, ali se zbog lakoće računanja uzimaju vektori paralelni sa x ili y-osom.

U praksi se brojanje preseka postiže posebnom proverom za svaku stranicu mnogougla. Stvar koja može uzrokovati problem prilikom brojanja je prolazak zraka kroz neko teme mnogougla. I ovaj problem ima više aspekata. Prvi aspekat je činjenica da jedno teme mnogougla dele dve stranice mnogougla. Drugi je to što prolazak kroz teme ne mora da znači izlazak ili ulazak iz mnogougla.

Prvi deo problema se rešava podelom temena između stranica, tako da svaka stranica sadrži samo jedno teme tj. predstavlja poluzatvoreni interval. Kako su sva temena u mnogouglu indeksirana, pravilo bi moglo da dodeljuje neko teme stranici ako isto:

• ima najveći postojeći indeks, ili
• ukoliko ima indeks manji od indeksa drugog temena

Drugi deo problema izbegava nepoželjne slučajeve tako što ne broji prolaske kroz temena kod kojih se i prethodno i sledeće teme nalaze sa iste strane zraka. Naravno, ukoliko se data tačka poklapa sa nekim temenom ili leži na nekoj stranici, odmah se može zaključiti da pripada mnogouglu.

Još jedan podslučaj vredan razmatranja je kada je neka od stranica mnogougla paralelna sa smerom vektora i leži na zraku. Logički se u ovom slučaju ništa ne menja, ali zbog prirode računa se ovaj slučaj posebno obrađuje.

Implementacija

Recimo da je vektor zraka (0,-1) tj. vertikalan i usmeren „nadole“ odnosno u negativnom smeru y-ose. Tada će glavna metoda za ovu proveru u Javi izgledati ovako:

public static boolean tackaUMnogouglu(Tacka[] tacke, Tacka p) {
  int brojPreseka = 0;
  for(int i=0, j=1, k = tacke.length - 1; i < tacke.length; i++, j++, k++) {
    if(j == tacke.length) {
      j = 0;
    }
    if(k == tacke.length) {
      k = 0;
    }
    switch(tackaIznadStranice(p, tacke[i], tacke[j], tacke[k])) {
      case 1:
        brojPreseka++;
        break;
      case -1:
        return true;
    }
  }
  return (brojPreseka % 2) == 1;
}

Ova metoda vraća true ukoliko je tačka unutar mnogougla, a u suprotnom slučaju false. Pomoćnoj metodi tackaIznadStranice se uvek prosleđuju tačka i tri temena. Prva dva predstavljaju teme koje pripada stranici, drugo teme stranice koje se ne računa kao njen deo, i teme koje prethodi prvom temenu, da bi se moglo ustanoviti da li teme treba račuanti ili ne u specijalnim slučajevima. Metoda vraća 1 ukoliko se tačka nalazi iznad stranice (dakle duži, ne prave određene ovom stranicom), -1 ukoliko se nalazi negde na njoj, i inače 0. Pritom prati gorenavedeni algoritam.

public static int tackaIznadStranice(Tacka p, Tacka a, Tacka b, Tacka c) {
  // Специјалан случај, кад је страница паралелна вектору зрака
  if(Math.abs(a.x - b.x) < 1e-4) {
    // Да ли је тачка на истој x-координати?
    if(Math.abs(p.x - a.x) < 1e-4) { 
      if((p.y >= a.y && p.y <= b.y) || (p.y >= b.y && p.y <= a.y)) {
        return -1; // Ако се још налази и на правој, вратити -1.
      }
      // Ако се налази изнад праве, рачунати као пресек
      return p.y > a.y && p.y > b.y ? 1 : 0; 
    }
    return 0; // Иначе, нема пресека
  }

  // Ако тачка лежи на x-координати темена
  if(Math.abs(a.x - p.x) < 1e-4) {
    if(Math.abs(a.y - p.y) < 1e-4) { // Ако је тачка заправо у темену
      return -1;
    }
    if(p.y > a.y) { // Ако је тачка изнад темена
      // И ако теме треба да се урачуна, вратити један пресек
      return ((p.x - b.x)*(p.x - c.x) < 0) ?  1 : 0;
    }
  }

  // Ако тачка није изнад, на или испод странице, вратити 0
  if((p.x < a.x || p.x >= b.x) && (p.x > a.x || p.x <= b.x)) {
    return 0;
  }

  // y-координата дужи на пресеку са правом кроз тачку p у смеру зрака
  double hab = a.y + (b.y - a.y) * (p.x - a.x) / (b.x - a.x);

  // Ако је тачка на правој, вратити -1
  if(Math.abs(hab - p.y) < 1e-4) {
    return -1;
  }

  // Ако је тачка изнад, вратити 1. У супротном 0.
  return hab < p.y ? 1 : 0;
}

Metoda indeksa tačke

Primer tačke čiji je indeks u odnosu na datu krivu dva tj. tačka se nalazi unutar krive. Videti i animaciju.

Drugi metod je određivanje indeksa date tačke P u odnosu na datu putanju. Ova putanja može biti određena stranicama mnogougla, ali i bilo kojom zatvorenom krivom. Na putanji se izabire proizvoljna polazna tačka, i proizvoljnim smerom kretanja se obilazi cela putanja do povratka u polaznu tačku. Pri tome data tačka P prati ovo kretanje rotirajući u mestu, oko same sebe. Broj punih obrtaja koje tačka P ovako napravi se naziva njenim indeksom u odnosu na datu putanju. Ovaj broj pripada skupu N₀, a tačka P se nalazi unutar date putanje (odnosno figure koju ona obrazuje) ukoliko je ovaj broj veći od nule.

Metoda sume površina

Ilustracija metode sume površina

Pripadnost tačke mnogouglu se može odrediti i sumom površina svih trouglova koje ona gradi sa stranicama datog mnogougla. Ukoliko je ova suma jednaka površini mnogougla, tačka se nalazi unutar njega. Ukoliko je suma površina ovih trouglova veća od površine mnogougla, onda se nalazi van njega. Ograničenje ove metode je što se može primeniti samo na konveksne mnogouglove.

Ova metoda bi se takođe mogla smatrati najnepreciznijom od dve prethodne, jer se pri svakom račuanju površine trougla zbog osobina brojeva u pokretnom zarezu pravi greška koja se akumulira sa porastom broja stranica mnogougla.

Implementacija

Prema formuli kojom se na osnovu koordinata tačaka može izračuati površina mnogougla, može se odrediti površina kako zadatog mnogougla, tako i svakog trougla na koga je podeljen. Ova metoda bi u Javi izgledala ovako:

public static double povrsina(Tacka... tacke) {
 double pov = 0;
  for(int i=0, j=1; i<tacke.length; i++, j++) {
    if(j == tacke.length) {
      j = 0;
    }
    pov += tacke[i].x * tacke[j].y - tacke[i].y * tacke[j].x;
  }
  return Math.abs(pov) / 2;
}

A metoda koja određuje pripadnost tačke mnogouglu, bi se svela na:

public static boolean tackaUMnogouglu(Tacka[] tacke, Tacka p) {
  double povrsinaMnogougla = povrsina(tacke);
  double sumaPovrsina = 0;
  for(int i=0, j=1; i < tacke.length; i++, j++) {
    if(j == tacke.length) {
      j = 0;
    }
    sumaPovrsina += povrsina(tacke[i], tacke[j], p);
  }
  return Math.abs(sumaPovrsina - povrsinaMnogougla) < 1e-4;
}