points with connection matrix to solid?

Need help, or want to share a macro? Post here!
User avatar
awkonradi
Posts: 21
Joined: Thu Feb 01, 2018 10:25 pm

points with connection matrix to solid?

Postby awkonradi » Tue Jun 12, 2018 12:11 am

OS: Windows 10
Word size of OS: 64-bit
Word size of FreeCAD: 64-bit
Version: 0.17.13522 (Git)
Build type: Release
Branch: releases/FreeCAD-0-17
Hash: 3bb5ff4e70c0c526f2d9dd69b1004155b2f527f2
Python version: 2.7.14
Qt version: 4.8.7
Coin version: 4.0.0a
OCC version: 7.2.0
Locale: English/UnitedStates (en_US)

Hello All,

Would any of you be able to point me towards code that will accomplish the following?

1) Import points that are associated with a connection matrix.

2) Based on the connection matrix, create edges, and then faces, and then a solid from the points.

Understandably, this would report an error, if the points and the connection matrix did not define a unique solid.

Thanks!

Andrei, the 52-year-old organic chemist
User avatar
microelly2
Posts: 3945
Joined: Tue Nov 12, 2013 4:06 pm
Contact:

Re: points with connection matrix to solid?

Postby microelly2 » Wed Jun 13, 2018 8:59 am

if your data are in a common format like stl, obj .. you can simple import the data by default methods.
Can you upload an example datafile to see how your connection information is stored.
DrBwts
Posts: 101
Joined: Sun Oct 26, 2014 5:23 pm

Re: points with connection matrix to solid?

Postby DrBwts » Wed Jun 13, 2018 5:05 pm

As long as the points/vertices associated with the connectivity matrix have coordinates and you have a simple graph (ie no loops from a vertex back to itself or more then one edge connecting the same pair of vertices), then there should be no problem.

How big are the graphs?
User avatar
awkonradi
Posts: 21
Joined: Thu Feb 01, 2018 10:25 pm

Re: points with connection matrix to solid?

Postby awkonradi » Thu Jun 14, 2018 12:49 am

Hello DrBwts and microelly2,

I have attached an example points set and connection matrix. Of course, I would reformat this to match existing code. I edited this by hand, so maybe this does not represent a unique solid, but I think this represents a "house shaped" solid. In any case, this illustrates a small points set and connection matrix.

In the near term, I would be satisfied with handling ten points. But, if code exists, then I might attempt application to thousands of points.

I am very grateful for you help.

Best!

Andrei
Attachments
example connection matrix.csv
(702 Bytes) Downloaded 9 times
User avatar
microelly2
Posts: 3945
Joined: Tue Nov 12, 2013 4:06 pm
Contact:

Re: points with connection matrix to solid?

Postby microelly2 » Thu Jun 14, 2018 8:34 am

If you can create a file with your points data and connections in a formal like vrml
you can load it into the FreeCAd 3D scene

http://www.c3.hu/cryptogram/vrmltut/part5.html
(here you find the indexed faces set and the indexed line set too)

Code: Select all

#VRML V2.0 utf8
#IndexedFaceSet example: a pyramid
Shape {
	appearance Appearance{
		material Material { 
			diffuseColor     1 0 0 #simple red
			}
		}
	geometry IndexedFaceSet {
		coord Coordinate {
                    point [
				# bottom 
				-1.0 -1.0 1.0,	#vertex 0
				1.0 -1.0 1.0,	#vertex 1
				1.0 -1.0 -1.0,	#vertex 2
				-1.0 -1.0 -1.0,	#vertex 3
				# top
				0.0 1.0 0.0		#vertex 4
                    ]
                }
		coordIndex [
			#bottom square
			 0, 3, 2, 1, 0, -1,
			#side1
			 0, 1, 4, -1,
			#side2
			 1, 2, 4, -1,
			#side3
			 2, 3, 4, -1,
			#side4
			 3, 0, 4, -1,
			]
			
	}
}

Code: Select all

#VRML V2.0 utf8
#IndexedLineSet example
Shape {
	geometry IndexedLineSet {
		coord Coordinate {
                    point [
				-1.0 -1.0 0.0,	#vertex 0
				1.0 1.0 0.0,	#vertex 1
				1.0 -1.0 0.0,	#vertex 2
                    ]
                }
		color Color {
                    color [
                        1.0 0.0 0.0,	#red
				0.0 1.0 0.0,	#green
                        0.0 0.0 1.0,	#blue
                    ]
            }
		coordIndex [
			#red line
			 0, 1, -1,
			#green line
			 1, 2, -1,
			#blue line
			 2, 0, -1
			]
		colorIndex [
			0, 1, 2
			]
			
	}
}
using a connectivity matrix may work for small datasets but if you have 1000 points the matrix has a size 1000 000.
so the better way is to describe the lines or polygons as sequences of point indexes.
User avatar
awkonradi
Posts: 21
Joined: Thu Feb 01, 2018 10:25 pm

Re: points with connection matrix to solid?

Postby awkonradi » Thu Jun 14, 2018 12:56 pm

Hi microelly2,

Thank you very much. I will explore this.

Very best,

Andrei
TheMarkster
Posts: 544
Joined: Thu Apr 05, 2018 1:53 am

Re: points with connection matrix to solid?

Postby TheMarkster » Fri Jun 15, 2018 5:56 am

It's an interesting problem. I can read your csv and make some lines, but coming up with an algorithm to sort them into wires, faces, and then into solids has eluded me to this point. This might be enough to get you started though.

I think your original csv has a couple wires crossed (unless I did something wrong, quite possible.) I modified it as such:
example connection matrix2.csv
(702 Bytes) Downloaded 9 times
But the house still comes out a bit askew. Maybe there's a bug in the code or maybe it's in the csv.
csv.png
csv.png (4.63 KiB) Viewed 261 times

Code: Select all

import FreeCAD
import csv
from PySide import QtCore, QtGui
import Part, Draft


if not App.ActiveDocument:
    doc = App.newDocument()

name= QtGui.QFileDialog.getOpenFileName(QtGui.QApplication.activeWindow(),u'Open CSV File','*.csv')[0]

if not name:
    raise StandardError('No file selected.')

fields = []
rows = []
 
# reading csv file
with open(name, 'r') as csvfile:
    # creating a csv reader object
    csvreader = csv.reader(csvfile)
     
    # extracting field names through first row
    fields = csvreader.next()
 
    # extracting each data row one by one
    for row in csvreader:
        rows.append(row)
 

def getPoint(idx):
    if len(rows) < idx-1:
        raise StandardError('Index out of bounds.')
    row = rows[idx]
    return App.Vector(float(row[1]),float(row[2]),float(row[3]))

def isConnected(idx1,idx2):
    bConnected=True
    if len(rows)<idx1-1 or len(fields)<idx2-1:
        raise StandardError('Index out of bounds.')

    if rows[idx1][idx2+4]=='0' or rows[idx1][idx2+4]=='self':
        bConnected = False
    return bConnected

def getNumPoints():
    return len(fields)-4



numPoints = getNumPoints()
points = []

for ii in range(0,numPoints):
    points.append(getPoint(ii))


connections = [] 
for ii in range(0,numPoints):
    connection = []
    for jj in range(0,numPoints):
        if ii != jj and isConnected(ii,jj):
            connection.append(jj)
    connections.append(connection)




lines=[]
linePoints=[]

for ii in range(0,len(points)):
    for jj in range(0,len(points)):
        if ii!= jj and isConnected(ii,jj):
            lines.append(Draft.makeLine(getPoint(ii),getPoint(jj)))
            linePoints.append((ii,jj))
            FreeCAD.Console.PrintMessage("pt"+str(ii+1)+"-->"+"pt"+str(jj+1)+"\n")


for ii in range(0,len(points)):
    p = App.ActiveDocument.addObject("Part::Vertex","pt"+str(ii+1))
    p.X=points[ii][0]
    p.Y=points[ii][1]
    p.Z=points[ii][2]
    p.Label = "pt"+str(ii+1)

App.ActiveDocument.recompute()


I was thinking a brute force approach would be to try all the paths (imagine an ant traveling from point A to point B ... eventually back to point A), for example, by just trying to make a wire or face out of them within a try, except block. If it fails it would be because all the points weren't coplaner on that wire. The ones that succeed would be the valid faces, which could then be formed into a shell and then a solid. You can also end up with multiple solids, for example, with the house and roof being two different solids.

The code makes 2 lines (A to B and again B to A), so there are twice as many was what's actually needed. I was thinking of using the lines back for testing which paths were making it back to the original starting point.

isConnected() can tell you if the 2 points are connected in the matrix

connections provides info on how the points are connected:

Code: Select all

[[1, 2, 4], [0, 3, 5], [0, 3, 4, 6], [1, 2, 5, 7], [0, 2, 5, 8], [1, 3, 4, 9], [2, 7, 8], [3, 6, 9], [4, 6, 9], [5, 7, 8]]
As an example connections[0] = [1,2,4] means point 0 (pt1) connections to points 1,2, and 4 (pt2, pt3, and pt5)

isConnected(0,2) should return True.
Attachments
csv.FCMacro.py
(1.95 KiB) Downloaded 6 times
User avatar
microelly2
Posts: 3945
Joined: Tue Nov 12, 2013 4:06 pm
Contact:

Re: points with connection matrix to solid?

Postby microelly2 » Fri Jun 15, 2018 7:25 am

A good way to store informations on vertexes and edges is the python module networkx https://networkx.github.io/

there are lots of algorithms implemented which help to find closed pathes to detect faces.
I use networkx and I use sometimes neo4j as graph database to store larges sets of data
https://neo4j.com/
https://youtu.be/OWHNSkN00UY
TheMarkster
Posts: 544
Joined: Thu Apr 05, 2018 1:53 am

Re: points with connection matrix to solid?

Postby TheMarkster » Fri Jun 15, 2018 7:45 pm

Version 2.0

Works as long as there are only 3-sided and 4-sided faces. 5-sided faces (or more) will most likely fail (untested).

My algorithm to flesh out the faces is to create triangles from lines that are connected at all ends to each other and 4-sided faces
where 4 lines are connected together.

Passes Path -> Check Geometry test. I also tested by cutting a cylinder out of the house. Aside from a leaking roof it seems to be okay, but you can see the insides of the faces through the hole, so there's probably still something not quite right.

Code: Select all

import FreeCAD
import csv
from PySide import QtCore, QtGui
import Part, Draft


if not App.ActiveDocument:
    doc = App.newDocument()

name= QtGui.QFileDialog.getOpenFileName(QtGui.QApplication.activeWindow(),u'Open CSV File','*.csv')[0]
#name="C:/Users/mwganson/Downloads/example connection matrix2.csv"
if not name:
    raise StandardError('No file selected.')

fields = []
rows = []
 
# reading csv file
with open(name, 'r') as csvfile:
    # creating a csv reader object
    csvreader = csv.reader(csvfile)
     
    # extracting field names through first row
    fields = csvreader.next()
 
    # extracting each data row one by one
    for row in csvreader:
        rows.append(row)
 

def getPoint(idx):
    if len(rows) < idx-1:
        raise StandardError('Index out of bounds.')
    row = rows[idx]
    return App.Vector(float(row[1]),float(row[2]),float(row[3]))

def isConnected(idx1,idx2):
    bConnected=True
    if len(rows)<idx1-1 or len(fields)<idx2-1:
        raise StandardError('Index out of bounds.')

    if rows[idx1][idx2+4]=='0' or rows[idx1][idx2+4]=='self':
        bConnected = False
    return bConnected

def getNumPoints():
    return len(fields)-4

def getConnectingLines(line):
    """search the lines list for lines that connect to this line and return them as a list"""
    connectors = []
    for l in lines:
        if l.Start == line.Start or l.End == line.Start or l.Start == line.End or l.End == line.End:
            if not isSameLine(l,line):
                connectors.append(l)
    return connectors

def isSameLine(line1,line2):
    """returns True if these are the same lines, even if starts and ends are reversed"""
    if line1.Start == line2.Start and line1.End == line2.End:
        return True
    elif line1.End == line2.Start and line1.Start == line2.End:
        return True
    return False
def isConnectedLines(line,lineList,oneOnly=False): #bad grammar:P
    """if not oneOnly (for triangles) returns true if line is connected at at least one end to every line in lineList
       if oneOnly (for 4Legs) returns true if line is connected to any line in lineList"""
    if not oneOnly: #used for triangles
        for ll in lineList:
            if line.Start != ll.Start and line.Start != ll.End and line.End != ll.Start and line.End != ll.End:
                return False
        return True
    else: #used for 4-legs
        for ll in lineList:
            if line.Start == ll.Start or line.Start == ll.End or line.End == ll.Start or line.End == ll.End:
                return True
        return False

def isTriangle(lineList):
    """returns true if each line is connected to each of the other lines, but only one end per line (not a fork or a tee)"""
    if len(lineList)!=3:
        return False
    line1 = lineList[0]
    startCount = 0
    endCount = 0
    for ii in range(1,len(lineList)):
        if line1.Start == lineList[ii].Start or line1.Start == lineList[ii].End:
            startCount+=1
        if line1.End == lineList[ii].Start or line1.End == lineList[ii].End:
            endCount+=1
    if startCount == endCount:
        return True
    else:
        return False

def getUnconnectedEnds(twoLeg):
    """returns a list of 2 points that are not connected to each other"""
    def addPt(pt):
        if not pt in pts:
            pts.append(pt)
        else: #remove the common point
            pts.remove(pt)
    pts=[]
    addPt(twoLeg[0].Start)
    addPt(twoLeg[0].End)
    addPt(twoLeg[1].Start)
    addPt(twoLeg[1].End)

    return pts
    


def isFourLeg(twoLeg1,twoLeg2):
    """returns true if these twoLegs are connected to form a 4-edged face"""
    if not isConnectedLines(twoLeg1[0],twoLeg2,oneOnly=True) or not isConnectedLines(twoLeg1[1],twoLeg2,oneOnly=True):
        return False
    if twoLeg1==twoLeg2:
        return False
    unconnected1 = getUnconnectedEnds(twoLeg1)
    unconnected2 = getUnconnectedEnds(twoLeg2)
    for uc in unconnected1:
        if not uc in unconnected2:
            return False

    return True

def makeFace(lineList):
    partLines=[]
    face = None
    for line in lineList:
        partLines.append(Part.makeLine(line.Start,line.End))
    partEdges = []
    for pl in partLines:
        partEdges.append(Part.Edge(pl))
    try:
        pw = Part.Wire(partEdges)
    except:
        FreeCAD.Console.PrintMessage('Exception creating Part.Wire(partEdges)\n')
    try:
        face = Draft.makeWire(pw,closed=True,face=True)
        Draft.autogroup(pw)

    except:
        FreeCAD.Console.PrintMessage('Exception creating Part.Face(pw)\n')
    return face

numPoints = getNumPoints()
points = []

for ii in range(0,numPoints):
    points.append(getPoint(ii))


connections = [] 
for ii in range(0,numPoints):
    connection = []
    for jj in range(0,numPoints):
        if ii != jj and isConnected(ii,jj):
            connection.append(jj)
    connections.append(connection)




lines=[]
linePoints=[]

for ii in range(0,len(points)):
    for jj in range(ii,len(points)): #changing from 0 to ii removes extra lines
        if ii!= jj and isConnected(ii,jj):
            lines.append(Draft.makeLine(getPoint(ii),getPoint(jj)))
            linePoints.append((ii,jj))
            #FreeCAD.Console.PrintMessage("pt"+str(ii+1)+"-->"+"pt"+str(jj+1)+"\n")



#for ii in range(0,len(points)):
#    p = App.ActiveDocument.addObject("Part::Vertex","pt"+str(ii+1))
#    p.X=points[ii][0]
#    p.Y=points[ii][1]
#    p.Z=points[ii][2]
#    p.Label = "pt"+str(ii+1)

twoLegs = [] #2 of 3 legs needed for triangles
for line in lines:
    twoLeg = getConnectingLines(line)
    for leg in twoLeg:
        if not [line,leg] in twoLegs:
            twoLegs.append(sorted([line,leg]))

triangles = []
toBeRemoved=[]
for tl in twoLegs:
    for line in lines:
        triangle=[]
        if isConnectedLines(line,tl):
            for l in tl:
                if not l in triangle:
                    triangle.append(l)
            if not line in triangle:
                triangle.append(line)
                triangle = sorted(triangle)
            if not triangle in triangles and isTriangle(triangle):
                triangles.append(triangle)
                toBeRemoved.append(tl)

#for tbr in toBeRemoved:
#    twoLegs.remove(tbr) #we were able to build a triangle from existing lines, so remove them

fourLegs = [] #now build some 4-legged structures out of the twoLegs
for tw1 in twoLegs:
    for tw2 in twoLegs:
        fourLeg = []
        if isFourLeg(tw1,tw2):
            for line in tw1:
                if not line in fourLeg:
                    fourLeg.append(line)
            for line in tw2:
                if not line in fourLeg:
                    fourLeg.append(line)
            fourLeg = sorted(fourLeg)
            if not fourLeg in fourLegs and len(fourLeg)==4:
                fourLegs.append(fourLeg)

faces=[]
for four in fourLegs:
    face = makeFace(four)
    if not face in faces:
        faces.append(face)

for tri in triangles:
    face = makeFace(tri)
    if face and not face in faces:
        faces.append(face)

#partFaces = [] #works, but solid fails part -> geometry check because of "ceiling" face not being connect (I think that's the issue, anyway.)
#for face in faces:
#    partFaces.append(face.Shape.Face1)

#shell = Part.Shell(partFaces)
#solid = Part.Solid(shell)
#Part.show(solid)

j = BOPTools.JoinFeatures.makeConnect(name = 'Connect')
j.Objects = faces
j.Proxy.execute(j)
j.purgeTouched()
for obj in j.ViewObject.Proxy.claimChildren():
    obj.ViewObject.hide()

#for face in faces:  #need to keep these DWires as the connect object depends on them
#    App.ActiveDocument.removeObject(face.Label)
for line in lines:
    App.ActiveDocument.removeObject(line.Label)
App.ActiveDocument.recompute()
Attachments
csv(v2).FCMacro.py
(7.59 KiB) Downloaded 8 times
User avatar
awkonradi
Posts: 21
Joined: Thu Feb 01, 2018 10:25 pm

Re: points with connection matrix to solid?

Postby awkonradi » Sat Jun 16, 2018 4:25 pm

Hi TheMarkster,

I am having some success with your code. Will update more completely later. Thank you very much for your help.

Andrei