Spending too much time on identifying text bboxes

[robvandijk]

For the attached file to_markdown hangs for a long time on identifying bboxes (about half an hour).

Version pymupdf4llm: 0.0.17
Version pymupdf: 1.25.1

When stopping the conversion using Ctrl-C it is always in in_bbox:

  File "/usr/local/lib/python3.10/site-packages/pymupdf4llm/helpers/pymupdf_rag.py", line 936, in to_markdown
    parms = get_page_output(doc, pno, margins, textflags)
  File "/usr/local/lib/python3.10/site-packages/pymupdf4llm/helpers/pymupdf_rag.py", line 860, in get_page_output
    text_rects = column_boxes(
  File "/usr/local/lib/python3.10/site-packages/pymupdf4llm/helpers/multi_column.py", line 413, in column_boxes
    if in_bbox(nbb, path_rects) != in_bbox(bb, path_rects):
  File "/usr/local/lib/python3.10/site-packages/pymupdf4llm/helpers/multi_column.py", line 99, in in_bbox
    if bb in bbox:

Is it possible to speed up this identifying?

bbox-problem.pdf

[robvandijk]

The cause for this slowness is the path_rects variable in column_boxes. For the PDF included above, this is an array with ~31k entries. Due to the many loops over this array the processing time increases considerable when this array is large.

A PR has been raised to address this problem: #216

The processing time for the PDF included above is reduced from ~30 minutes to 40s.