Draw largest rectangle within a limited shape

[hs800150]

Ok so this lisp might be too complicated but I would like to know if anyone knows a lisp to automate the largest rectangle within a space. I have attached a picture of what I mean. The red rectangle has to be a rectangle (90 degrees between each angle) and stay within the boundaries of the white shape. Lets say I can choose a width say 40' and the lisp automatically finds the largest length based on trial and error. Or if there is a lisp to find both the largest width and length that would work too. 

[john.uhden]

That's sort of the way I was thinking, though I don't think there's any
point in limiting the length of the first edge. Let the computer figure it
out.
Also realize that the largest rectangle just might be too skinny for use as
a residential dwelling. You might want to include a parameter for a
minimum width/length.

[hak_vz]

@john.uhden  I agree with you, and it is actually much easier to work without without to many constrains.

[hak_vz]

@hs800150  Could you please provide a sample drawing. Not whole cadastre but a small section so that we can figure out how lots are created (version 2014). I work in with SI units so just to get a filling about sizes and so on.

[Kent1Cooper]

---

@hs800150 wrote:

.... I am thinking in the code you choose the side the rectangle needs to be parallel to the lot border. ....

 one side of the rectangle would be parallel to that line and go through iterations until it finds the largest fit....

---

So many complications....

Maybe I'm reading more into your image than you intend, but if you're assuming that your green rectangle is the largest, and  assuming that the largest would meet the corner of the perimeter [at the top in your image], you could get faulty results.  In my approximation of the same arrangement, the magenta rectangle is larger than the green one, freed from the need to meet an end of the chosen boundary edge.

That presumably complicates what a routine would need to work through, if both ends of the aligning edge are floating.

[john.uhden]

Your magenta rectangle could be arrived at by inching down the longer sideline testing for a bigger rectangle until it started shrinking again.  It shouldn't take very long to process since we're talking about a building lot, not the country of Chile.

[hs800150]

@hak_vz 

I have uploaded a sample cul-de-sac with lot lines and building lines. Let me know if they work on your version. I had to save to 2013. This is 8 lots with the building lines (Dashed lines). The dashed lines are the polygons that the largest rectangle will fit in. I also provided some sample building dimensions that were used on this project to determine whether or not they would fit within the building lines.

[hak_vz]

Here is my starting code (in attachment). It is not finished, it has address a lot of cases  that are not tackled yet, but you can see how it will work. It can fail on some edges. It is an early alfa version to prove a concept.

[hak_vz]

Now I have something to play with. Alfa code works on some shapes, other are disaster, but that is a normal sequence. This is not an easy task to write it perfectly in a first iteration.

[Sea-Haven]

The only issue is that the rules are you must meet a minimum building envelope, but it can have any orientation. So once working for a known side then unfortunately say rotate 5 deg's increments. One development near me was that a building envelope had to miss the trees to remain on the property.

[john.uhden]

I hate to say this, but most often a developer has a small variety of
footprints he would like to build. It usually requires the designer's eyes
to see what shape will fit properly on any lot. None of our clients builds
rectangular residential houses. Plus, the lot coverage is usually the most
restrictive requirement.

[hs800150]

@john.uhden 

I know developers don't usually have rectangular footprints but there is a lot more code to decide whether or not the certain footprint fits inside the LARGEST BOX I individually draw for each individual lot.

@Sea-Haven 

I wouldn't necessarily worry about meeting a minimum building envelope just the largest area within the setbacks. If there is a certain angle I can start from say I draw the line that faces the street or choose one of the side building lines or have the code let me choose both the front line and the side building setback and it returns the biggest box area from those two test is all I'm looking for. Let me know if this is a wash

[Sea-Haven]

A the end of the day it comes down to the planning Authority will they accept a "L" shape for the desired minimum area. The project I know of because of native vegetation took years to get permits and when you buy a block it has the designated house area decide to cut a tree down up to  $100,000 fine. 

The quickest solution and its something here in AUS as well we see blocks down to 350m2 I downsized from 700+ to 450m2 but its a very old back in the 1900's subdivision as grids. Make sure blocks bulk area is big enough without a rectang.

[hak_vz]

@hs800150 

Our rectangle is supposed  to lie on one of the polygon edge (presumably longest). What if there exist rectangle with larger area, that have edge parallel to asked one that don't lie on polygon. (situation \__/)? I'm will continue my work on code, but will not post until I have more robust solution since there is a lots of special cases that have to be included. Creating partial solution is not an option.

[hak_vz]

@hs800150 

In attachment is my code you should test if it solves your problem (at least in part). If it is ok,  select this as a final solution.

Further changes and updates are possible after you answer some of my previous questions.

[CodeDing]

@hak_vz ,

That's a great start. I enjoy the visuals also.

[hak_vz]

@CodeDing

I'm glad that you like my initial code. Visual effect is actually coming from command "area". When you define an area by picking points, command "area" stretches shaded area and visualize enclosed area.

Code is working very well but it has to address some flaws resulting from his iterative algorithm.

1) I have to test that resulting rectangle don't intersect enclosing polygon. Since at least one point lies on enclosing polygon using vla-intersectwith is not an option. I'll try to test if rectangle side, that is on opposite side to edge that lies on enclosing polygon, intersect with enclosing polygon.

2) If points that define enclosing polygon create a shape that looks like ">_<" (sorry have no time to create a slide), code also have to test rectangles that touch that vertex .

3) If there is an arc on opposite side to rectangle edge with downward concavity "U" its also have to be taken into account.

It would be great if there would be a function that would reshape starting polygon but that is not an option.

[hak_vz]

Here is improved version that skips rectangles that intersect with enclosing polygon.

[doaiena]

Here is my quick and dirty interpretation. It looks like me and @hak_vz had a similar idea, just the execution is different /i hope you don't mind i used your (/ distance 50) calculation for the steps/.

At the last moment i found a bug, where if you pick the first segment of a pline, the 'vlax-curve-getParamAtPoint' function returns the wrong parameter, because both par 0 and the last parameter share the same point.

(defun c:test ( / *error* GroupPoints ClosestInters LWPoly ent obj acadmodel segPt segPtPar segStartPt segEndPt segAngle
	       dir step stepBase stepForward stepBack osm ray inter ray2 bp1 bp2 p1 p2 len width maxArea maxRect)

(setq *variables* '(GroupPoints ClosestInters LWPoly ent obj acadmodel segPt segPtPar segStartPt segEndPt segAngle
		    dir step stepBase stepForward stepBack osm ray inter ray2 bp1 bp2 p1 p2 len width maxArea maxRect))

(defun *error* (msg)
(cond
((not (vl-position msg '("Function cancelled" "*Cancel*" "quit / exit abort")))
(princ "\nAn error has occured.")
)
(T (princ "\nExit."))
)

(if osm (setvar 'osmode osm))
(if (/= *variables* nil) (mapcar '(lambda (x) (set x nil)) *variables*))
(setq *variables* nil)
(vla-endundomark (vla-get-activeDocument (vlax-get-acad-object)))
(redraw)

(gc)
(princ)
);defun

(defun GroupPoints (lst)
(if (> (length lst) 2)
(cons (list (car lst) (cadr lst) (caddr lst)) (groupPoints (cdddr lst)))
)
);defun

(defun ClosestInters (ray pline pt)
(cadr (vl-sort (GroupPoints (vlax-invoke ray 'intersectWith pline acExtendNone))
'(lambda (a b) (< (distance pt a) (distance pt b)))))
);defun

(defun LWPoly (lst)
(entmakex (append (list (cons 0 "LWPOLYLINE")
(cons 100 "AcDbEntity")
(cons 100 "AcDbPolyline")
(cons 90 (length lst))
(cons 70 1))
(mapcar (function (lambda (p) (cons 10 p))) lst)))
);defun


(while (not ent) (setq ent (entsel "\nSelect a closed polyline: ")))
(setq obj (vlax-ename->vla-object (car ent)))

(if (and (= (vla-get-objectName obj) "AcDbPolyline")
	 (= (vla-get-closed obj) :vlax-true)
	 )
(progn
(vla-startUndoMark (vla-get-activeDocument (vlax-get-acad-object)))
(setq acadmodel (vla-get-modelspace (vla-get-activeDocument (vlax-get-acad-object))))

(setq segPt (getpoint "\nPick a point, near one of the PLINE segments."))
(setq segPtPar (vlax-curve-getParamAtPoint obj (vlax-curve-getClosestPointTo obj segPt)))
(setq segStartPt (vlax-curve-getPointAtParam obj (fix segPtPar)))
(setq segEndPt (vlax-curve-getPointAtParam obj (+ (fix segPtPar) 1)))
(setq segAngle (angle segStartPt segEndPt))
(setq dir 1)
(setq step (/ (distance segStartPt segEndPt) 50))
(setq stepBase (vlax-3D-point '(0 0 0)))
(setq stepForward (vlax-3D-point (polar '(0 0 0) segAngle step)))
(setq stepBack (vlax-3D-point (polar '(0 0 0) (+ segAngle pi) step)))
(setq osm (getvar 'osmode))
(setvar 'osmode 0)

(setq ray (vla-addray acadmodel
		      (vlax-3D-point (polar (vlax-curve-getPointAtParam obj (+ (fix segPtPar) 0.5)) (+ segAngle (/ pi 2.0 dir)) 0.1))
		      (vlax-3D-point (polar (vlax-curve-getPointAtParam obj (+ (fix segPtPar) 0.5)) (+ segAngle (/ pi 2.0 dir)) 10))))
(setq inter (vlax-invoke ray 'intersectWith obj acExtendNone))
(if (and (> (length inter) 0) (/= (rem (/ (length inter) 3) 2) 0))
(setq dir 1)
(setq dir -1)
)
(vla-delete ray)

(setq ray (vla-addray acadmodel (vlax-3D-point segStartPt) (vlax-3D-point (polar segStartPt (+ segAngle (/ pi 2.0 dir)) 10))))
(while (/= (rem (/ (length (vlax-invoke ray 'intersectWith obj acExtendNone)) 3) 2) 0)
(vla-move ray stepBase (vlax-3D-point (polar '(0 0 0) segAngle 0.1)))
)

(setq ray2 (vla-addray acadmodel (vlax-3D-point segEndPt) (vlax-3D-point (polar segEndPt (+ segAngle (/ pi 2.0 dir)) 10))))
(while (/= (rem (/ (length (vlax-invoke ray2 'intersectWith obj acExtendNone)) 3) 2) 0)
(vla-move ray2 stepBase (vlax-3D-point (polar '(0 0 0) (+ segAngle pi) 0.1)))
)

(setq bp1 (vlax-get ray 'basePoint))
(setq bp2 (vlax-get ray2 'basePoint))
(setq p1 bp1)
(setq p2 bp2)

(while (and (vlax-curve-getParamAtPoint obj p1) (> (vlax-curve-getParamAtPoint obj p2) (vlax-curve-getParamAtPoint obj p1)))

(while (> (vlax-curve-getParamAtPoint obj p2) (vlax-curve-getParamAtPoint obj p1))

(setq len (distance p1 p2))
(setq width (min (distance (ClosestInters ray obj p1) p1) (distance (ClosestInters ray2 obj p2) p2)))
(if (> (* len width) maxArea)
(setq maxArea (* len width)
      maxRect (list p1 p2 (polar p2 (+ segAngle (/ pi 2.0 dir)) width) (polar p1 (+ segAngle (/ pi 2.0 dir)) width))
      )
)
(vla-move ray2 stepBase stepBack)
(setq p2 (polar p2 (+ segAngle pi) step))
);while
(vla-move ray stepBase stepForward)
(setq p1 (polar p1 segAngle step))
(vla-move ray2 (vla-get-basePoint ray2) (vlax-3D-point bp2))
(setq p2 bp2)
);while

(vla-delete ray)
(vla-delete ray2)
(LWPoly maxRect)
(vla-put-color (vlax-ename->vla-object (entlast)) 6)

(setvar 'osmode osm)
(vla-endUndoMark (vla-get-activeDocument (vlax-get-acad-object)))
)
(princ "\nThe selected object is not a closed polyline.")
);if closed pl

(setq *variables* nil)
(princ)
);defun

[hak_vz]

@doaiena

I like it. You just have to implement tests that I mentioned in my previous posts. In some situation your code produces  a resulting rectangle that intersects with enclosing polygon. 

[john.uhden]

You must be an old fart like myself. I haven't seen localized variables
escape since R13.