[Poppler-bugs] [Bug 3188] Pasting tables cells in strange order

[bugzilla-daemon at freedesktop.org]

https://bugs.freedesktop.org/show_bug.cgi?id=3188

--- Comment #68 from Marek Kasik <mkasik at redhat.com> 2010-11-16 07:10:29 PST ---
Created an attachment (id=40308)
 View: https://bugs.freedesktop.org/attachment.cgi?id=40308
 Review: https://bugs.freedesktop.org/review?bug=3188&attachment=40308

optimization of search for tables

Hi,

this patch improves efficiency of searching for blocks which belong to a table.
In the worst case it is still quadratic but it should be O(n*sqrt(n)) in
average case.
It creates a list of all y coordinates and then sort it. After that it goes
through this list and for each y coordinate which begins a block it starts a 
local while cycle. This while cycle searches for blocks which overlaps with the
actual block in y. It finds closest blocks from the left and from the right
during this search.
It does the same for the x coordinate and finds up and down adjacent blocks.
After that, it uses this information for computing of ExMin, .., EyMax and for
determining whether the actual block is part of a table.
(You need to have the Brian's patch applied already.)

Regards

Marek

-- 
Configure bugmail: https://bugs.freedesktop.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.