2D Mondrian like subdivision

Algorithm flow. This subdivision method actually creates a given user Mondrian like space, but does not actually subdivide a given mesh selection area. While I could have used a point testing algorithm to determine neighboring nodes without key mapping node neighbor relations, on the other hand point testing especially with a larger node base means potentially having a nearest neighbor testing mechanism to do so. Obviously mapping key relations to begin with using key hashing saves any checks that need be done later one potentially with any added inefficiencies in a redundant search, and is something commonly done throughout my algorithm. In fact I construct a number of smaller dictionary/mapped relationship for three different node types that I have categorized here, namely: Boundary nodes, Crossing nodes, and regular Subdivision Nodes. Boundary Nodes originate from Subdivision Nodes (or Nodes as I have called them), and Crossing Nodes also originate from Subdivision Nodes. I construct three separate dictionary/maps for each of these different node types (parsing differences in logical structure forming such nodes), and then compile all of these maps into a larger map. Each of these maps, by the way, have the same directory structure which makes for ease in a unitary compilation.

Albeit having written this for creating a subdivision, for instance, using three randomly positioned subdivision node points, this should in theory be extendable to the generalized n node points case.

First to assign to nodes by position. Second rank ordering nodes by x and y axis respectively. Third to check on the subdivision grid all other intersection points (outside of the grid boundaries) for crossings.

Here are models depicting crossings checks:

Rules for crossing

• Node have crossing precedent.
• An edge starting from a crossing node, does not have an edge terminating on a non passing neighbor crossing node, but may pass into a crossing node if positive for crossing or if a neighboring node is non crossing or a regular node, or in other words, all edges starting from a crossing node may not have a 4 direction radial pattern but instead contingent on the neighboring crossing positives assigned. The no terminating on a non crossing node rule, is excepted in the case of a non crossing nodes not already having been drawn by an edge.
• Crossing nodes and nodes alike have boundary clearance direction leeway. Meaning we can draw a subdivision edge in the direction of the nearest boundary, as long as such boundary is on a neighboring position/point.
• All edges starting from a node have 4 directions, and terminate on crossing nodes whether positive or negative for crossing.
• All edges must start and end when passing into a node, but may cross (pass through) a crossing node.

For the example above, for instance, an edge drawn from 3 in the 'down' direction terminates at the nearest crossing node. To resume drawing from the crossing node means according to rules drawing the edge to the 'right' since the crossing node to the 'left' is negative for crossing.

While at node 2 we draw 'top' 2 crossing node positions up, and terminate the edge. A new edge formed at this terminus would form to the right terminating at node 3. An edge drawn to the right from node 1 terminates at the crossing node 1 unit above node 2. This in turn leads to a node that can be drawn 1 unit down to node 2 and 1 unit up to the crossing node 3+ terminus.

Rules for drawing faces

• Nodes are prioritized for the construction of faces. All faces are constructed from nodes first, and then remainder faces are determined from incompleteness.
• Faces are drawn from nodes where starting in one of 4 directions and drawing in a counterclockwise manner. Face's are determined by two edges, one starting in the given starting direction away from such node, and secondly according to the counterclockwise direction chosen on the second vertex. The remaining vertex is determined using the projected axis length of the second vertex alongside the projected axis length from node vertex to the first edge length's endpoint vertex.
• A construction sweep is prioritized from left to right (x axis ordering) on nodes.
• Face overlap constructions are avoided, that is adding into the same area, or adding a face which overlaps into such area.
• Faces are tracked by vertices in a list, and also keyed by vertices into a corresponding face bucket.
• Any candidate face is checked for overlap by measuring node overlaps given any already keyed face with nodes that intersect (will provide a sketching of this)

Intersection testing starts by considering any face as a composition of the simplest irreducible face element (e.g., consider that the starting node for such face should have an adjacent neighbor crossing node in orthogonal direction alongside one node compliment that is a neighbor of both such neighbors that is likewise at a basis inside such face), then we can describe any face as a aggregate composition of nuclear face elements (i.e., the smallest irreducible face) that occupies such face. Then one can describe an intersection test as follows (I'll call such irreducible face a 'simple' face):

• Any face is given by the union of all simple faces as a subset.
• Any simple face that belongs to the union of another subset 'face', fails the intersection test.

Here then has a relatively simple feature of defining such simple faces subset for any defined face, and from this examining this union for intersection failures. In this case, I hadn't wanted to flunk any face (by way of simple face unions), however, with intersection failure, but instead the algorithm works only to completely flunk such face construction, if the root node simple face (only 1 such root node simple face exists such to contain our node point which is represents a corner in such union) has already been given in another face by simple union faces subset. Instead if the root node simple face passes, then we pass all passing faces to another algorithm. Which re defines a passing intersection test, by starting from the root node and redrawing simple faces in either orthogonal neighboring directions. Until reaching a 'no pass' limit. This also ensures neither passing (by way of ordering) non contiguous nodes, as in the case of an intersection which span overlaps 1 intersecting regions but has 2 non contiguous passing regions.

Faces as related to all nodes have been constructed. Now what?

There is remaining incompleteness likely especially likely as the number of subdivision nodes increases. The general strategy is then, with an overall definition of the entire area given as union of simple faces subset, and a given definition likewise of already processed areas by any union of simple faces, one can process simple face remainders for completeness in filling the rest of a given spatial area. In this case, however, one should define a given crossing node (as in the case of the node being defined in the previous process) as a node of origin, and a similar procedural method should apply in so far as drawing in 4 directions any given face. Once having iterated over a given remainders set, then a complete description of faces should be given.

Other possible subdivision methods?

Albeit potentially simpler methods that I could think of off hand rely upon ranking subidivision ordering . For instance, a first node subdivides equally the entire area. While a second node subdivides, one of the 4 quadrants of the first node. While a third node, can either subdivide one of three remaining 1rst node subdivided quadrants, or subdividing one of the 2nd node quadrants, and this iterated procedure repeats itself for a nth node procedure. In these cases, one could create something like a binary tree for tracking parent to child subdivision processes, coupled to the appropriate subdivsion quadrant. This method with large nth ordered nodes, quasi fractal patterns, but I am not so certain that this would be as great in maintaining a balanced scaling between quadrant subdivision as one were adding nodes. For instance, it is easy to imagine that node subdivision clusterings would lead to node groupings where geometric subdivisions are more tightly clustered relative to other areas...the effect, however, could be interesting.