Diskuze: Konvexné štvoruholníky

Jozef

Člen

Jozef:20.7.2015 10:53

Zdravím.
Narazil som na úlohu, v ktorej mám zo zadaných súradníc vypočítať počet všetkých konvexných štvoruholníkov, ktoré sa dajú zo zadaných bodov vytvoriť. Môj program pracuje na myšlienke, že vďaka vzorcu ux*vy - uy*vx (ux,uy,vx,vy, sú vektory zo zadaných bodov) je možné zistiť, kde sa bod nachádza vzhľadom na priamku. Kladný výsledok- bod sa nachádza naľavo; záporný výsledok - bod sa nachádza napravo; 0 - bod sa nachádza na priamke. A pre každý konvexný štvoruholník platí, že jeho každý vrchol je od priamky, ktorá sa naňho napája napravo, resp. každý vrchol je naľavo. Takže ak pre každú stranu a vrchol zistíme pozíciu a keď je každá z tých pozícii záporná, resp. každá kladná, tak sa jedná o konvexný štvoruholník. Potom už iba vyskúšam všetky možnosti. Kedže štvoruholník s konkrétnymi bodmi je len jeden, ale môžu byť vrcholy poprehadzované(napr. 4.-uholník so stranami 0 2 3 1 je ten istý ako 1 0 2 3) ale môj program ho započíta dvakrát. To som vyriešil tým, že ukladám si pozície vrcholov v utriedenom poradí a potom porovnávam, či už 4-uholník s rovnakými vrcholmi nemám. Ak nie, uložím ho a započítam, ak áno, nerobím nič. Program funguje síce správne, ale pomaly, pretože pre vysoký počet bodov nestíham časový limit. Dalo by sa nejakým spôsobom ošetriť môj kód, aby som vždy započítal každý 4-uholník iba raz? Ak nie, akým iným spôsobom mám riešiť túto úlohu?

Príklad vstupu:

vstup               výstup
5                     3
0 0
6 0
0 6
6 6
5 3

vstup               výstup
6                     9
0 0
0 1
1 0
1 1
2 0
2 1

Prvé číslo udáva počet zadaných súradníc, nasleduje N súradníc.

#include<stdio.h>

void bubbleSort(int list[],int size) {
  // kontrola prohozeni
  int swapped = 1,temp;
  while (swapped) {
    swapped = 0;
    for (int i = 0; i < size; i++) {
      // prohozeni
      if (list[i] > list[i + 1]) {
        temp = list[i];
        list[i] = list[i + 1];
        list[i + 1] = temp;
        swapped = 1;
      }
    }
    size--;
  }
}

/**
štruktúra na suradnice x,y
*/
typedef struct
{
    int x;
    int y;
} POINT;

typedef struct
{
    int a;
    int b;
    int c;
    int d;

} ZAZNAM;

/**
* funkcia spocíta, ci sa bod z nachádza od priamky |xy| napravo - vráti sa záporná hodnota;
* naľavo - vráti sa kladná hodnota;
* na priamke - vráti sa 0;
*/
int calculate_vector(POINT x, POINT y, POINT z)
{
    int ux = y.x - x.x;
    int uy = y.y - x.y;
    int vx = z.x - x.x;
    int vy = z.y - x.y;
    return ux*vy - uy*vx;
}

int main()
{
    int i,j,k,l,n;
    int res1,res2,res3,res4,num;
    res1 = res2 = res3 = res4 = num = 0;
    scanf("%d",&n);
    POINT array[n];
    ZAZNAM zaz[120000];
    int cislo = 0;
    int new;
    for(i = 0; i < n; i++)
        scanf("%d%d",&array[i].x, &array[i].y);
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(j != i){
                for(k = 0; k < n; k++){
                    if(k != i && k != j){
                        for(l = 0; l < n; l++){
                            if(l != i && l != k && l != j){

                                                                                            //res1....res4 zisujú, v akej pozícii sú všetky 4 body štvoruholníka.
                                res1 = calculate_vector(array[i],array[j],array[k]);  //tretí bod vzh¾adom na priamku prvého a druhého
                                res2 = calculate_vector(array[j],array[k],array[l]);   //štvrtý bod vzh¾adom na priamku druhého a tretieho
                                res3 = calculate_vector(array[l],array[k],array[i]);   //prvý bod vzh¾adom na priamku tretieho a štvrtého
                                res4 = calculate_vector(array[i],array[l],array[j]);    //druhý bod vzh¾adom na priamku štvrtého a prvého
                                if((res1 > 0 && res2 > 0 && res3 > 0 && res4 > 0)||(res1 < 0 && res2 < 0 && res3 < 0 && res4 < 0)){ //ak sú všetky body od seba buï napravo, alebo na¾avo, ide o konvexný útvar
                                    int sort[4];
                                    sort[0] = i;
                                    sort[1] = j;
                                    sort[2] = k;
                                    sort[3] = l;
                                    bubbleSort(sort,3);
                                    new = 1;
                                    for(int p = 0; p < cislo; p++){
                                        if(sort[0] == zaz[p].a && sort[1] == zaz[p].b && sort[2] == zaz[p].c && sort[3] == zaz[p].d){
                                            new = 0;
                                            break;
                                        }
                                    }
                                    if(new){
                                       zaz[cislo].a = sort[0];
                                       zaz[cislo].b = sort[1];
                                       zaz[cislo].c = sort[2];
                                       zaz[cislo++].d = sort[3];
                                       num++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    printf("%d\n",num);
    return 0;
}

Odpovědět

20.7.2015 10:53

I'm not afraid to die on a treadmill

Jozef

Člen

Jozef:21.7.2015 22:06

Nie je tu nikto, kto by mi vedel pomôcť?

Nahoru Odpovědět

21.7.2015 22:06

I'm not afraid to die on a treadmill

Drahomír Hanák

Tvůrce

Drahomír Hanák:21.7.2015 23:36

Taky by mě zajímalo optimální řešení.

V rychlosti mě napadlo: pokud těch bodů bude N a budou vrcholy konvexního polygonu, pak jejich počet bude N nad 4 (každé 4 body z N tvoří konvexní polygon - čtyřúhelník), což je zároveň maximální možný počet čtyřúhelníků, které ty body mohou tvořit. Třeba to pomůže.

Mimochodem pokud budeš počítat každý čtyřúhelník zvlášť, pak nejoptimálnější metoda bude muset projít v nejhorším případě ~N⁴/24 čtyřúhelníků

Nahoru Odpovědět

21.7.2015 23:36

coells

Tvůrce

coells:22.7.2015 0:01

Jozefe, do jaké míry chápeš to své řešení, které jsi někde zřejmě někde vyčetl?
Ptám se, protože typicky je pak velice těžké optimalizovat algoritmus, když nerozumíš tomu, o co se snaží, zatímco ty potřebuješ spočítat něco jiného.

Nevím, jestli má smysl to vysvětlovat, ale postup pro detekci konvexity, který používáš, má lineární složitost vzhledem k počtu vrcholů, což je výhodný pro mnohoúhelníky.
Alternativní detekce konvexity může místo vrcholů využívat úhlopříčky, jenže takový algoritmus má kvadratickou složitost, což se vyplatí pouze pro čtyřúheník. Et voilá!

Pro konvexní čtyřúhelník musí platit, že se úsečky dané úhlopříčkami protínají.
Pokud máš vrcholy zadané souřadnicemi, stačí sestavit parametrické rovnice vektorů a najít jediné řešení, pro které musí být oba parametry v rozmezí (0, 1) exkluzivně.
To je jen trocha lineární algebry.

Algoritmus:
1/ vezmeš dvojici vrcholů, která určí vektorově zadanou úhlopříčku
2/ vezmeš druhou dvojici vrcholů, která určí vektorově zadanou druhou úhlopříčku
3/ otestuješ průnik parametrických rovnic, pokud jsou oba parametry z (0, 1), máš konvexní čtyřúhelník

Budeš mít sice opět 4 vnořené for-cykly, ale stačí ti projet i=[0, n-3], j=[i+1, n-2], k=[j+1, n-1], l=[k+1, n].
Díky tomu každé 4 body zkontroluješ pouze a právě jednou a odpadne ti řada kontrol včetně toho nešťastného třídění vrcholů.

Nahoru Odpovědět

22.7.2015 0:01

coells

Tvůrce

coells:22.7.2015 2:08

Ještě malá poznámka k implementaci.

Pokud budeš procházet cykly tak, jak jsem je popsal, potřebuješ vyzkoušet ruzné kombinace úhlopříček ve čtyřúhelníku.
Naštěstí jsou takové kombinace jenom 3.
Navíc systém rovnic pro průnik vektorů musí vyjít v rozmezí (0, 1), což znamená, že ani není potřeba počítat výsledek.
Stačí, aby absolutní hodnota vedlejších determinantů byla menší než absolutní hodnota hlavního determinantu (a také musí mít stejné znaménko).

Upravený algoritmus:
1/ pro indexy: i=[0, n-3], j=[i+1, n-2], k=[j+1, n-1], l=[k+1, n]
2/ vezmi 4 vrcholy a sestav z nich 3 dvojice úhlopříček
3/ pro každou dvojici vytvoř parametrizované vektory
4/ spočítej hlavní a vedlejší determinanty Dh, Dv
5/ pokud 0 < Dv/Dh < 1 máš konvexní čtyřúhelník

Akceptované řešení
+20 Zkušeností
+2,50 Kč

Nahoru Odpovědět

22.7.2015 2:08

Jozef

Člen

Jozef:22.7.2015 9:34

Vďaka, práve niečo takéto som potreboval. Popis spôsobu akým sa to dá riešiť, kedže môj je zjavne príliš pomalý.
K tvojej otázke:

Jozefe, do jaké míry chápeš to své řešení, které jsi někde zřejmě někde vyčetl?

Toto riešenie som si celé vymyslel aj napísal sám, takže mu celkom rozumiem.Bolo to jediné čo ma napadlo na kontrolu konvexnosti, že sú body od strany 4-uholníka vždy na rovnakej strane- buď naľavo, alebo napravo.Pomocou analytickej geometrie nie je problém zistiť, v akej pozícii sa vzhľadom na priamku nachádzajú. Ale jediný spôsob, ktorý som vymyslel, ako skontrolovať všetky možné kombinácie, ktoré vytvárajú 4-uholník, boli v sebe vnorené 4 cykly.
Triedenie vrcholov som použil preto, aby bolo ľahšie skontrolovať, či už daný 4-uholník nemám zapísaný, kedže v takom prípade by boli všetky rovnaké vrcholy na rovnakých pozíciách.

Nahoru Odpovědět

22.7.2015 9:34

I'm not afraid to die on a treadmill