Organizing/Ordering Points for Polygon

Dimitar_Venkov · July 7, 2021, 2:37pm

Another thing you could try is the “LineLoop.Merge” node from springs. It should act similar to Vikram’s solution:

solamour · July 7, 2021, 3:38pm

Just for fun I used TuneUp to check on all the speeds of these solutions (If performance will be an issue) and you get as follows:

Note: The millisecond execution numbers do jump around a little (+/- 15ms) so take them all with a little grain of salt.

Short answer is they are all awesome solutions

c.poupin · July 8, 2021, 5:25am

a small variant

import sys
import clr
import itertools
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import *

clr.AddReference('RevitAPI')
import Autodesk
from Autodesk.Revit.DB import *
import Autodesk.Revit.DB as DB

clr.AddReference('RevitNodes')
import Revit
clr.ImportExtensions(Revit.GeometryConversion)

def customIntersectAll(*args):
    if sys.implementation.name == 'ironpython':
        for curveA, curveB in itertools.product(*args):
            interResultArray = clr.Reference[IntersectionResultArray]()
            compareResult = curveA.Intersect(curveB, interResultArray)
            if compareResult == SetComparisonResult.Overlap:
                yield(interResultArray.Value[0].XYZPoint )
    else:
        for curveA, curveB in itertools.product(*args):
            outInterResultArrayout = IntersectionResultArray()
            compareResult, interResultArray = curveA.Intersect(curveB, outInterResultArrayout) 
            if compareResult == SetComparisonResult.Overlap:
                yield(interResultArray[0].XYZPoint)

def isParallelOverlap(c1, c2):
    v1 = c1.Direction.Normalize()
    v2 = c2.Direction.Normalize()
    check1 = c1.Intersect(c2) == SetComparisonResult.Equal
    check2 = v1.CrossProduct(v2).IsAlmostEqualTo(XYZ(0, 0, 0))
    return all([check1, check2])

def sortPoint(lstPts, orderPts = []):
    global lstCurveA
    if len(orderPts) == 0:
        orderPts.append(lstPts.pop(0))
    #   
    lstPts.sort(key = lambda x : x.DistanceTo(orderPts[-1]))
    for idx, pta in enumerate(lstPts):
        lineAB = DB.Line.CreateBound(pta, orderPts[-1])
        if any(isParallelOverlap(c, lineAB) for c in lstCurveA):
            orderPts.append(lstPts.pop(idx))
            lineAB.Dispose()
            return sortPoint(lstPts, orderPts)
        
    return [x.ToPoint() for x in orderPts]

lstRvtLines = UnwrapElement(IN[0])
lstCurveA = [x.Location.Curve for x in lstRvtLines]
lstCurveB = lstCurveA[:]
outPoint = []

for pt in customIntersectAll( lstCurveA, lstCurveB):
    if all(not pt.IsAlmostEqualTo(x) for x in outPoint):
        outPoint.append(pt)
        
OUT = sortPoint(outPoint)

see also this post
Organizing/Ordering Points for Polygon - #27 by c.poupin

sovitek · July 8, 2021, 6:57am

A way with nodes, not so stable as @c.poupin, @Vikram_Subbaiah, @Dimitar_Venkov amazing methods but will work in this case…

solamour · July 9, 2021, 2:37pm

This is another option with Nodes Around 65ms, but is caveated: Will only work on the proviso that when you split lines you want to keep the longest one.

Zakim_OrderingPointsForPolygon.dyn (28.9 KB)

zakim · July 11, 2021, 8:19pm

Thank @c.poupin for sharing this solution. It is a great help.
So I finally had sometime to play with it. For some reason, I am getting points out of sequence when one of the edges are long.?!

c.poupin · July 12, 2021, 11:11am

Hello,
because the script searches for the nearest point for each point

you can try this version of python code

import sys
import clr
import itertools
import System
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import *
import Autodesk.DesignScript.Geometry as DS

clr.AddReference('RevitAPI')
import Autodesk
from Autodesk.Revit.DB import *
import Autodesk.Revit.DB as DB

clr.AddReference('RevitNodes')
import Revit
clr.ImportExtensions(Revit.GeometryConversion)


def customIntersectAll(*args):
	if sys.implementation.name == 'ironpython':
		for curveA, curveB in itertools.product(*args):
			interResultArray = clr.Reference[IntersectionResultArray]()
			compareResult = curveA.Intersect(curveB, interResultArray)
			if compareResult == SetComparisonResult.Overlap:
				yield(interResultArray.Value[0].XYZPoint )
	else:
		for curveA, curveB in itertools.product(*args):
			outInterResultArrayout = IntersectionResultArray()
			compareResult, interResultArray = curveA.Intersect(curveB, outInterResultArrayout) 
			if compareResult == SetComparisonResult.Overlap:
				yield(interResultArray[0].XYZPoint)


def isParallelOverlap(c1, c2):
	v1 = c1.Direction.Normalize()
	v2 = c2.Direction.Normalize()
	check1 = c1.Intersect(c2) == SetComparisonResult.Equal
	check2 = v1.CrossProduct(v2).IsAlmostEqualTo(XYZ(0, 0, 0))
	return all([check1, check2]), v1
	
def allVectorsAreParallel(lstPairBool_Vect):
	"""
	check if all vector are parallel
	input Parameter -> [[bool, vector], [bool, vector], ...]
	"""
	lstVect = [v[1] for v in lstPairBool_Vect if v[0]]
	v1 = lstVect.pop(0)
	for v2 in lstVect:
		if not v1.CrossProduct(v2).IsAlmostEqualTo(XYZ(0, 0, 0)):
			return False
	return True

def sortPoint(lstPts, orderPts = []):
	"""
	sort points by intersection/overlap curves
	"""
	global lstCurveA
	if len(orderPts) == 0:
		orderPts.append(lstPts.pop(0))
	# 1st pass  
	lstPts.sort(key = lambda x : x.DistanceTo(orderPts[-1]), reverse = True)
	for idx, pta in enumerate(lstPts):
		lineAB = DB.Line.CreateBound(pta, orderPts[-1])
		lstPairBool_Vect = [isParallelOverlap(c, lineAB) for c in lstCurveA]
		if sum(c[0] for c in lstPairBool_Vect) == 1:
			orderPts.append(lstPts.pop(idx))
			lineAB.Dispose()
			return sortPoint(lstPts, orderPts)
	# 2nd pass  		
	for idx, pta in enumerate(lstPts):
		lineAB = DB.Line.CreateBound(pta, orderPts[-1])
		lstPairBool_Vect = [isParallelOverlap(c, lineAB) for c in lstCurveA]
		if sum(c[0] for c in lstPairBool_Vect)  > 1 and allVectorsAreParallel(lstPairBool_Vect):
			orderPts.append(lstPts.pop(idx))
			lineAB.Dispose()
			return sortPoint(lstPts, orderPts)

	return [x.ToPoint() for x in orderPts]
	
def toList(curves):
	curves = curves if hasattr(curves, '__iter__') else [curves]
	if isinstance(curves[0], DS.Curve):
		return [x.ToRevitType() for x in curves]
	elif hasattr(curves[0],  "Curve"):
		return [x.Curve for x in curves]
	elif hasattr(curves[0],  "Location"):
		return [x.Location.Curve for x in curves]		
	else: return []

lstCurveA = toList(UnwrapElement(IN[0]))
if lstCurveA:
	lstCurveB = lstCurveA[:]
	outPoint = []
	
	for pt in customIntersectAll( lstCurveA, lstCurveB):
		if all(not pt.IsAlmostEqualTo(x) for x in outPoint):
			outPoint.append(pt)
	#			
	OUT = sortPoint(outPoint)

zakim · July 12, 2021, 3:33pm

Thanks @c.poupin for your help and contribution… I have no idea why I am getting an error in this line.

Kulkul · July 12, 2021, 3:35pm

@zakim Connect Directly Elements list. No need to add CurveElement.Curve node.

zakim · July 12, 2021, 4:48pm

Thanks @Kulkul seems to work directly without the CurveElement.Curve node.
What is strange… the original Python script used to work with the [CurveElement.Curve node]…!

For the purpose of my small project, I am collecting the CurveElement.Curve node lines info, perform some cleanup/List action, then I wish to send the CurveElement.Curve node lines to the Python to create the final polygon. Is this possible?

c.poupin · July 12, 2021, 7:40pm

I updated my previous post to be able to use the CurveElement.Curve node

zakim · July 12, 2021, 10:40pm

Thank you very much @c.poupin … it works really well. I have tried different lines/shapes in a small test Revit file. It produced exactly the required Polygon points… Works beautifully … Among other great solutions posted here, I feel this is the suitable one.

Sorry to trouble you with a last question: when I used your Python script inside my overall all project I am working on, the Python does not produce the required list of point to generate the polygon.

Again… Thanks a lot.

c.poupin · July 13, 2021, 3:54pm

Because it’s a bug , the script did not work in some cases (according to the order of the input curves)
I fixed it here

zakim · July 15, 2021, 3:44pm

Thank you @c.poupin for your great help. I really appreciate everyone’s help

Topic		Replies	Views
Point List Order & Distance From Average Lists-Logic revit , geometry , dynamo	2	361	March 30, 2023
Ordering Points Around Perimeter Revit dynamo	3	1148	January 13, 2022
Reorder points Revit revit , dynamo	4	155	May 6, 2024
Ordering point after curve deconstruct polycurve (curtain panel boundaries) Packages dynamo	19	2557	March 21, 2019
Uniting groups of families with polycurves Lists-Logic revit , python	3	416	March 25, 2021

Organizing/Ordering Points for Polygon

Related topics