A couple of enhacement suggestions

[Jacajack]

Hi,

First of all, thank you for this great project - it's really helpful and helps to save a lot of time.

Today I used the interactive BOM during assembly of two rather large PCBs (~350 BOM entries each). Based on my first impressions, I came up with a list of suggestions that could make manual assembly process a bit smoother. I just wanted to know if there's any chance that these could be implemented in the future versions:

• Add an option or filter syntax to search only specific columns (https://github.com/openscopeproject/InteractiveHtmlBom/issues/167 might be related?). Suppose you only want to see 120 Ohm resistors - when you search for 120 all the 1206 footprints will be selected too. Searching only the values is especially useful if you don't follow any strict placement order and just grab one bag of parts after another in random order and then just search the BOM for whatever fell into your hands.
• Add a keyboard shortcut to focus on the element list. When you want to filter the list, you can press Alt+F to focus on the filter field and search for something. As far as I know, there is no way to bring the focus back to the element list other than by using your mouse.
• Add an option to sort elements by their proximity instead of sorting by reference - this could make the placement order more natural.
• Make it possible to center the PCB preview on the currently selected element - useful when the viewport is too small to show the entire PCB.

This was my first time using this tool, so I suppose some of the features I mentioned might already exist, but I could have just missed them. In any case, if you think that any of these are worth having, I could try (I'm not very good with Python) to implement some of them and open a PR.

Thanks

[qu1ck]

Hi, thanks for the suggestions, let me address them in same order:

• Yes, #167 is related, a linked merge request on that issue implements hiding columns. When you get too many false positive matches you will be able to hide extra columns and search will not match entries based on those fields. Alternative solution would be to introduce some sort of column search syntax like : that will only match specific field. But I think hiding columns is enough for most cases. For the specific case you described though, I'm not sure why search for a value at all. Bom table entries are grouped by value and even in ungrouped mode components with same value are one continuous block.
• You don't need focus on element list, up/down arrows still work even when focus is in search field. At least on supported browsers.
• Proximity of a set of coordinates is not well defined on 2d space. For a random set of dots on a plane any trivial sorting scheme (by x, by y, by polar coordinate angle) will feel random. There are some complex algorithms that can identify and group clusters of dots or optimize for minimum total distance of a line connecting all dots in a sequence (like tool travel optimization on cnc drill) which I can look into but it seems like an overkill.
• I'm assuming you are talking about ungrouped mode where each bom table entry is single component. The issue here is ibom has no idea what "too small" is for any given board. Perception of adequate zoom level also differs based on a lot of things like ppi of the screen, how busy with details is the piece of the board in question, how large the viewport is. It also goes against the general idea of ibom which is to give indication of location of component on a graphical representation of the board with outline and visible board graphics like silkscreen so that you can quickly locate that position on actual board in your hand. If ibom zooms in on a specific piece of the board does that really help you locate that position? I'd argue that it's more useful to see a small red dot on a large board view than a large red rectangle with a footprint zoomed in on a piece of a board where you have to additionally guess which piece is displayed. One could argue that on a large enough board tiny 0201 footprint is a dot so small it's hardly noticeable, which is true but in such case a) you are not likely to assemble such boards by hand and b) zooming in on a component will make the problem of guessing which piece of the large board is displayed even worse. The only solution I can offere here is to work with a large screen and increase the viewport of the rendered pcb (the delimiters are draggable).

I'm not totally opposed to implementing something like this but usability issues need to be considered thoroughly. For example question of "how much zoom" can be answered with either "let user zoom in once and set it as preferred zoom" or "heuristically determine zoom for each component as bounding box taking 10% of viewport area or being 20px on longest dimension, whichever is smaller". Question of "how can user understand which piece of board is zoomed in" is typically resolved with drawing a minimap of the image in a corner with a rectangle representing viewport area.

If you'd like to help then the proximity thing will be in python but autozoom feature will be entirely in javascript.

[Jacajack]

Thanks for your quick and detailed response

• That's good to hear, I'll be following #167 then. The reason why I'm searching for specific values instead of scrolling the list is simply because it's quicker, especially when you're working on a laptop with a touchpad. I have to say, that I'd really love to see a more advanced search syntax too, or perhaps even a regex search.
• That's true, you can navigate the list, but you cannot mark elements as placed with N. You end up typing n in the filter field instead. This can also be solved by adding another "mark as placed" shortcut, for example Alt+N. Sorry for not being specific about the issue here in the first place.
• You're obviously right, but from my experience improving the ordering even slightly is very convenient. It doesn't have to be perfect. Before I found this project, I used to work with spreadsheet BOMs with (x, y) coordinates of the components. I would quantize the coordinates to 10-20mm resolution, and then use them while sorting the list (sort by x, then y, ascending). This obviously wasn't ideal, but was significantly better than having to jump between opposite edges of the board in some cases. No matter what what algorithm you use you're always going to have some outliers and discontinuities in the placement order. While the CNC solution would probably yield the best results possible, here are a couple of my (probably simpler) ideas, that could be just good enough:
  1. Compute 2D BVH tree containing the components. A good heuristic could be n_components/area. Inside the leaves, sort the components by either x or y coordinate depending on whether the leaf is wider or longer. Then just determine the final order by traversing the BVH. In my imagination this works quite well and is the best one of these three. I could implement a proof of concept when I have some more time.
  2. Divide components into sectors (just like I did in Excel), and then just sort the sectors containing elements. This isn't very good, but isn't that bad either. I have a feeling that it may be worth trying to sort the sectors based on Hilbert curve (or any other space filling curve) traversal.
  3. I'm not quite sure about this one, but maybe something like BFS traversal of minimum spanning tree could provide a decent ordering?
• I was thinking more about the "let user zoom in once and set it as preferred zoom" option. In fact, this feature doesn't have to affect the zoom setting at all. I think a menu option like "Center view on the selected item" or a keyboard shortcut to do so would be sufficient. This way, the user can set whatever zoom level they find comfortable and the PCB would only move around. "Comfortable" could mean that, say, ~75% of the PCB is visible (so there's no problem with making out what region you're looking at) while distinguishing between components next to each other is easier. Also, I feel that "bring the component within the middle 75% of the viewport" may be a better approach than a simple centering (because of components near the edges). The user experience could be made a bit better if the focus transition was a smooth animation instead of a disorientating sudden jump too. But yes, you're right, this more complicated than I initially thought this would be.

[Jacajack]

As for the spatial ordering, here's what I got using the BVH so far: It's not perfect and there are still a couple of things to tweak, but I think it looks quite good already.

[qu1ck]

Alt+[1-9] shortcuts already exist and work when focus is in text field. They don't advance the row like N does but Alt+char is used in some locales to enter variations of the character so I'd like to avoid using such shortcut.

Regarding spatial ordering, first of all: awesome discussion. You never know when some hardcore CS stuff will pop into relevance even in something so utilitarian in function as bom generation.

Second, I like your ideas and BVH graph looks a lot better than random. I also pondered on your MST idea with BFS and I think it can be improved quite a bit:

1. Use DFS instead of BFS. BFS will jump around a lot on later stages.
2. Choose start node smartly: a leaf node on one of the ends of a longest path of the tree should work fine.
3. Sort child nodes by angle relative to "entry" edge so that you traverse subtrees in, say clockwise order.

This should be pretty good and maybe some more optimization can be added if we visualize it.

[qu1ck]

Another thing we can do for any algorithm as post optimization:

Say the path we found is A1..An, say the longest edge is Ai-Ai+1 Try to find 0<j<i such that if we take subpath Aj-Ai and reverse it in place so that resulting path will be A1..Aj-1-Ai-Ai-1..Aj-Ai+1..An and it's total length is less than initial path. Do the same on the other side of the longest edge.

Repeat the operation reasonable amount of times thus continually reducing overall length.

Each optimization attempt for an edge should be O(n) so for n<300 we can try about n^2 optimizations. There won't be too many large groups on any board anyway.

What do you think?

[Jacajack]

Alt+[1-9] shortcuts already exist and work when focus is in text field. They don't advance the row like N does but Alt+char is used in some locales to enter variations of the character so I'd like to avoid using such shortcut.

That's right, I didn't think of that, but unfortunately unlike N these shortcuts do not advance the selection. One little thing, though - in Firefox Alt+1...9 are used to switch between tabs by default and it seems that you forgot to override the default behavior with preventDefault(). I just fixed that and will submit a pull request in a second (#247).

Regarding spatial ordering, first of all: awesome discussion. You never know when some hardcore CS stuff will pop into relevance even in something so utilitarian in function as bom generation.

That's exactly what I though too! I never thought I would ever have to write a BVH tree to optimize component placement :)

As for the MST method, you're right - DFS will probably be better. Initially I thought it would be more "jumpy" than BFS, but if you start at the end of the longest path in the tree, it should be better. I like the idea of sorting the nodes by relative angle too. I might implement that later and see how it performs. Right now, I'm still playing around with the BVH and I think I can improve it by a lot by changing the order in which the nodes are visited at the end. Maybe the MST-based algorithm will come useful here? We'll see...

Another thing we can do for any algorithm as post optimization: [...]

Sounds like something worth trying, but I have to admit that it's hard for me to visualize in my head how effective that will be. Still, definitely a something to keep in mind :)

[qu1ck]

Sounds like something worth trying, but I have to admit that it's hard for me to visualize in my head how effective that will be. Still, definitely a something to keep in mind :)

The idea here is to see if we can get rid of long jumps between tight sections by flipping start and end points of some tight sections. Here is a visualization (forgive my scribbles in the most advanced graphics editor ever known, ms paint):

When applied a lot of times it will have a tendency to also uncross all overlapping edges and "unwind" the spiral into more of a zigzag.

[Jacajack]

I think this approach can be generalized a bit and replaced with a genetic algorithm (for approximating TSP solution). Maybe then we could determine the optimal order in three passes:

1. Group together close vertices with BVH.
2. Inside each group (leaf) determine the shortest path using said genetic algorithm.
3. Extract the first and last vertices from all these paths and connect them with "mandatory" bidirectional edges. Use similar genetic algorithm to find the shortest path passing through all the mandatory edges.

What do you think about that?

[qu1ck]

I don't think it will work too well because

• it's hard to find the right balance on how small the groupings of close components should be
• It has no flexibility once start and end points of the group are chosen. The chosen start and end may be a local optimum but give much worse overall results because the outside connections are not in a convenient place.

TSP heuristics page has a MST based algorithm and it even has decent upper bound on solution deviation from optimum.

Unsurprisingly someone thought of the edge replacement optimization long before me, it is described on the same page, see "Pairwise exchange" section.

I vote for not treading a new path in this well researched problem.

[qu1ck]

One advantage of following BVH path is that it may generate a route that feels more "natural" even if other algorithm provides a shorter path. We may have to build the alternative and compare the results visually to make a call on that.

[Jacajack]

Okay, I'll try out the k-opt technique and maybe the BVH+TSP combo too if I have some time this week. I'll let you know when I have some results.