Estimating bounding boxes and layout extends

[mozman]

The first idea is to use a non-graphical drawing backend to simplify entities
for the estimation of bounding boxes and layout extends.

The result of such a simplification is a collection of construction tools:

• Path() entities for linear entities and text entities
• MeshBuilder() for all face based 2D/3D entities.

Bounding Box detection for Path() by flattening() is fast, if the C-extension
is available. Bounding box for MeshBuilder() is easy.

Linear entities as Path()

• LINE
• CIRCLE
• ARC
• ELLIPSE
• SPLINE
• HELIX?
• LWPOLYLINE (incl. bulges, without width)
• 2D POLYLINE (incl. bulges, without width)
• 3D POLYLINE
• SOLID
• TRACE
• 3DFACE
• IMAGE (clipping path)
• VIEWPORT (clipping path)

Text entities as a Path() rectangle

Using mono-spaced text width calculation:

text_width = len(text) * text_height * width_factor

I will not invest much time into bounding box detection for text entities, it
will never be perfect - so simple and easy should be sufficient.

• TEXT
• SHAPE? like a mono-spaced text
• ATTRIB
• ATTDEF
• MTEXT (simplify to TEXT entities)

3D entities as MeshBuilder()

• POLYMESH
• POLYFACEMESH
• MESH
• 2D polylines with width: MeshBuilder() from TraceBuilder()

Collection of construction tools

• POINT (dissolve point symbols)
• HATCH as collection of boundary paths
• LEADER
• MLEADER
• MLINE
• INSERT
• DIMENSION is an INSERT
• LAYOUT (model space and paper space)
• Proxy graphic

Ignored entities

• ACIS data as always not supported!
• WIPEOUT - to remove hidden vertices the drawing order is required
  which just raises the complexity
• XREF
• UNDERLAYS

This structure raises the question, if the implementation as a drawing backend
is a good idea?

This representation could also represent 3D text, which is not supported by the
drawing front end. Property resolving is not required. The matplotlib library
is not required, therefore it could be added as a core tool.

[mbway]

I think the advantage that the drawing frontend has rather than working with the dxf entities directly is that it takes this long list of complex entity types and converts them to and small number of simple primitive types, then passes those primitives to the backend. This functionality would be useful if it was available in a stand-alone form not requiring a frontend object to be created. In most cases at least, it should be possible to implement some kind of .primitives() -> Iterable[Primitive] for the entities to perform the conversion that is currently handled by the frontend.
Primitive could be something like: Primitive = Union[LinePrimitive, PointPrimitive, TextPrimitive, Path] (just a suggestion)

There would obviously be some information loss in this conversion (such as HATCH becoming just a collection of Path primitives without the semantic information to know which are holes etc), but the conversion is always going to be lossy so it's a choice about which information is useful to keep most of the time. I think keeping just the geometry makes sense for most use cases but I'm not sure.

Then if you have an insert entity or something which contains LINE, POLYLINE, LWPOLYLINE entities etc, and you want all the line segments to get

my_insert = ...
my_lines = [primitive for primitive in my_insert.primitives() if isinstance(primitive, LinePrimitive)]

you could provide standalone functions like bounding_box(primitives: Iterable[Primitive]) or points(primitives: Iterable[Primitive]) or convex_hull(primitives: Iterable[Primitive]) to automatically be able to calculate things like bounding boxes of any combination of primitives. For example:

bb = bounding_box(primitive for insert in layout.query('INSERT') for primitive in insert.primitives())

This might be more usable than providing only methods for calculating bounding boxes (although helper Entity.bounding_box() methods would probably still be useful).

This is all just a suggestion, there are probably lots of ways to achieve a similar result.

I have seen projects often use ezdxf for these kinds of things but always do a custom conversion from the dxf entities that they are interested in and extracting information about a subset of those entities. If ezdxf offered a way to handle all the complexity of the difference between LWPOLYLINE and POLYLINE for example then these projects would be more robust, handle more entity types and be simpler to maintain (as the complexity is maintained in ezdxf). Here is one random example I picked that uses ezdxf. This type of processing would benefit massively from this kind of api being offered directly from ezdxf.

[mozman]

I think we mean the same thing, but I'm not 100% sure.

In the last paragraphs of my post I came to the conclusion that writing a non-graphical backend for the drawing add-on is maybe not the right way, but I didn't show what I thought of instead.

1. The lists above shows that all entities could be represented by only 2 "primitives" and collections of them: Path() and MeshBuilder(), for text only a rough bounding box.

2. A generator could yield these "primitives" from a LAYOUT, an INSERT or any collection of DXF entities like an EntityQuery(), let's call it to_primitives(entities). This would be the equivalent of the drawing frontend.

3. A bounding_box() function as you showed, would be the consumer of such a generator: bounding_box(to_primitives(entities)), to find the bounding box the function could easily approximate (flatten) the Path() objects and MeshBuilder() has already a vertices list to push into the BoundingBox() entity and the same input could be used for a convex_hull() function or just a to_vertices() generator, which yields all vertices. This allows writing the bounding_box() function as BoundingBox(to_vertices(to_primitives(entities)))

4. Including meta data as handle to the source entities would be nice, but breaks already a the first recursion level which yields only virtual entities with handle=0.

5. A wrapper abstraction for "primitives" could be the solution for carrying source information, which could include the whole source DXF entity.

6. Next Idea: An additional generator layer on top: to_entities(), which yields all DXF entities as a linear stream, which is already planned for the BaseLayout() object. The execution chain would look like: BoundingBox(to_vertices(to_primitives(to_entities(entities)))). This looks like a versatile tool chain or pipeline. Convenience functions like bounding_box(entities)could be built on top of this tools.

Suggestions for function and module names are welcome:

• module: disassemble, dismantle, decompose
• disassemble.to_entities(collection) -> DXF entities stream (Line, Circle, Arc, ....), disassembles Insert entities recursively
• disassemble.to_primitives(entities) -> Primitive() (the wrapper class) stream, convert DXF entities to Path() and MeshBuilder() objects
• disassemble.to_vertices(primitives) -> vertices stream

[mbway]

I like this suggestion. I was thinking slightly differently in that the to_primitives() function would do the exact same deconstruction as the drawing frontend does currently (meaning the frontend could be redesigned to use to_primitives() internally), but if shedding a bit more information can result in only 2 primitive types then that could be more useful for the normal use cases for things like getting the bounding box.

Personally I like the idea of somehow being able to obtain the dxf entity that a primitive corresponds to. Instead of a wrapper, maybe the to_primitives() function could take an argument to decide whether to return the source entity along with the primitive like this:

for primitive in to_primitives(entities):
    ...

for primitive, entity in to_primitives(entities, source_entities=True):
    ...

A wrapper might still be useful if there are useful abstract methods that the two primitive types could implement differently though.

[mbway]

thinking about your comment in #323 about caching. If the user wants to query the bounding box of lots of groups of entities with overlap then it would be quite easy for the user to cache those:

bounding_boxes = {e.dxf.handle: bounding_box(e) for e in to_primitives(root)}

box1 = bounding_box_union(bounding_boxes[e.dxf.handle] for e in to_primitives(group1))
box2 = bounding_box_union(bounding_boxes[e.dxf.handle] for e in to_primitives(group2))

for axis aligned bounding boxes, calculating the union of a list of bounding boxes is very efficient (even more so when using cython)

this approach could potentially be built into a class which caches the bounding box of each new entity it encounters?

[mozman]

from ezdxf.math import BoundingBox
from ezdxf.entities import bounding_box

cache: Dict[handle, BoundingBox] = dict()
bbox = bounding_box(group1, cache)  # bounding_box() uses disassemble.to_primitives(group1)
# single entity
bbox = bounding_box([entity], cache)
# extend existing bounding box
bbox.extend(bounding_box(group2, cache))
# create a new union bounding box from two others
bbox2 = bbox.union(bounding_box(group2, cache))

The cache object is provided by the user and it is None by default for usage without a cache.

This works of course only for the top level entities, because the content of block references (LEADER, MLINE, ...) are virtual entities and do not have a handle and will be created on the fly every time the block reference will be iterated.

[mozman]

First bounding boxes calculated by ezdxf, and as I expected without matplotlib support the bounding boxes for text are much too wide (monospace-font calculation), but the rest is not bad:

[mozman]

It's good enough for the often wished EXTENDS calculation, but people will be surprised how long it takes ;-).