dev.gamez.lv Forum Index dev.gamez.lv
Latvian Game Developers Community
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 

Dota linija. Noteikt vai punks atrodas uz linijas.

 
dev.gamez.lv Forum Index -> Matemātika un fizika
View previous topic :: View next topic  
Author Message
coderpp



Joined: 20 Aug 2005
Posts: 167
Location: Rīga, Koknese, Gajiena

PostPosted: Tue Jan 29, 2008 8:43 am    Post subject: Dota linija. Noteikt vai punks atrodas uz linijas.

Doti divi punkti - A(x1, y1) un B(x2, y2) - caur kuriem novilkta linja. Vel ir tresais punkts C(x, y). Janosaka vai punkts C atrodas uz linijas un atrodas starp punktiem A, B. Kads var palidzet ar formulu?
Back to top
View user's profile Send e-mail
MoKa



Joined: 10 Oct 2007
Posts: 79
Location: Daugavpils

PostPosted: Tue Jan 29, 2008 9:49 am    Post subject:

Может помочь функция с проверкой коллизии окружности и отрезка, думаю разберёшся :)

Code:
' Line - Circle
'   LinePoint1X,LinePoint1Y,LinePoint2X,LinePoint2Y,CircleCenterX,CircleCenterY,CircleRadius
Function LineOverlapCircle(x1#,y1#,x2#,y2#,cx#,cy#,Radius#)
   phCollDist#=0 phCollLineAng#=0 phCollAng#=0 phCollNX#=0 phCollNY#=0 phCollNPointX#=0 phCollNPointY#=0
   Local Ang#,Dist1#,Dist2#
   Local nx#,ny#
   Local dx31#=cx#-x1#
   Local dx21#=x2#-x1#
   Local dy31#=cy#-y1#
   Local dy21#=y2#-y1#
   Local d#=((dx21#*dx21#)+(dy21#*dy21#))
   
   If d#<>0 d#=((dx31#*dx21#)+(dy31#*dy21#))/d#
   If d#<0.0 d#=0
   If d#>1.0 d#=1
   Dist1=Distance2D#(cx,cy,(x1#+(dx21#*d#)),(y1#+(dy21#*d#)))
   
   If Radius#=>Dist1
      phCollLineAng#=(270-ATan2((x2-x1),(y2-y1)))
      Nx#=Cos(phCollLineAng-90)*radius
      Ny#=Sin(phCollLineAng-90)*radius
      LinInter=LineIntersect(x1,y1,x2,y2,cx-Nx,cy-Ny,cx+Nx,cy+Ny)
      phCollNPointX#=LiX
      phCollNPointY#=LiY
      If LinInter=False
         Dist1#=Distance2D(x1,y1,cx,cy)
         Dist2#=Distance2D(x2,y2,cx,cy)
         If Dist1<Dist2
            phCollNPointX#=x1
            phCollNPointY#=y1
         Else
            phCollNPointX#=x2
            phCollNPointY#=y2
         EndIf
      EndIf
      phCollAng#=(180.0-ATan2((cx-phCollNPointX),(cy-phCollNPointY)))
      phCollDist#=radius-Distance2D(phCollNPointX,phCollNPointY,cx,cy)
      phCollNX#=Cos(phCollAng-90)
      phCollNY#=Sin(phCollAng-90)
      
      Return True
   EndIf
End Function


Она правда ещё присваивает много другой инфы, в общем писал для реализации физики на основе окружности и отрезков.
_________________
Текущий Инструментарий: BlitzMax + Xors3D + FastImage + PhysX + sFXe
Back to top
View user's profile Visit poster's website
bubu
Indago Uzvarētājs
Indago Uzvarētājs


Joined: 23 Mar 2004
Posts: 3223
Location: Riga

PostPosted: Tue Jan 29, 2008 11:24 am    Post subject:

MoKa: kas par spamu? Te ar riņķiem nav nekāa sakara.

Līniju var uzdot parametriskā formā ar diviem vienādojumiem:
x = Ax + t * (Bx - Ax)
y = Ay + t * (By - Ay)
kur, ja t pieder intervālam [0, 1], tad (x,y) atrodas starp A un B punktiem.

Izsakot no abiem vienādojumiem t:
x - Ax = t * (Bx - Ax)
y - Ay = t * (By - Ay)

No abiem var izteikt t:
t = (x - Ax) / (Bx - Ax)
t = (y - Ay) / (By - Ay)

Abas puses pielīdzinot dabū: (x - Ax) * (By - Ay) = (y - Ay) * (Bx - Ax)

Ja šis vienādojums ir patiess (ņem tik vērā float salīdzināšanas neprecizitāti), ta punkts (x,y) ir uz taisnes, kas savieno punktus A un B.
Atliek noskaidrot vai tas ir starp punktiem A un B pa vidu.

To var darīt izrēķinot t:
Code:
if (Bx - Ax != 0)
{
    t = (x - Ax) / (Bx - Ax)
}
else if (By - Ay != 0)
{
    t = (y - Ay) / (By - Ay)
}
else
{
    // ERROR, punkti A un B sakrīt! Taisne nav iespējama.
}

Salīdzināšanās ņem vērā float neprecizitāti. Labāk ir salīdzināt nevis tieši ar 0, bet gan ar mazu epsilon vērtību (piemēram 1e-6).

Tagad, kad esi dabūjis t vērtību atliek pārbaudīt vai tā ir no 0 līdz 1 (ieskaitot). Ja ir - tad punkts atrodas starp A un B. Citādi - neatrodas.

To visu var smukākā veidā pierakstīt šādi:
Code:
bool IsPointOnLineSegment(Point a, Point b, Point c)
{
    Point ab = b - a;
    if (Dot(ab, ab) == 0.0)
    {
        throw Error("a un b ir viens un tas punkts!");
    }
    float t = Dot(c - a, ab) / Dot(ab, ab);

    return t >= 0.0f && t <= 1.0f;
}

Dot ir vektoru skalārais reizinājums, t.i. Dot( (a,b), (c,d) ) = a*c + b*d.
(ja vajag, tad varu izvest arī šajā funkcijā lietotās formulas).

P.S. Nejauc līnijas ar nogriežņiem. Līnijas ir bezgalīga garuma. Nogriezinis ir līnijas fragments, kas atrodas starp diviem punktiem. Tev vajag noskaidrot vai punkts ir uz nogriežņa, nevis līnijas ;)
Back to top
View user's profile Send e-mail
MoKa



Joined: 10 Oct 2007
Posts: 79
Location: Daugavpils

PostPosted: Tue Jan 29, 2008 11:47 am    Post subject:

Никакого спама, функция урезается до ~10 строк, и выполняет свою роль.
Чтож, если она не совсем отвечает по теме, окай, больше попыток помоч не будет.
_________________
Текущий Инструментарий: BlitzMax + Xors3D + FastImage + PhysX + sFXe
Back to top
View user's profile Visit poster's website
Display posts from previous:   
dev.gamez.lv Forum Index -> Matemātika un fizika All times are GMT + 2 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group