Ergebnis 1 bis 11 von 11

Thema: Distanz Punkt Polygon

  1. #1
    Benutser Avatar von rownn
    Registriert seit
    17.12.2011
    Ort
    DDB
    Beiträge
    650
    Software
    MSA

    Standard Distanz Punkt Polygon

    Hey allerseits,

    ich suche nach einer Herangehensweise einen Punkt-Polygon-Abstand zu berechnen.
    Ich stell die Frage gleich mal hier rein, weil ich mich schon ewig tüfteln sehe um eine wackelige Lösung zu finden. Habe im SDK auf jeden noch nix gefunden oder es schlichtweg überlesen :/

    In meiner Vorstellung sollten die selektierten Punkte dem größeren Polygon des anderen Objektes zugeordnet werden und die anderen dem anderen des anderen.



    Grüße und Danke schonmal
    rownn

    Nicht möglich! 0 Nicht möglich!

  2. #2
    Benutser Avatar von rownn
    Registriert seit
    17.12.2011
    Ort
    DDB
    Beiträge
    650
    Software
    MSA

    Standard

    Also meine Überlegung ist folgende ...

    Schritt 1: Ich trianguliere das Polygon.

    Schritt 2: Ich nehme das erste Tri und brechne anhand der 3 Punkte eine Matrix deren Z-Richtung die Normale des Tris ist.

    Schritt 3: Ich rechne den Punkt in die Matrix des Tris und setze den neuen Vektor auf z = 0.

    Schritt 4: Ich überprüfe ob der Vektor innerhalb des Dreiecks des Tris liegt. (Wie auch immer man das macht.)

    Schritt 5: Wenn der Vektor innerhalb des Dreiecks liegt, dann ist der nicht auf 0 gesetzte Z-Wert der Abstand.

    Schritt 6: Wenn der Vektor außerhalb des Dreiecks liegt, dann berechne ich den jeweils kürzesten Abstand des Punktes zu den drei Geraden des Tris. (Mal sehen wie man das macht.) Der kleinste der resultierenden Abständen wäre dann der gesucht Abstand vom Punkt zum Tri.

    Schritt 7: Schritt 2 bis 6 mit dem anderen Tri.

    Schritt 8: Die beiden Abstände vom Punkt zu den Tris vergleichen und der kleinere ist der Gewinner.

    Hmm...

    Nicht möglich! 0 Nicht möglich!

  3. #3
    Witwer Avatar von MoeGraph
    Registriert seit
    27.07.2013
    Ort
    Duisburg
    Beiträge
    729
    Software
    CINEMA 4D R14

    Standard

    Damit ich es richtig verstanden habe, es soll durch die Punkte des einen Objektes iteriert werden und jedem Punkt ein Polygon (das auch mehrfach genannt werden kann) des anderen Objektes zugeordnet werden? Dabei soll jenes Polygon gewählt werden, dass beim sinnbildlichen wachsen des Punktes (zu einer Kugel) zuerst mit diesem kollidiert?

    Das Ganze soll vermutlich auch dreidimensional funktionieren?

    Nicht möglich! 0 Nicht möglich!
    Geändert von MoeGraph (11.08.2017 um 22:08 Uhr)
    Mein "aktuelles" Projekt Schraube
    http://c4dnetwork.com/board/threads/85938-Vollparametrische-Schraube?p=803316

  4. #4
    Benutser Avatar von rownn
    Registriert seit
    17.12.2011
    Ort
    DDB
    Beiträge
    650
    Software
    MSA

    Standard

    Ja, das trifft´s. 3dimentional, ja.

    Nicht möglich! 0 Nicht möglich!

  5. #5
    User auf Probe Avatar von pyrael
    Registriert seit
    30.07.2010
    Ort
    Düsseldorf
    Beiträge
    1.231
    Software
    MSA

    Standard

    ich weiss nicht ob dir das was hilft aber hier habe ich ein paar mesh funktionen:


    Code:
    def getNearestPoints(connectedPolys, pointsOnPoly):
    
        connectedPolys = list(set(connectedPolys))
        out = []
    
        for poly in connectedPolys:
            if pointsOnPoly[poly]:
                out += pointsOnPoly[poly]
    
        return out
    
    
    def getPointsFromPoly(connectedPolys, polys, mesh):
    
        points = []
        for p in connectedPolys:
            points.append(mesh.GetPoint(polys[p].a))
            points.append(mesh.GetPoint(polys[p].b))
            points.append(mesh.GetPoint(polys[p].c))
        return points
    
    
    def createMesh(surface):
    
        surface2list = [surface]
        doc = c4d.documents.GetActiveDocument()
        settings = c4d.BaseContainer()
        settings.SetBool(c4d.MDATA_CURRENTSTATETOOBJECT_INHERITANCE, True)
        polysurface = c4d.utils.SendModelingCommand(c4d.MCOMMAND_CURRENTSTATETOOBJECT, surface2list, bc=settings, doc=doc)
    
        settings = c4d.BaseContainer()
        c4d.utils.SendModelingCommand(c4d.MCOMMAND_TRIANGULATE, polysurface, bc=settings, doc=doc)
    
        return polysurface[0]
    
    
    polySize = math.sqrt(((points[polys[i].a] - points[polys[i].b]).GetLength() * (points[polys[i].a] - points[polys[i].c]).GetLength()) / 2)

    Nicht möglich! 0 Nicht möglich!
    -
    postwendend.com
    -

  6. #6
    Benutser Avatar von rownn
    Registriert seit
    17.12.2011
    Ort
    DDB
    Beiträge
    650
    Software
    MSA

    Standard

    So, habe ein bisschen Zeit gefunden da mal zu tüfteln. Is irgendwie ein arrg langer Code geworden ... ni so geil, aber ich denke dass es erstmal funktioniert. Theoretisch sollte jetzt immer der kürzeste Abstand vom Punkt zum Objekt plus Polygonindex berechnet werden.

    Worauf ich hinaus will soll zwar kein LiveUpdateZeusch sein, aber ich bange um die Performance ... mal schauen.



    Code:
    PointPolygonobjectDistance(point, polygonobject)
    Parameters
    point = globaler Vektor
    polygonobject = das Polygonobject
    
    return: list
    distance = kürzeste Distanz zw. Punkt und Objekt
    vector = globaler Vektor auf Objekt
    polyID = Index des Polygons
    Code:
    import c4d
    import math
    #Welcome to the world of Python
    
    def IsInTriXY(tp0, tp1, tp2, p):
        dvs = [(tp^c4d.Vector(1,1,0))-(p^c4d.Vector(1,1,0)) for tp in [tp0, tp1, tp2]]
        return int(sum([c4d.utils.GetAngle(dvs[i], dvs[(i+1)%3]) for i in xrange(3)])*1000) == int(math.pi*2*1000)
    
    def DistanceVectorTriXY(tp0, tp1, tp2, p):
        return min([c4d.utils.PointLineSegmentDistance2D(tp0, tp1, p), c4d.utils.PointLineSegmentDistance2D(tp1, tp2, p), c4d.utils.PointLineSegmentDistance2D(tp2, tp0, p)], key=lambda t: t[0])
        
    def GetTriMatrix(p0, p1, p2):
        off = (p0+p1+p2)/3
        aim = ((p1+p2)/2-p0).GetNormalized()
        third = aim.Cross(p1-p2).GetNormalized()
        up = aim.Cross(third).GetNormalized()
        return c4d.Matrix(off, aim, up, -third)
            
    def PointPolygonobjectDistance(point, polygonobject):
        mg = polygonobject.GetMg()
        pnts = [p*mg for p in polygonobject.GetAllPoints()]
        plys = polygonobject.GetAllPolygons()
        
        distance = 100000000.0
        vector = c4d.Vector()
        polyID = -1
        
        for index, ply in enumerate(plys):
            if ply.IsTriangle(): tris = ([pnts[ply.a],pnts[ply.b],pnts[ply.c]],)
            else: tris = ([pnts[ply.a],pnts[ply.b],pnts[ply.c]], [pnts[ply.a],pnts[ply.c],pnts[ply.d]])
            
            for tri in tris:
                triMg = GetTriMatrix(tri[0], tri[1], tri[2])
                triPoints = [p*~triMg for p in tri]
                pointInM = point*~triMg
                
                if IsInTriXY(triPoints[0], triPoints[1], triPoints[2], pointInM):
                    if int(distance*10000) > int(abs(pointInM.z)*10000):
                        distance = abs(pointInM.z)
                        vector = (pointInM^c4d.Vector(1,1,0))*triMg
                        polyID = index
                    
                else:
                    tup = DistanceVectorTriXY(triPoints[0], triPoints[1], triPoints[2], pointInM)
                    d = math.sqrt(tup[0]**2+pointInM.z**2)
                    if int(distance*10000) > int(d*10000):
                        distance = d
                        vector = tup[1]*triMg
                        polyID = index
                        
        return distance, vector, polyID
        
    
    def main():
        obj = op.GetObject()
        A = doc.SearchObject("A")
        dist, vec, index = PointPolygonobjectDistance(A.GetRelPos(), obj)
    Grüße
    rownn

    PS: @pyrael, besten Dank für die Zeilen.
    Angehängte Dateien Angehängte Dateien

    Nicht möglich! +2 Nicht möglich!

  7. #7
    böse & unprofessionell™ Avatar von Yakuza
    Registriert seit
    28.03.2007
    Ort
    Annexia
    Beiträge
    6.255
    Software
    MSA

    Nicht möglich! 0 Nicht möglich!
    "you're so special, just like anybody else."

  8. #8
    Benutser Avatar von rownn
    Registriert seit
    17.12.2011
    Ort
    DDB
    Beiträge
    650
    Software
    MSA

    Standard

    Collider is klar, aber dafür müsste ich vom Punkt aus in alle Richtungen und in die Richtungen zwischen den Richtungen schießen um den kürzesten Abstand zu bekommen. Wobei ich dann noch nicht weiß ober eine Richtung zwischen Richtungen zwischen den Richtungen evtl. noch einen kürzeren Abstand ergeben würde. Oder sehe ich das falsch?

    Nicht möglich! 0 Nicht möglich!

  9. #9
    böse & unprofessionell™ Avatar von Yakuza
    Registriert seit
    28.03.2007
    Ort
    Annexia
    Beiträge
    6.255
    Software
    MSA

    Standard

    Zitat Zitat von rownn Beitrag anzeigen
    Collider is klar, aber dafür müsste ich vom Punkt aus in alle Richtungen und in die Richtungen zwischen den Richtungen schießen um den kürzesten Abstand zu bekommen. Wobei ich dann noch nicht weiß ober eine Richtung zwischen Richtungen zwischen den Richtungen evtl. noch einen kürzeren Abstand ergeben würde. Oder sehe ich das falsch?
    nein, ich hatte mich da nicht so reingedacht, nur dass der collider evtl. hilfreich sein könnte und du ihn nicht kennst.

    Nicht möglich! +1 Nicht möglich!
    "you're so special, just like anybody else."

  10. #10
    User auf Probe Avatar von pyrael
    Registriert seit
    30.07.2010
    Ort
    Düsseldorf
    Beiträge
    1.231
    Software
    MSA

    Standard

    Bitte bitte.
    Im prinzip hast du Recht was RayCollide angeht. Nur wenn du das RayCasten umdrehst. Also von allen Normalen die dem Punkt zugewannt sind sollte das gehen.

    Ach ja KEKS!

    Nicht möglich! 0 Nicht möglich!
    -
    postwendend.com
    -

  11. #11
    Benutser Avatar von rownn
    Registriert seit
    17.12.2011
    Ort
    DDB
    Beiträge
    650
    Software
    MSA

    Standard

    Hey,

    hab mir grad mal bissl die Performance angeschaut. Hab mich noch nie näher damit beschäfftigt, aber man kann einiges rausholen. Habe 1Punkt auf 100.000Polys getestet. Mit der alten Funktion braucht das 0.355s und mit dem neuen nur noch 0.184s. Nicht optimal, aber schonmal die Hälfte. Wenn man mehr als einen Punkt testen will, müsste das ganze umgebastelt werden, weil viele Sachen sich wiederholen. Wie auch immer blablub ...
    Code:
    def PointPolygonobjectDistance(point, polygonobject):
        pnts = polygonobject.GetAllPoints()
        plys = polygonobject.GetAllPolygons()
        plyCount = len(plys)
        
        lst = [100000000.0, c4d.Vector(), -1]
        pi2 = int(pi*2*1000)
        
        for index, ply in enumerate(plys):
            if ply.IsTriangle(): tris = ([pnts[ply.a],pnts[ply.b],pnts[ply.c]],)
            else: tris = ([pnts[ply.a],pnts[ply.b],pnts[ply.c]], [pnts[ply.a],pnts[ply.c],pnts[ply.d]])
            
            for tp0, tp1, tp2 in tris:
                off = (tp0+tp1+tp2)/3
                aim = ((tp1+tp2)/2-tp0).GetNormalized()
                third = aim.Cross(tp1-tp2).GetNormalized()
                up = aim.Cross(third).GetNormalized()
                triMatrix = c4d.Matrix(off, aim, up, -third)
                
                pointInM = point*~triMatrix
                p = pointInM^c4d.Vector(1,1,0)
                
                tp0 *= ~triMatrix
                tp1 *= ~triMatrix
                tp2 *= ~triMatrix
                
                dv0 = tp0-p
                dv1 = tp1-p
                dv2 = tp2-p
                
                if int((GetAngle(dv0, dv1)+GetAngle(dv1, dv2)+GetAngle(dv2, dv0))*1000)==pi2:
                    if int(lst[0]*10000) > int(abs(pointInM.z)*10000): lst = [abs(pointInM.z), p*triMatrix, index]
                
                else:
                    tup = PointLineSegmentDistance2D(tp0, tp1, p)
                    tup1 = PointLineSegmentDistance2D(tp1, tp2, p)
                    tup2 = PointLineSegmentDistance2D(tp2, tp0, p)
                    
                    if tup1[0]<tup[0]: tup=tup1
                    if tup2[0]<tup[0]: tup=tup2
                    
                    d = (math.sqrt(tup[0]**2+pointInM.z**2))
                    if int(lst[0]*10000) > int(d*10000): lst = [d, tup[1]*triMatrix, index]
                    
        return lst
    Grüße
    rownn

    Nicht möglich! 0 Nicht möglich!

Aktive Benutzer

Aktive Benutzer

Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)

Lesezeichen

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •