Shape Fitting is a simple SketchUp plugin that finds a simpler shape with fewer vertices from an input shape with many vertices. Plugin originates from one functionality of Park Generator, which was employed when the initial input region had to be mapped to a quad somehow before Grid rule can be applied to it. The quad area should match the area of the input polygon in the best possible way, and that does not necessarily mean minimal differences in areas . Rather, the quad should act as a template for the Grid rule – we should bear in mind that the ultimate goal is for the resulting park to look good. Park content is bounded (practically speaking – clipped) by the input region.
The plugin is available at the Extensions Warehouse store. Widgets are created with the SKUI library.
Currently, the plugin uses three methods to find this quad, and these are grouped into two classes below.
Bounding Boxes Methods
AABB (Axis Aligned Bounding Box) and OBB (Oriented Bounding Box) enclose the entire input polygon. While AABB aligned to x and y (world) coordinate axes, as the name suggests, OBB is rotated – to find the rectangle with the minimal area that contains the entire input polygon. The plugin uses GTE library to compute OBB, which implements rotating callipers algorithm [1].
Axes Corners method uses x- and y-axes as the name suggests. If OBB is chosen from the Box type parameter – axes are mapped to the local coordinates of the oriented box. Algorithm works as follows: from the centre of the polygon rays are cast to the corners of the box (‘corners of axes’) and resulting edge intersections make up the quad vertices. It is worth noting that the fitted polygon (quad) vertices lay on the boundary of the input, which (for the most time) do not coincide with those of the input polygon.
Angle Thresholding Methods
A Naive angle thresholding method filters input vertices by an angle threshold between adjacent edges. For instance, if the dot product of the adjacent edges is less than a certain value (e.g. 0.5) then the vertex angle is sharp enough for this vertex to be classified as a corner. However, depending on the input shape, for a given threshold value there could be an arbitrary number of corners detected! Next method, an improvement of this one, fixes this.
Adaptive thresholding method tries to search for the optimal threshold that delivers specified number of corners (4 in a case of a quad). The algorithms takes the initial cosine range of [-1, 1], picks a threshold somewhere in the middle, and, until the threshold produces the correct number of corners – iteratively searches in one of the subranges – either below (to get fewer corners) or above (to get more corners) the threshold. Currently, for “somewhere in the middle” the plugin picks a value exactly in the middle (e.g. 0.5 for [0, 1] range), although other picks could possibly be tried too to make convergence faster! This algorithm, however, does not terminate for every case, such as when all angles are equal (a poly-circle). To solve this, the total number of iterations is limited, and if no threshold found algorithms returns an empty polygon.
