Autor Wątek: Punkt we wklęsłym wielokącie [PointInConcavePolygon]  (Przeczytany 760 razy)

Offline Maciekp

  • Użytkownik
    • maciekpartyka

# Sierpień 05, 2011, 21:00:45
Witajcie drodzy Bracia Programiści!
Tak oto kodując w upalny dzień, napotkałem problem który zdaje się przekraczać wszelkie moje umiejętności koderskie, lecz mam nadzieję, że nie Wasze.
Chciałem wykryć, czy dany punkt znajduje się w danym wielokącie wklęsłym. Cała akcja rozgrywa się 2D, tak więc funkcje nie powinny być zbyt skomplikowane, a jednak!
Chciałem skorzystać z metody, gdzie trzeba sprawdzić ile razy półprosta od danego punktu przecina ściany wielokątu.
Jeśli nieparzyście, punkt jest w wielokącie, jeśli parzyście- punkt jest poza wielokątem.
----------------
Funkcja, do której przekazuje wierzchołki, offset w tablicy , p-punkt.
bool PointInConcavePolygon(float *v,int qty,unsigned int offset,CVector p)
{
    bool inside=false;
//ostatnie punkty. zaczynamy od ostatniej sciany-> laczymy ostatni punkt z pierwszym
    float lX=v[offset+qty*3-3],lY=v[offset+qty*3-2];
    for(int i=offset;i<offset+qty*3;i+=3){
          //polprosta [-infinity,p.y]->[p.x,p.y]
        if(IntersectionSegmentSegment2D(-9999999,p.y,p.x,p.y,lX,lY,v[i],v[i+1]))
            inside=!inside;
        lX=v[i];
        lY=v[i+1];
    }
    return inside;
}
Ta funkcja została napisana przeze mnie, więc to pewnie tutaj jest błąd...
Sprawdzam, czy 2 linie się przecinają, jeśli tak, to sprawdzam czy 0<=s<=t<=1. Jeśli tak ,to segmenty również się przecinają.
bool IntersectionSegmentSegment2D(float x1, float y1, float x2, float y2,
                               float x3, float y3, float x4, float y4)
{
    float x,y;
    if(IntersectionLineLine2D(x1,y1,x2,y2,x3,y3,x4,y4,x,y))
    {
        //moznaby sprawdzic tylko na x, albo tylko na y, ale by trzeba bylo wiedziec, czy ktores !=0
        CVector p1(x4-x3,y4-y3,0);
        CVector p2(x-x3,y-y3,0);
        p1.x!=0&&(p2.x/=p1.x);
        p1.y!=0&&(p2.y/=p1.y);
        if(p2.Length()>1||(p2.x<0&&p2.y<0))
            return false;
        p1.set(x2-x1,y2-y1,0);
        p2.set(x-x1,y-y1,0);
        p1.x!=0&&(p2.x/=p1.x);
        p1.y!=0&&(p2.y/=p1.y);
        if(p2.Length()<=1&&p2.x>=0&&p2.y>=0)
            return true;
    }
    return false;
}
Ta funkcja na pewno działa, z ->http://mathworld.wolfram.com/Line-LineIntersection.html
bool IntersectionLineLine2D(float x1,float y1,float x2,float y2,
                               float x3,float y3,float x4,float y4,
                                float &x,float &y)
{
    float x00=x1*y2-y1*x2;
    float x10=x1-x2;
    float x01=x3*y4-y3*x4;
    float x11=x3-x4;
    float uxd1=x00*x11-x10*x01;
    float uxd2=x10*(y3-y4)-(y1-y2)*(x3-x4);
    if(uxd2==0)
        return false;
    x=uxd1/uxd2;

    float y10=y1-y2;
    float y11=y3-y4;
    float uyd1=x00*y11-y10*x01;
    float uyd2=x10*y11-y10*x11;
    if(uyd2==0)
        return false;
    y=uyd1/uyd2;
    return true;
}
Za wszelką okazaną mi pomoc, obiecuję góry złota i darmowe wejściówki do burdelu pod Warszawą, o którym sam Bill Gates do dziś wypowiada się z największym szacunkiem, miło wspominając dawne lata młodości.
« Ostatnia zmiana: Sierpień 05, 2011, 21:07:21 wysłana przez Maciekp »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline nembutal

  • Użytkownik

# Sierpień 05, 2011, 21:21:29
http://www.faqs.org/faqs/graphics/algorithms-faq/
Subject 2.03: How do I find if a point lies within a polygon?
Tam jest kod.
Jest też tutaj:
http://tog.acm.org/resources/GraphicsGems/gemsiv/ptpoly_haines/ptinpoly.c
(Funkcja CrossingsMultiplyTest na końcu pliku)

Offline Maciekp

  • Użytkownik
    • maciekpartyka

# Sierpień 06, 2011, 12:12:44
Zażenowany, że kolejna funkcja z internetu nie chce działać poprawnie, napisałem własną. Umieszczam jakby ktoś miał mało takich funkcji w internecie:
bool myPointTest(float *v,int pQty,unsigned int offset,CVector p)
{
    bool inside=false;
    float lX=v[offset+pQty*3-3],lY=v[offset+pQty*3-2];
    for(int i=offset;i<offset+pQty*3;i+=3){
        CVector c1(lX,lY,0);
        CVector c2(v[i],v[i+1],0);

        //czy punkty sa po roznych stronach p.y
        if((p.y-c2.y)*(p.y-c1.y)>0){
            lX=v[i];
            lY=v[i+1];
            continue;
        }

        float h=p.y-c1.y;
        CVector c(c2-c1);
        c.Normalize();
        float qty=h/c.y;
        c=c1+qty*c;
        CVector v4=c;
        if(v4.x>p.x){
            lX=v[i];
            lY=v[i+1];
            continue;
        }
        inside=!inside;
        lX=v[i];
        lY=v[i+1];
    }
    return inside;
}
zwraca true dla punktu w wielokacie wkleslym 2d, false poza tym wielokatem