5

I'm interested in calculating the "optical alignment" of an icon. For example:

enter image description here

If you're familiar with UI design, you know certain icons, such as the "play" button triangle as demonstrated above, often feel out of place. Even though the rectangular bounds of the icon are technically centered, the icon still doesn't feel centered. This is because of the uneven distribution of the icon's surface area.

What I've tried:

It's funny, when I was researching this before asking, after Googling "volumetric center icon", the first Google result that came up was a question I asked at Mathematics Stack Exchange on this very same topic 2 years ago, with no answer.

On Math SE there is a similar question, but as it uses a JPEG image as its example, the solution that answers are pointing out is to use the pixel grid to calculate the solution. I could of course render the vector icon on HTML5 canvas (I'm a web developer and would ultimately like to do this in JavaScript, even though I'm just tagging this as "algorithm") and count pixels but that would be an ugly approach to say the least.

I'm wondering if there's any algorithm I can use to calculate the volumetric center of a vector icon or even simply the optical alignment (which could be done manually by drawing the smallest circle possible around the icon as shown above, but I'm interested in an automatic approach). I realize this may be a challenging question, because a vector icon could have any number of shapes combined to make it, vector shapes can have holes in them, etc.

Question:

Does anyone know how to write such an algorithm? When it comes to complex math algorithms such as this, I don't know where to begin.

Note: There is this question but it seems to be only asking about polygons, and answers don't address odd curves.

Community
  • 1
  • 1
  • I'd like to point out as an after thought: I do realize that the volumetric center and optical alignment are two slightly different things - I'm interested in whichever one is easier to calculate. –  May 19 '17 at 13:25
  • 1
    Is the icon in the middle always a polygon? If so, you can collect all the points and determine the polygon centroid, then find the difference between that and the circle center to figure out how much you're misaligned by. Simply move the shape by the negative of that vector to align it. – Asad Saeeduddin May 19 '17 at 13:31
  • @AsadSaeeduddin No, the question is about "any vector shape" which includes any curve and line segment combination imaginable. –  May 19 '17 at 13:33
  • you can overlay an arbitrarily precise polygon over a curve and calculate the centroid from that... – Grady Player May 19 '17 at 13:34
  • 1
    Awesome question! The first thing that comes to mind is to tesselate the overall shape into triangles (since for triangles there is a simple equation of mass center and area) and then calculate their common center of mass based on the set of weighted points: (X; Y) — mass centers, W — area. – hidefromkgb May 19 '17 at 13:35
  • In that case, you need to perform some form of geometric decomposition to find actual functions to represent your curves, then perform integration on those to find the first moment of area, then use the first moment of area to determine the centroid. This becomes complicated very quickly, so you might also consider a numerical approach. You should look at the math for how Civil Engineers find the centroid of arbitrary beam shapes, you are solving the same problem. – Asad Saeeduddin May 19 '17 at 13:36
  • I don't think you gain much from using triangles.. unit squares would be just as good, and if they aren't... then use smaller units until they are :) – Grady Player May 19 '17 at 13:36
  • @AsadSaeeduddin Yes I realized that this question, while having a seemingly simple goal, might have a very complex answer. Because we aren't even just trying to find the center of a single shape really - The problem I'm trying to solve is centering vector icons properly, which could be a combination of different shapes, or even shapes that subtract area from the icon rather than add to it - yikes. Maybe it isnt even possible to find a viable solution! It's definitely a harder question than it seems at first. –  May 19 '17 at 13:40
  • @hidefromkgb That's an interesting suggestion, but as GradyPlayer sort of pointed out, wouldn't that essentially be the same thing as "rendering" the icon on a low resolution, then counting pixels? If that's the only way then it's not so hard to do... but it sure wouldn't be elegant would it? –  May 19 '17 at 13:46
  • @Viziionary, no it wouldn\`t! This is a [triangulated polygon](https://upload.wikimedia.org/wikipedia/commons/6/67/Polygon-ear.png). I\`m not suggesting to subdivide the plane into a regular triangular grid, but rather to subdivide the input poly. – hidefromkgb May 19 '17 at 13:51
  • @hidefromkgb Oh, but what about the weird curves that could be involved in any vector shape? –  May 19 '17 at 13:52
  • @Viziionary, any curve can be approximated with a polygonal chain, given the necessary precision. – hidefromkgb May 19 '17 at 13:54
  • @hidefromkgb Oh ok. My mistake. –  May 19 '17 at 13:55
  • @Viziionary It is not a novel or impossible problem, it's been solved over and over in many different fields (CFD, FEA, image processing, etc.). You're simply looking for the centroid. Whether you can determine the precise centroid analytically depends on what limits you can set on your input and how much work you're willing to put in. In general, people just use some kind numerical integration scheme because they *can't* prescribe any limits on their input. – Asad Saeeduddin May 19 '17 at 14:17
  • @AsadSaeeduddin I see. I just meant that it's a much more difficult problem than I would've imagined - it's become apparent that the solution is significantly more computationally expensive (and logically complex) than a typical algorithm for calculating area or volume or anything of that nature. –  May 19 '17 at 14:26
  • @Viziionary Working out the area or volume or whatever of an arbitrary shape works exactly the same way; you numerically integrate tiny strips of the shape; the only difference is that you skip the bookkeeping of distance-weighted areas I'm doing in the algorithm below. When working out the area you'd just add the "occupied lengths" up. – Asad Saeeduddin May 19 '17 at 14:31
  • @AsadSaeeduddin thanks for all the explanation. –  May 19 '17 at 14:41

1 Answers1

1

What that article refers to as "real center" is technically known as the centroid of the object. For simple shapes like triangles, or even for arbitrary polygons, there is formula you can just plug the bounding points into to obtain the centroid. For example, the Wikipedia article on centroids shows how to determine the centroid of a triangle, which agrees with the results shown in the article you linked.

Unfortunately, with vector graphics you have a slightly harder problem, because the bounding curve can be just that; any arbitrary curve. In such a case, it is easiest to use numerical integration to determine the centroid. Here is an outline of an algorithm (you can look here for an implementation if you're familiar with MATLAB):

  • Determine the bounding box of your shape
  • For each of the x and y dimensions:
    • Split the bounding box into a suitable resolution of evenly spaced sample points
    • At each point:
      • Determine the "occupied length" in the direction orthogonal to the one you are iterating in.
        • For convex shapes, the occupied length is simply the difference between the two boundary points
        • For concave shapes you will may have multiple boundary points and will need to determine which jumps are occupied (off the top of my head, every alternate pair of boundary points is occupied, starting with the outermost pairs being occupied)
      • Additionally, determine the centroid of the "occupied length". Finding the centroid of a bunch of collinear lines is not hard, so I'll leave this as an exercise
      • Store the product of the "occupied length" and its centroid
    • Average all of the weighted occupied lengths to find the centroid in the dimension orthogonal to which you are iterating

Once you have the centroid in both directions, you know the "real center" of the shape.

Asad Saeeduddin
  • 46,193
  • 6
  • 90
  • 139
  • This (subdividing the plane into an evenly-spaced grid) is exactly the approach that the OP is trying to avoid. – hidefromkgb May 19 '17 at 13:56
  • @hidefromkgb I've looked at the question again, can't see where this is mentioned. However, unless you try to build approximating functions for arbitrary bounding curves, or dismiss the possibility of having icons that cannot be decomposed into simpler regular shapes, avoiding numerical integration is impossible. – Asad Saeeduddin May 19 '17 at 13:59
  • @hidefromkgb Also, I don't actually know *why* you would want to avoid numerical integration, since you can get good results with good performance, and assuming you check boundaries via your vectorized representation, can scale this approach up to arbitrary precision. – Asad Saeeduddin May 19 '17 at 14:01
  • If this is the most reasonable approach, and there doesn't exist a much more efficient approach with better performance then I'm not against it. I just always try to use the most efficient and "clean" approach to any problem. –  May 19 '17 at 14:03
  • @AsadSaeeduddin, this is so, beyond doubt. But i still consider my curvature-based tesselation approach followed by a simple weighted sum a better one. – hidefromkgb May 19 '17 at 14:03
  • @hidefromkgb You could try it out, but it is much more difficult in terms of implementation complexity and computational expense, and is more likely to have pathological cases where the icon tesselates poorly. I've had some experience with automatic triangular grids in CFD, and you almost always need to go in and substitute features with a regular grid to get suitable resolution. – Asad Saeeduddin May 19 '17 at 14:12