Algorithmus: Abstand von Punkt zu Polygon
-
Hi Leute,
Ich bin hier an meiner Studienarbeit im Bereich Computeranimation, und habe den Programmcode einer vorhergehenden Diplomarbeit zu Verfügung, in der u.a. die Distanz eines Punktes zu einem Polygon (gegeben durch die Eckpunkte) berechnet wird. Da ich jetzt allerdings unerkläreliche Probleme bei der Berechnung neuer Eckpunkte bekommen habe, führte ich das Problem auf die Distanzberechnung zurück, die mir z.B. für die kürzeste Distanz zwischen dem
Punkt P ( 0.1818, -0.2727, 0.0000 )
und dem
Dreieck D ( (0,0,0), (1,0,0), (1,0,1) )
die
Distanz d = 0.07438
berechnet. Wenn man sich das ganze mal aufzeichnet, erkennt man schnell, dass sogar die minimale Distanz des Punktes zur der dem Dreieck D entsprechenden sich unendlich ausdehnenden Ebene 0.2727 betragen muss, da sie der Länge des Lotes von P auf die Ebene entsprechen würde. Die Distanz zum Dreieck muss mindestens so lang sein.
Da ich zur Abstandsberechnung zwischen Punkt und endlicher Fläche im 3D-Raum nichts finden kann, poste ich hier mal den mir zur Verfügung stehenden Code, in der Hoffnung, dass Ihr den dahintersteckenden Algorithmus erkennt bzw. sogar wisst, wo eventuell der Fehler liegt. Danke!
------------------------------------------------------------------------
const float Triangle::getDistanceToPoint( const Vector &p ) { // Gegeben sind m_cornerA, m_cornerB, m_cornerC Vector m_edge0 = m_cornerB - m_cornerA; Vector m_edge1 = m_cornerC - m_cornerA; float m_fA = blitz::dot( m_edge0, m_edge0 ); float m_fB = blitz::dot( m_edge0, m_edge1 ); float m_fC = blitz::dot( m_edge1, m_edge1 ); float m_s = 0.0; float m_t = 0.0; float fd = blitz::dot( m_edge0, ( m_cornerA - p )); float fe = blitz::dot( m_edge1, ( m_cornerA - p )); float ff = blitz::dot(( m_cornerA - p ), ( m_cornerA - p )); float denom = m_fA * m_fC - m_fB * m_fB; float s_0 = m_fB * fe - m_fC * fd; float t_0 = m_fB * fd - m_fA * fe; float s, t; float ret_val; if( s_0 + t_0 <= denom ) { if( s_0 < 0.0 ) { if( t_0 < 0.0 ) { //region 4 if( fe < 0.0 ) { //copied from region3 s = 0.0; t = ( fe >= 0.0 ? 0.0 : ( -fe >= m_fC ? 1.0 : -fe / m_fC )); } else { //copied from region 5 t = 0.0; s = ( fd >= 0.0 ? 0.0 : ( -fd >= m_fA ? 1.0 : -fd / m_fA )); } } else { //region 3 s = 0.0; t = ( fe >= 0.0 ? 0.0 : ( -fe >= m_fC ? 1.0 : -fe / m_fC )); } } else if( t_0 < 0.0 ) { //region 5 t = 0.0; s = ( fd >= 0.0 ? 0.0 : ( -fd >= m_fA ? 1.0 : -fd / m_fA )); } else { //region 0 denom = 1.0 / denom; s = s_0 * denom; t = t_0 * denom; } } else { if( s_0 < 0.0 ) { //region 2 if(( -m_fC - fe ) < 0.0 ) { //copied from region3 s = 0.0; t = ( fe >= 0.0 ? 0.0 : ( -fe >= m_fC ? 1.0 : -fe / m_fC )); } else { //copied from region 1 s = ( m_fC - m_fB + fe - fd ); if( s < 0.0 ) { s = 0.0; } else { s = s / ( m_fA - 2.0 * m_fB + m_fC ); if( s > 1.0 ) { s = 1.0; } } t = 1.0 - s; } } else if( t_0 < 0.0 ) { //region 6 if( -m_fA - fd < 0.0 ) { //copied from region 5 t = 0.0; s = ( fd >= 0.0 ? 0.0 : ( -fd >= m_fA ? 1.0 : -fd / m_fA )); } else { //copied from region 1 s = ( m_fC - m_fB + fe - fd ); if( s < 0.0 ) { s = 0.0; } else { s = s / ( m_fA - 2.0 * m_fB + m_fC ); if( s > 1.0 ) { s = 1.0; } } t = 1.0 - s; } } else { //region 1 s = ( m_fC - m_fB + fe - fd ); if( s <= 0.0 ) { s = 0.0; } else { s = s / ( m_fA - 2.0 * m_fB + m_fC ); if( s >= 1.0 ) { s = 1.0; } } t = 1.0 - s; } } m_s = s; m_t = t; // ret_val = sqrt(fabs(m_fA*s*s + 2.0*m_fB*s*t + m_fC*t*t + 2.0*fd*s + 2.0*fe*t + ff)); ret_val = fabs( m_fA * s * s + 2.0 * m_fB * s * t + m_fC * t * t + 2.0 * fd * s + 2.0 * fe * t + ff ); return( ret_val ); }Mir steigen die ganzen Skalarprodukte ( blitz::dot(x,y) ) über den Kopf. Ich kann mir da nix anschaulich zusammenreimen.
Danke für Eure Hilfe
-
lies dir mal den kommentar durch,
die funktion lässt das wurzelziehen weg
(wahrscheinlich, weil man eh nur vergleiche mit den werten machen sollte,
sqrt is streng monoton ... usw. das muss ich einem diplomanten ja nicht erklären)vllt solltest du die funktion umbennen
getDistanceToPointSquared( const Vector &p )oder irgend so ein mist
-
Ja es geht vorerst um den quadrierten Abstand. Erst wenn man den geringsten Abstand gefunden hat, wird die Wurzel gezogen.
Welchem Kommentar meinst du genau?
Danke und Grüßle
-
Hm diese if-if-if-if strukturen sehen ja ein wenig unueberichtlich aus. Dazu kommt, dass ueberfluessige Abfragen eingebaut sind, beispielsweise im ersten if-if-if-if-Block:
if( fe < 0.0 ) { //copied from region3 s = 0.0; t = ( fe >= 0.0 ? 0.0 : ( -fe >= m_fC ? 1.0 : -fe / m_fC )); }Die Abfrage fe >= 0.0 ist ueberfluessig, da ja laut Abfrage fe<0.0 gilt.
-
jiriki schrieb:
Ja es geht vorerst um den quadrierten Abstand. Erst wenn man den geringsten Abstand gefunden hat, wird die Wurzel gezogen.
Dann zieh doch mal die Wurzel aus dem was Dir das Programm ausspuckt... das passt ziemlich genau zu dem, was Du erwartest.
edit: btw passiert da eigentlich nix anderes als zunächst eine Projektion auf die Ebene in der das Dreieck liegt. Anschließend werden ein paar Fälle durchgespielt, wo die Projektion liegen kann. Allerdings ist der Code auch nicht besonders schön.