wassimj / topologicpy

The python bindings for topologic
Other
91 stars 26 forks source link

Some questions about Graph #47

Closed gaoxipeng closed 5 months ago

gaoxipeng commented 8 months ago

Dear @wassimj : Hello, I saw the video on your YouTube about "Creating Directed Hierarchical Graphs in topologicpy," regarding the use of holes to create graphs of reachability. I have also implemented a similar effect before, I consider doors and stairs or elevators as passable faces, creating a reachability graph for a multi-story building. but I feel that the efficiency is too low. Do you have a more efficient method or could you share the code for implementing the graphics shown in the video?Thank you.

    g = Graph.ByTopology(cellcomplex)
    edges = Graph.Edges(g)
    neighborCell = []
    for edge in edges:
        vertices = Edge.Vertices(edge)
        cells = []
        for vertex in vertices:
            for cell in trans_cells:
                if Cell.IsInternal(cell, vertex):
                    cells.append(cell)
        neighborCell.append(cells)

    for cells in neighborCell:
        has_point_on_face = False
        for face in hole:
            v = Topology.CenterOfMass(face)
            if round(Vertex.Distance(v, cells[0])) == 0 and round(Vertex.Distance(v, cells[1])) == 0:
                has_point_on_face = True
                break
        if not has_point_on_face:
            v1 = Topology.CenterOfMass(cells[0])
            v2 = Topology.CenterOfMass(cells[1])
            edge = Edge.ByStartVertexEndVertex(v1, v2)
            allgraph = Graph.RemoveEdge(g, edge)

image

gaoxipeng commented 8 months ago

Dear @wassimj :In the latest 0.4.94 version, the following code takes a long time to execute and the generated web page is laggy if showVertices=True, but it works normally when showVertices=False. I tried the previous 0.4.78 version, and the execution times of these two settings were similar.

from topologicpy.Topology import Topology
from topologicpy.CellComplex import CellComplex

cp = CellComplex.Prism(width=10.0, 
                       length=10.0,
                       height=10.0,
                       uSides=9,
                       vSides=9,
                       wSides=9)
Topology.Show(cp,showVertices=True)
wassimj commented 8 months ago

Dear @gaoxipeng, Thank you for catching this bug. It seems it had to do with how I was dealing with "intensities" for vertex colouring. I believe I have fixed it in 0.4.95. My testing (see image below) indicates that now showVertices = True vs. showVertices = False does not significantly affect rendering time. What is a bit strange is that, several runs of this script has shown that showVertices = True is actually 1 or 2 seconds faster than showVertices-=False! Not sure why this is. Looking forward to the results of your testing. This was conducted on a modest Intel NUC mini computer.

Testing01
wassimj commented 8 months ago

Dear @gaoxipeng, Apologies for the lateness in replying to your query above. The jupyter notebook for the workflow listed above is under notebooks in this github. They are called MEP, MEP01 and MEP02.

gaoxipeng commented 8 months ago

Dear @wassimj , Hello, the issue with showVertices has been resolved, and using Topology.AddApertures(cp, hole, subTopologyType="face") also addressed my questions regarding Graph. Thank you for the fixes and guidance👍.

gaoxipeng commented 7 months ago

Dear @wassimj , Hello, I set a dictionary for one of two intersecting edges. After grouping them into a cluster and using SelfMerge, they separate at the intersection vertex into four short edges, but only one of them carries the dictionary. I think there should be two edges carrying the dictionary. Is it possible to have the results of SelfMerge carry dictionaries based on their sources?

from topologicpy.Vertex import Vertex
from topologicpy.Edge import Edge
from topologicpy.Cluster import Cluster
from topologicpy.Plotly import Plotly
from topologicpy.Topology import Topology
from topologicpy.Dictionary import Dictionary

e1 = Edge.ByStartVertexEndVertex(Vertex.ByCoordinates(0, 0, 0), Vertex.ByCoordinates(10, 0, 0))
e2 = Edge.ByStartVertexEndVertex(Vertex.ByCoordinates(5, 5, 0), Vertex.ByCoordinates(5, -5, 0))

d = Dictionary.ByKeyValue('name', 'wall')
e1 = Topology.SetDictionary(e1, d)
es = Cluster.ByTopologies([e1, e2])

es = Topology.SelfMerge(es)
print(es)
print(Topology.Edges(es))

for e in Topology.Edges(es):
    print(Dictionary.Values(Topology.Dictionary(e)))
wassimj commented 7 months ago

The variety of possibilities when doing boolean operations is too great to manage dictionary transfer automatically. I am actually surprised there is still a dictionary stored in one of the edges. Instead, I suggest you manage the transfer of dictionaries manually through Topology.TransferDictionariesBySelectors. That said, I can see that creating a Cluster.ByTopologies could easily merge all the dictionaries from the input topologies into one dictionary assigned to the cluster. Additionally, Topology.SelfMerge(topology) could easily copy the dictionary from the input topology to the output topology since both are single object. I will implement a transferDictionary boolean flag for both methods in the next release.

gaoxipeng commented 7 months ago

Dear @wassimj, Hello,The current version of Topology.ExportToOBJ cannot correctly handle concave parts of the shape, resulting in the error shown in the picture.

from topologicpy.Vertex import Vertex
from topologicpy.Face import Face
from topologicpy.Topology import Topology

v1 = Vertex.ByCoordinates(0, 0, 0)
v2 = Vertex.ByCoordinates(0, 200, 0)
v3 = Vertex.ByCoordinates(200, 200, 0)
v4 = Vertex.ByCoordinates(200, 400, 0)
v5 = Vertex.ByCoordinates(400, 400, 0)
v6 = Vertex.ByCoordinates(400, 200, 0)
v7 = Vertex.ByCoordinates(600, 200, 0)
v8 = Vertex.ByCoordinates(600, 0, 0)

f = Face.ByVertices([v1, v2, v3, v4, v5, v6, v7, v8])
Topology.ExportToOBJ(f, r'D:\Desktop\0329.obj', overwrite=True)

image I tried modifying the Topology.OBJString function, not using Topology.Geometry, but using the triangulateFaceGeometry function to obtain the triangulated face indices, and it seems to have produced the correct result. I do not know if there will be additional errors in this modification, looking forward to your testing

    def OBJString(topology, transposeAxes=True, mantissa=6, tolerance=0.0001):
        """
        Returns the Wavefront string of the input topology. This is very experimental and outputs a simple solid topology.

        Parameters
        ----------
        topology : topologic.Topology
            The input topology.
        transposeAxes : bool , optional
            If set to True the Z and Y coordinates are transposed so that Y points "up"
        mantissa : int , optional
            The desired length of the mantissa. The default is 6.
        tolerance : float , optional
            The desired tolerance. The default is 0.0001.

        Returns
        -------
        str
            The Wavefront OBJ string of the input topology

        """
        from topologicpy.Helper import Helper
        from topologicpy.Vertex import Vertex
        from topologicpy.Face import Face

        def triangulateFaceGeometry(topology, mantissa=mantissa):
            def triangulateFace(face):
                faceTriangles = []
                for i in range(0, 5, 1):
                    try:
                        _ = topologic.FaceUtility.Triangulate(face, float(i) * 0.1, faceTriangles)
                        return faceTriangles
                    except:
                        continue
                faceTriangles.append(face)
                return faceTriangles

            vertices = []
            faces = []

            if topology is None:
                return {"vertices": None, "faces": None}

            topVerts = []
            if topology.Type() == 1:  # input is a vertex, just add it and process it
                topVerts.append(topology)
            else:
                _ = topology.Vertices(None, topVerts)

            # Process vertices
            for aVertex in topVerts:
                coords = Vertex.Coordinates(aVertex, mantissa=mantissa)
                if coords not in vertices:
                    vertices.append(coords)

            # Process faces
            topFaces = []
            if topology.Type() == 8:  # Input is a Face, just add it and process it
                topFaces.append(topology)
            elif topology.Type() > 8:
                _ = topology.Faces(None, topFaces)

            for aFace in topFaces:
                triFaces = triangulateFace(aFace)
                for aTriFace in triFaces:
                    # Obtain the vertices for each triangular face
                    faceVertices = []
                    _ = aTriFace.Vertices(None, faceVertices)
                    faceIndices = []
                    for aVertex in faceVertices:
                        coords = Vertex.Coordinates(aVertex, mantissa=mantissa)
                        if coords in vertices:
                            faceIndices.append(vertices.index(coords) + 1)  # OBJ indices are 1-based
                        else:
                            vertices.append(coords)
                            faceIndices.append(len(vertices))
                    if len(faceIndices) == 3:
                        faces.append(faceIndices)

            return {"vertices": vertices, "faces": faces}

        if not isinstance(topology, topologic.Topology):
            print("Topology.ExportToOBJ - Error: the input topology parameter is not a valid topology. Returning None.")
            return None

        lines = []
        version = Helper.Version()
        lines.append("# topologicpy "+version)
        d = triangulateFaceGeometry(topology, mantissa=mantissa)
        vertices = d['vertices']
        faces = d['faces']
        tVertices = []
        if transposeAxes:
            for v in vertices:
                tVertices.append([v[0], v[2], v[1]])
            vertices = tVertices
        for v in vertices:
            lines.append("v "+str(v[0])+" "+str(v[1])+" "+str(v[2]))
        for f in faces:
            line = "f"
            for j in f:
                line = line+" "+str(j)
            lines.append(line)
        finalLines = lines[0]
        for i in range(1,len(lines)):
            finalLines = finalLines+"\n"+lines[i]
        return finalLines

The Topology.ByOBJPath cannot be correctly created because faces with more than three points do not meet the requirements for forming faces in topologicpy. Below are the test results using a Blender monkey head obj file. image

wassimj commented 7 months ago

Dear @gaoxipeng, Thank you for finding these bugs. I believe I have addressed all of them in the new version of topologicpy (v. 0.4.96). Kindly test and let me know if indeed they are solved. Here is Lucy in full: :)

Lucy
wassimj commented 7 months ago

And here is the T-shape. I offseted the original face to create a hole just to make sure it all works fully.

t_shape
wassimj commented 7 months ago

Just to note that any imported .OBJ will be triangulated automatically for it to work.

gaoxipeng commented 7 months ago

Dear @wassimj, Thank you for your rocket-fast fix, the issues regarding obj have all been resolved, but I still don't know how to keep the dictionary while splitting edges. Could you possibly give me a simple example of how to use Topology.TransferDictionariesBySelectors🫡?

wassimj commented 7 months ago

Dear @gaoxipeng, Please try this code. This is does not use selectors. I will demo that in a different code.

# Transferring the dictionary of the parent to the children
# Step 1: Create an Edge
e = Edge.Line(length=10)
# Step 2: Create and assign a dictionary to the edge
d = Dictionary.ByKeyValue("id", "edge 01")
e = Topology.SetDictionary(e,d)
# Step 3: Create a slicing tool (cluster of vertices in this case)
v1 = Vertex.ByCoordinates(-2.5,0,0)
v2 = Vertex.ByCoordinates(0,0,0)
v3 = Vertex.ByCoordinates(2.5,0,0)
cluster = Cluster.ByTopologies([v1,v2,v3])
# Step 4: Slice the edge
e = Topology.Slice(e, cluster)
# Step 5: We will assume that we don't know that the edges came from this parent edge. We will test each.
edges = Topology.Edges(e) # Get a list of edges
for edge in edges: # Loop through each of the edges
    c = Topology.Centroid(edge) # Get the edge's centroid
    if Vertex.IsInternal(c, e): # Test if the centroid is inside the parent edge. You might want to test start and end vertices instead.
        edge = Topology.SetDictionary(edge, d) # If it is inside, then copy over the parent dictionary. You might want to merge dictionaries instead if the child edge already has a dictionary as not to lose it.
# Step 6: Verify that the dictionary was copied to the children edges
for edge in edges:
    d2 = Topology.Dictionary(edge)
    print(Dictionary.Keys(d2), Dictionary.Values(d2))
gaoxipeng commented 7 months ago

Dear @wassimj, I attempted to use Topology.Intersect on non-intersecting wire and edge, expecting it to return None. However, it returned a cluster containing four vertices.

from topologicpy.Vertex import Vertex
from topologicpy.Edge import Edge
from topologicpy.Wire import Wire
from topologicpy.Topology import Topology

w = Wire.Rectangle()
e = Edge.ByStartVertexEndVertex(Vertex.ByCoordinates(5, 5, 0), Vertex.ByCoordinates(10, 0, 0))

print(Topology.Intersect(w, e))
wassimj commented 7 months ago

Hi @gaoxipeng , Thank you for catching this! It is was an incomplete implementation because I recently had to fix Topology.Intersect (because the C++ core code is faulty, so had to circumvent it and do it all in python). Sadly, it is much slower now, but hopefully more robust. The error you got was because I forgot to test adge vs. wire, so it reverted to using the standard C++ function which is faulty. I have not fixed this in version 0.4.97. Please download and test. Thanks as always for your sharp bug hunting! :)

gaoxipeng commented 7 months ago

Dear @wassimj , I attempted to form a cluster using elements like faces, shells, cells, etc., and then exported them as an OBJ file. However, some faces were lost, which may have been caused by Topology.Triangulate. Additionally, I previously had some data that, after using SelfMerge due to precision issues, resulted in some faces with extremely small areas that still could not be triangulated when using Topology.Show. I look forward to your testing. :)

from topologicpy.Topology import Topology

building = Topology.ByBREPPath(r'D:\Desktop\1.brep')
print(building)
Topology.ExportToOBJ(building, path=r'D:\Desktop\1.obj')

image 1.zip

wassimj commented 6 months ago

I can confirm that once I triangulate this geometry, the roof disappears! Will debug. Thanks for finding this!

gaoxipeng commented 6 months ago

Dear @wassimj , Hello, after testing, the issue regarding triangulation has been resolved. Thank you for your fix. Additionally, the current Edge.IsCollinear function returns whether two edges are adjacent and in the same linear direction. In my previous work, there was a step where I needed to determine if two lines were in the same linear direction, but there might be a distance between them. My previous approach was to check if the slope (k) and intercept (b) of their lines were equal within a certain threshold. However, for edges that are close but not perpendicular, this resulted in a very large intercept, making comparison impossible. The current approach involves using one of the edges to derive the line equation and checking if the distance of the two points from the other edge to this line is close to 0. I'm not sure if this is useful or if there's a simpler method. Also, I have only considered edges on a 2D plane. I look forward to your testing. image

    def are_collinear(edge1, edge2, tolerance=0.01):
        """
        Determine if two edges are collinear by directly computing and checking
        if both endpoints of the second edge are close to the line defined by the first edge.
        """
        # Calculate coefficients A, B, C from edge1
        start1 = edge1.StartVertex()
        end1 = edge1.EndVertex()
        A = end1.Y() - start1.Y()
        B = -(end1.X() - start1.X())
        norm = np.sqrt(A ** 2 + B ** 2)
        A /= norm
        B /= norm
        C = -(A * start1.X() + B * start1.Y())

        # Calculate perpendicular distance for start vertex of edge2
        start_vertex_edge2 = edge2.StartVertex()
        x0, y0 = start_vertex_edge2.X(), start_vertex_edge2.Y()
        distance_start = abs(A * x0 + B * y0 + C)

        # Calculate perpendicular distance for end vertex of edge2
        end_vertex_edge2 = edge2.EndVertex()
        x0, y0 = end_vertex_edge2.X(), end_vertex_edge2.Y()
        distance_end = abs(A * x0 + B * y0 + C)
        print(distance_start, distance_end)

        # Check if both distances are within tolerance
        return distance_start < tolerance and distance_end < tolerance
wassimj commented 6 months ago

@gaoxipeng Sorry for the delayed response. Have you tried Edge.IsParallel? Does that work for you?

wassimj commented 6 months ago

I am closing this issue since I have not heard back in a few weeks. Feel free to re-open if you are still facing issues.

gaoxipeng commented 6 months ago

Dear @wassimj ,

I'm so sorry for not seeing your reply from three weeks ago. In Edge.IsParallel, the comparison is done through Edge.Angle, which can be used to determine the relationship among edges ①/②/③ and ④. Edge.IsCollinear is done by comparing Edge.Angle and the distance between vertices, which can be used to determine edges ① and ② as parallel and adjacent to each other. The function are_collinear I uploaded earlier is used to determine if two edges are on the same line; they might not be adjacent, such as ① and ③. This determination might just be a personal need and has already been resolved.🫡

image

wassimj commented 6 months ago

@gaoxipeng Thank you for the explanation! This has now been resolved in v0.7.2

IsCollinear
gaoxipeng commented 6 months ago

Dear @wassimj , Thank you for your testing and additions. Previously, the IsCollinear function determined whether lines were parallel and adjacent. Now, it checks if points are collinear in a 2D plane. The two kinds of logic serve different purposes, which may affect functions that use this function, such as Wire.ByOffset and Wire.RemoveCollinearEdges. If these functions need to be called in 3D space, they may fail and may need to be modified to support 3D space.

from topologicpy.Edge import Edge
from topologicpy.Vertex import Vertex
from topologicpy.Topology import Topology
import numpy as np

def IsCollinear(edgeA, edgeB, mantissa: int = 6, tolerance: float = 0.0001) -> bool:

    # Get start and end points of the first edge
    start_a = Edge.StartVertex(edgeA)
    end_a = Edge.EndVertex(edgeA)
    start_a_coords = np.array([Vertex.X(start_a), Vertex.Y(start_a),
                               Vertex.Z(start_a)])
    end_a_coords = np.array(
        [Vertex.X(end_a, mantissa=mantissa), Vertex.Y(end_a, mantissa=mantissa), Vertex.Z(end_a, mantissa=mantissa)])

    # Calculate the direction vector of the first edge
    direction_a = end_a_coords - start_a_coords

    # Normalize the direction vector
    norm_a = np.linalg.norm(direction_a)
    direction_a /= norm_a

    # Function to calculate perpendicular distance from a point to the line defined by a point and direction vector
    def distance_from_line(point, line_point, line_dir):
        point = np.array([Vertex.X(point, mantissa=mantissa), Vertex.Y(point, mantissa=mantissa),
                          Vertex.Z(point, mantissa=mantissa)])
        line_point = np.array(line_point)
        diff = point - line_point
        cross_product = np.cross(diff, line_dir)
        distance = np.linalg.norm(cross_product) / np.linalg.norm(line_dir)
        return distance

    # Get start and end points of the second edge
    start_b = Edge.StartVertex(edgeB)
    end_b = Edge.EndVertex(edgeB)

    # Calculate distances for start and end vertices of the second edge to the line defined by the first edge
    distance_start = distance_from_line(start_b, start_a_coords, direction_a)
    distance_end = distance_from_line(end_b, start_a_coords, direction_a)

    # Check if both distances are within tolerance
    return bool(distance_start < tolerance) and bool(distance_end < tolerance)

v1 = Vertex.ByCoordinates(0, 0, 0)
v2 = Vertex.ByCoordinates(1, 1, 1)
v3 = Vertex.ByCoordinates(2, 2, 2)
v4 = Vertex.ByCoordinates(3, 3, 300)

e1 = Edge.ByStartVertexEndVertex(v1, v2)
e2 = Edge.ByStartVertexEndVertex(v3, v4)
# e2 = Topology.Translate(e2, z=1)
print(IsCollinear(e1, e2))
print(Edge.IsCollinear(e2, e2))
wassimj commented 5 months ago

Dear @gaoxipeng, Thank you again for your diligence. I have now updated the code with your suggestions. Can you please check version 0.7.4 or later and let me know if it meets expecations on 2D and 3D cases? Thanks!

gaoxipeng commented 5 months ago

Dear @wassimj , Hello, the current function is correct,Thank you for your recognition. but there are some details to consider. Specifically, start_a_coords = np.array([Vertex.X(start_a), Vertex.Y(start_a), Vertex.Z(start_a)]) should also take into account the mantissa, which was an oversight on my part😵‍💫. Additionally, using Edge.Length(edgeA) < tolerance ensures that the two vertices of the edge are different. In what situations would line_dir_norm == 0 occur?

wassimj commented 5 months ago

I’m very bad at propagating tolerance and mantissa through functions. Will include that in next release. My professor instilled in me to never divide without checking for zero in the denominator. So I do that without considering if it can or cannot be zero. Again, I am not consistent with that and was going to do a universal check on all divisions in the code and add a check for zero