Programmatically Break Down Complex Shapes into Simple Polygons

Hello all,

I want to start by saying I am not looking for you to complete this assignment for me. I have made some attempts but ultimately have failed very early on in each. I am at a loss for another try. I categorized this under Machine Learning because I feel that is what it would need but I am not sure.

I work in Seattle and have been given a very particular task. The city does not trust Revit or the Architecte to provide the area for FAR (Floor to Area Ratio) diagrams. Developers need to pay the city for each square foot they build. As a result, we need to break down complex shapes into simple 3 and 4 sided polygons so the plan checkers can calculate the area themselves (See image below for example).

Please let me know if you have any ideas.

Thank you,
Steven

Can you post an example shape to work with (ie: the shape above or something similar?). I have a few ideas but nothing is ever as easy as it first appears (as always).

surely those developers would not even dream of fudging the numbers…

how simple does the geometry go ? In your example- it looks rectangles, triangles and sectors.
Is a circle a circle, or 4 sectors, or approximated with triangles ? Is an ellipse approximated with sectors or triangles ?

If you are just after a quick ‘sanity check’ method to check that the claimed numbers are in the right ballpark- perhaps you could generate a grid over each shape and automatically number/count units. For example- if the grid was 10x10’- shape 2 would be approximately 2 1/2 units (24’) by 5 1/2 units (56’)
Add up the full units and the leftover bits equals ~1350 SF

I was thinking a ‘largest inscribed box’ might help break things down, but it may be less effective than an option that starts outside in.

Compare edge to edge to edge to edge and draw boxes between corner points when you have a 90 degree angle, trim that box with the perimeter curves and scale up (or down) a new box as needed. Remove that box from the shape when done and repeat until you can’t fit a box on a set of curves. For remaining curves/ surfaces, triangulate the surface, make 90 degree triangles, and then do the math.

Fails to take into account arcs and Nurbs curves though.

It may be easier for us (and the city) if they requested the layout points of the building shape, and verified the area programmatically. More accurate and helps all parties involved. That or hold development teams accountable for their signed affidavits…

Thanks for taking an interest. Attached is an rvt with a single area plan (shown in the picture below for reference). This is an actual example pulled from one of our past projects. I simplified the view removing all unnecessary elements to this task. By no means is this the only solution.

The Retail (green) area is considered nonchargeable (an incentive for developers to provide public street fronts). @Andrew_Hannell love the sarcasm! We all know developers would never try to overinflate nonchargeable areas.

The overall goal would be to have a Rectangle and right triangles. The city then takes our PDFs and checks the areas by hand. Thus why they want such simple shapes.

In my first example, I did provide a rounded edge but let’s face it buildings are really round so I think we can exclude arches, circles, and ellipses for now. If there were to be one I think it could be managed by hand if the other 90% was automated. Or perhaps could be solved in round two.

@Andrew_Hannell I like where your head is at with the general approximation. I too went there and was turned down. The city wants to be able to come to the exact same number down to the hundredths of a decimal place.

Last night after posting this I looked into converting the flat surfaces into a mesh. I then tried to simplify the mesh but had no luck. It is hard to get a mesh to form rectangles and right triangles. Also when oversimplified the original border was lost. I am not the best with mesh geometry and could be missing something so I figured it was worth noting the idea.

Let me know if you have any further questions.

Complex Shapes to Simple Polygons.rvt (1.6 MB)

1 Like

I stumbled upon this stackoverflow comment which answers a similar problem. I´d like to try it, but it will take me some time to understand the math behind it.

Based on the stackoverflow comment:

  • Create a grid on top of the area, aligned to the longest and an adjacent boundary line
  • Remove lines outside the polygon
  • Remove lines of grid cells that are intersecting the boundary (Bresenham’s line algorithm)
  • Combine remaining cells to larger rectangles

The last point involves more algorithms as described in the SO comment.
I would personally leave it by a grid of squares and combine what is left on the boundaries manually. But I can see how it might save (a lot) of time and it might be worth going down that rabbit hole.

Each of the colors is treated as a unique polygon then… Lemme sketch for a bit…

Likely worth looking for other options as this does NOT look efficient. OpenCV would help, requires Python 3 though.

1 Like

This should do about 75% of the job, I suppose.

Known issues …

  1. Doesn’t work if the slab has openings within
  2. Creates sub divisions as long as there are parallel edges.
  3. Sometimes creates boundaries beyond surface (adjust variable acc01 when this happens)

RectangularDivision.dyn (40.1 KB) (ver 2.8)

def Rect(srf:var[]..[])
{
	srf01 = List.Flatten(srf.Explode(),-1);
	srf02 = List.FilterByBoolMask(srf01,List.Count(srf01.Vertices.PointGeometry<1>)>3)["in"];
	crv00 = srf02.PerimeterCurves();
	pcv01 = PolyCurve.ByJoinedCurves(crv00);
	vtx01 = List.Flatten(srf02.Vertices.PointGeometry,-1);

	//Offset Perimter Curves Outwards
	seg01 = 100;
	off01 = List.Flatten(crv00,-1)[0].Length/seg01;
	pcv02 = pcv01<1>.Offset([off01,-off01]);
	pcv03 = List.FirstItem(pcv02<1>);
	pcv04 = List.LastItem(pcv02<1>);
	pcv05 = pcv03.Length > pcv04.Length ? pcv03 : pcv04;

	//Inward Vectors
	acc01 = 8;
	pnt01 = crv00<1><2>.PointAtParameter((0..1..#acc01));
	vct00 = crv00<1><2>.NormalAtParameter((0..1..#acc01));
	vct01 = List.GetItemAtIndex(vct00<1><2>,Math.Floor(acc01/2));
	pnt02 = List.Flatten(pnt01.Project(pcv05,vct01)<1><2>,-1);
	bln01 = List.AllTrue((pnt01.DistanceTo(pnt02)!=off01)<1><2>);
	vct02 = bln01 ? vct01 : vct01.Reverse();

	//Rectangle aligned to Surface Boundaries
	pnt03 = List.Flatten(pnt01.Project(pcv05,vct02)<1><2>,-1);
	dis01 = Math.Round(pnt01.DistanceTo(pnt03)-off01,6);
	bln02 = List.DropItems(dis01<1><2>,-1)==List.DropItems(dis01<1><2>,1);
	fil01 = List.IndexOf(bln02<1><2>,true);
	fil02 = fil01==-1 ? acc01 : fil01;
	fil03 = List.DropItems(bln02<1><2>,fil02<1><2>);
	fil04 = List.IndexOf(fil03<1><2>,false);
	fil05 = fil04 == -1 ? acc01-1 : fil04+1;
	fil06 = List.DropItems(pnt01<1><2>,fil02<1><2>);
	pnt04 = List.TakeItems(fil06<1><2>,fil05<1><2>);
	fil07 = List.DropItems(pnt03<1><2>,fil02<1><2>);
	pnt05 = List.TakeItems(fil07<1><2>,fil05<1><2>);
	lin01 = List.Clean(Line.ByStartPointEndPoint(pnt04,pnt05).ExtendEnd(-off01),false);
	bln03 = List.Count(List.RemoveIfNot(lin01.Intersect(pcv01)<1><2><3>,"Point")<1><2><3>)>2;
	lin02 = List.FilterByBoolMask(lin01,bln03)["out"];
	lin03 = List.FirstItem(lin02<1><2>);
	lin04 = List.LastItem(lin02<1><2>);
	vct03 = Vector.ByTwoPoints(lin03.PointAtParameter(0.5),lin04.PointAtParameter(0.5));
	vct04 = Vector.ByTwoPoints(lin04.PointAtParameter(0.5),lin03.PointAtParameter(0.5));

	//Shift edge towards Closest Vertex
	pnt06 = List.Transpose(vtx01<3>.Project(lin03<1><2>,vct03<1><2>)<1>);
	bln04 = DSCore.Object.IsNull(List.Count(pnt06<1><2><3>)>0)?true:List.Count(pnt06<1><2><3>)>0;
	dis02 = lin03.DistanceTo(List.FilterByBoolMask(vtx01,bln04<1><2>)["in"]);
	lin05 = lin03.Translate(vct04,List.MinimumItem(dis02));
	pnt07 = List.Transpose(vtx01<3>.Project(lin04<2><1>,vct04<2><1>)<1>);
	bln05 = DSCore.Object.IsNull(List.Count(pnt07<1><2><3>)>0)?true:List.Count(pnt07<1><2><3>)>0;
	dis03 = lin04.DistanceTo(List.FilterByBoolMask(vtx01,bln05<1><2>)["in"]);
	lin06 = lin04.Translate(vct03,List.MinimumItem(dis03));

	//Largest Rectangle
	lin07 = List.Transpose([lin05,lin06]);
	edg01 = List.FirstItem(lin07<1>);
	edg02 = List.LastItem(lin07<1>);
	pnt08 = List.Transpose(List.Transpose([edg01.StartPoint,edg01.EndPoint,edg02.EndPoint,edg02.StartPoint])<1>);
	rct01 = Rectangle.ByCornerPoints(pnt08);
	are01 = rct01.Patch().Area;
	rct02 = List.LastItem(List.SortByKey(rct01<1>,are01<1>)["sorted list"]<1>);
	return rct02;
};


def Divs(srf:var[]..[])
{
	divs = [Imperative]
	{
		c = 0;
		r = [];
		n = true;
		s = [];
		while (n)
		{
			r [c] = Rect(srf);
			sld01 = Surface.ByPatch(List.Flatten(r[c],-1));
			sld02 = Solid.ByUnion(Surface.Thicken(sld01,10));
			s [c] = Surface.SubtractFrom(srf,sld02);
			srf = List.Flatten(s[c],-1);
			n = List.Count(List.Flatten(r[c],-1))>0;
			c = c+1;

		}
		rct01 = List.DropItems(List.Flatten(r,-1),-1);
		prm01 = (List.LastItem(List.DropItems(List.Flatten(s,-1),-1)).Explode());
		return [rct01,prm01];
	}
	crv01 = PolyCurve.ByJoinedCurves(divs[1].PerimeterCurves());
	crv02 = List.Flatten([divs[0],crv01],1);


	return crv02;
};
5 Likes

Huge Thanks Vikram,

I will dissect your DS to see if I have any ideas on solving the know issues. This will be a huge help as is though.

Thank you

1 Like

Subtraction from boundary concept. I’m lost on what the approach would be for curves, but this creates a sufficient number of rectangles to start annotating dimensions (annotate point-to-point from the final line generation, then collect the boundary corners and annotate point-to-point along the exterior)

3 Likes

This is a very nice solution - squaring off the points like this is ideal.

I have to wonder if the AHJ would be ok with this though.

If the AHJ is insistent on addition instead of subtraction, the vertices could probably be re-tooled pointing inward: getting the orthogonal vector that is ‘closest’ to the centroid and shooting a line across until it hits the first boundary curve it contacts. In this case the exterior boundary points would just be used for hosting the dimension segments. The caveat would be a lot of unnecessary rectangles that would be simplified if the process was done by hand.

1 Like

Vikram,

I have tried your solution but I am running into some problems.

Warning: Internal error, please report: Dereferencing a non-pointer.

I have additional packages that have defined libraries with List and Math. I tried two things to solve this. One I removed all of my packages and two I took your code and pasted it into note pad and replaced List with DSCore.List and Math with DSCore.Math. I got the above warning in both cases.

I also recreated your script with nodes. It helps me visualize where the problem maybe coming from. This resulted in no data though. At fil03 an empty list is produced as 8 items have been removed from a list of 7. This triggers all of the following to produce nothing as well. Should the if statement for fil02 grab acc01?

I think I understand what you are doing but I got a little lost through this section.

Sorry I was not able to figure this out you have already provided so much.

My interpretation of your Design Script
RectangularDivision to Nodes.dyn (255.3 KB)

Thank you,

I like where your heads at @Robert_Younger, unfortunately they are not interested in addition. I will study your solution though as it is very simple. Even if this does not 100% get us there its a huge step from nothing.

A start on something Python based which could help pull the larger bounding boxes out of the interior spaces. I haven’t tried this on your shape yet, and it will need some edge condition and less ‘brute force’ try-except efforts. I don’t plan on pushing this much further in the near future as it meets the needs of my current projects.

#### Written by Jacob Small ####
#Twitter: @JacobWSmall
#Original Share location: https://forum.dynamobim.com/t/programmatically-break-down-complex-shapes-into-simple-polygons/57485/15?u=jacobsmall

#### sets up the Dynamo Python environment so we can do work ####
import sys #imports the system module so we can configure the Dynamo Python environment
import clr #imports the common language runtime so we can call non-Python libraries
clr.AddReference('ProtoGeometry') #imports the protogeometry library
from Autodesk.DesignScript.Geometry import * #adds the design script geometry module to the Dynamo Python environment.

#### builds any new custom definitions ####
def offsetEdge(basePnts,rect): #builds a custom definition to reduce the bounding rectangle to a smaller inscribed rectangle
rectLines = Geometry.Explode(rect) #pulls the lines from the rectangle input
dist = 0 #sets the base distance to 0
farPoint = 0 #sets a variable for the far point as a number, because reasons
for pnt in basePnts: #sets up a looop to iterate over every point in the list of base points
pntSeparation = Geometry.DistanceTo(rect,pnt)#gets the separation distance from the rectangle to the point
if dist < pntSeparation: #if the distance from the point to the rectangle is less than the separation between the point and the rectangle
farPoint = pnt #set the far point variable to the point
dist = pntSeparation #set the distance to the separation
offset = dist #sets the offset variable to the resulting distance after looping over the points
closeLine = 1 #sets a variable for the closest line as a number, because reasons
indx = 0 #sets the initial index to 0
vect = 0 #sets a variable for the offset vector as a number, because reasons
i = 0 #sets a the variable i to 0 so we can use it to iterate over
for line in rectLines: #sets up a looop to iterate over every line in the list rectangle lines
lineDist = Geometry.DistanceTo(line,farPoint) #sets the line offset distance to the sepration between the line and the far point
if offset >= lineDist: #if the offset distance from the point to rectangle comparison is greater than or equal to the line distance
closeLine = line #sets the sets the closest line variable to the line we're iterating over
closePnt = Geometry.ClosestPointTo(line,farPoint) #sets the closest point variable to the closest poin on the line to the farest point from the rectangle
vect = Vector.ByTwoPoints(closePnt,farPoint) #craetes a vector by the point on the line and the farthers point from the rectangle
indx = i #sets the value of the index to the value of i
i+=1 #incremetns the value of i by 1
newLine = Geometry.Translate(closeLine,vect) #moves the offset line by the vector defined in the proceeding for loop
next = indx+2 #gets the index opposite in the rectangle by adding two
if next >= 4: #if the value of next is greater than or equal to 4
next-=4 #ensures we aren't indexing further than the lenght of the list by subtracting 4
oppositeLine = rectLines[next] #gets the line in the existing rectangle by pulling the item at the next index
pnts = [newLine.StartPoint,newLine.EndPoint,oppositeLine.StartPoint,oppositeLine.EndPoint] #sets a list of points from the offset line and the opposite line on the rectangle
newRect = Polygon.ByPoints(pnts) #generates a new rectangle by the list of points
newPnts = [] #defines an empty list to append the remaining points inside the new rectangle
for pnt in basePnts: #sets up a looop to iterate over every point int he list of base points
if Polygon.ContainmentTest(newRect,pnt): #if the point is inside the new rectangle
newPnts.append(pnt)#append it to the list for new points
return newPnts, newRect #returns the list of new points and the new rectangle defined in the definition

#### begins to work with real data now that we ahve set up the list of tools we need ####
baseShape = IN[0] #the perimeter curves of the shape in question
basePnts = [] #defines an empty list to append the base points to
for line in baseShape:#sets up a looop to iterate over every line in the initial base shape
basePnts.append(line.StartPoint)#append the start point to the basePnts list
boundingBox = BoundingBox.ByGeometry(baseShape)#pulls the bounding box from the initial list of lines
mN = boundingBox.MinPoint #gets the minimum point of the base shape bounding box
mX = boundingBox.MaxPoint #gets the maximum point of the base shape bounding box
xVals = [mN.X,mX.X,mX.X,mN.X] #generates a series of X values to build a rectangle with
yVals = [mN.Y,mN.Y,mX.Y,mX.Y] #generates a series of Y values to build a rectangle with
pnts = [] #defines an empty list to a list to append the rectange corner points to
i = 0 #sets a new variable i to iterate over
for val in xVals: #sets up a looop to iterate over every value in the list of rectangle corner point X values
pnt = Point.ByCoordinates(xVals[i],yVals[i]) #generate a point from the X Y index
pnts.append(pnt) #append the point to the list of points
i+=1 #increment the variable i
rect = Polygon.ByPoints(pnts) #generates a polygon from the rectangel corner points
base = [basePnts,rect] # creates a list of the base points and the initial rectangle to use in the custom definition
i=0 #sets the value of i to 0 to use as an iteration in our loop.
while i<4:# sets up a looop to perform the actions four times, or once for each side of the rectangle
try:#sets up an attempt to offset one side of the rectangle
basePnts = base[0]#gets the base points from the base variable
rect = base[1]#gets the base rectangle from the base variable
base = offsetEdge(basePnts,rect) #sets the base variable to the output of the custom definition, shifting 1 side of the rectangle
i+=1#incremetns the value of i by 1
except: #if that fails
i+=1#incremetns the value of i by 1

OUT = base[1]#outputs the reduced rectangle

Recreating this with nodes could be tedious. Instead you could paste the body of the first definition in a fresh code block and identify the line that’s causing trouble by checking the output at each output port. If the output at a particular line is null, that would need to be addressed.

Something like this…

It works for me so no nulls in the illustration

1 Like