A new algorithm for finding a visual center of a polygon | Hacker News Reader

A new algorithm for finding a visual center of a polygon

mapbox.com

119 pointslobo_tuerto32 comments

While their approach is clever, it is not guaranteed to converge in a fixed number of iterations. Author states that constrained Delaunay Triangulation is "slow and error-prone". I disagree -- I've implemented parallel and recursive Delaunay on GPU before, and it converges in a fixed number of recursions -- for a taste of the general approach, see here:

http://www.comp.nus.edu.sg/~tants/jfa/i3d06-submitted.pdf

JFA could certainly be "abused" for this purpose.

For those who don't immediately know what JFA stands for:

http://www.comp.nus.edu.sg/~tants/jfa.html

Thanks for posting this. I was convinced that Delaunay triangulation was a good example of irregular parallelism - something that fundamentally doesn't work well on a GPU, and have been telling people this for years, so I'll look forward to reading the paper. (A Voronoi diagram is just a different way to show a Delaunay triangulation isn't it?)

I was running this on (high end) GPUs back in 2011, in real-time (30fps), on 1920x1080 video textures. I can confirm that the clever recursion and performance of this is mind-boggling. Oh, and you get a distance transform out of it as an intermediate step, just for giggles. My general take is that while linear kernel-thinking in parallel might get nowhere, this is a prime example of recursion solving the problem when parallelism is available. I wish I could claim to have invented it... :)

That sounds fascinating, can you explain the project a bit more?

We were doing GPU-based 2D-3D conversion for HD and 4K and one of the intermediate steps required that we compute a DT (distance transform), and JFA was perfect for this. The DT was used along with a Hough transform (also real-time) to conduct vanishing point and geometry analysis.

> A Voronoi diagram is just a different way to show a Delaunay triangulation isn't it?

Yes, Voronoi and Delaunay are duals of eachother, so you can flip between them. Edges of one turn to vertices of the other and vice versa.

> While their approach is clever, it is not guaranteed to converge in a fixed number of iterations.

Are you sure about it? I struggle to find a case where the quadtree version of their algorithm would not converge.

I didn't mean to imply that there were cases where it would Never converge, just that the number of iterations is not a-priori fixed or predictable.

My intuition is that the worst case scenario would be a fractal-like curve with multiple solutions (imagine a snake-like polygon following a Hilbert pattern). In that case the algorithm would need to explore all of the smallest squares, that gives us a higher bound on the number of iterations. It will be far less in most cases.

Would the delaunay-based algorithm be faster in the worst case?

Beautiful! I would love to see an animation of it in action (a la https://bost.ocks.org/mike/algorithms/)!

By pure coincidence, I just had a discussion at work the other day on how to automatically place labels for clusters on tSNE plots. It looks like all I need is a sensible way to convert the points to a polygon first (convex hull won't work here, for obvious reason)

There are ways to get the most "typical" (I think there is a better term for that) sample of a cluster, which should usually lie in the center of the cluster. AFAIK that's the traditional way to achieve what you are trying to do.

Try compute the median point across all members of the cluster then compute the cosine similarity between each point in the cluster and the median of that cluster and use the most similar as your label point.

The clusters on our tSNE plots tend to be stretched out, have concave bits and en up intertwined - we'd have the exact same problem outlined in this article.

In fact, that was the whole reason we started discussing it, since I initially proposed just doing what you suggested

Good to know! I must've been lucky, since most tSNE plots I've worked with were pretty tame in that respect.

Look up Alpha Shapes.

Thank you! I knew it was a matter of finding the right keywords to search for. Time to experiment a bit.

EDIT: Oh, wait:

> Basic alpha shapes are based on the Delaunay triangulation.

At that point we might as well go for DT based approaches, don't we?

What's wrong with "the lawnmower approach"? Imagine you're mowing the lawn in a spiral from the outside in. When a section is completely mowed, just continue spiraling in the remaining area. The center is the last place with high grass. The only drawback I see is that you could get multiple answers for certain shapes. But for the ones in the post, I think the answer is about the same.

Im not sure about the exact cost, but at first sight this approach would still require a lot more operations per line - you need to keep the lawnmower inside by measuring distance/intersection to closest edge, plus track the already mowed area. Maybe making the lawnmower wide enough could make it fast and accurate enough for specific use cases.

That's equivalent to calculating the "straight skeleton", which is mentioned in the article as being among the published solutions, but too slow and error-prone.

https://en.wikipedia.org/wiki/Straight_skeleton

There's no explicitly spiraling/lawnmower aspect to the straight skeleton: you may have a raster-based incremental literally spiralling solution in mind, but for the geometric examples they show this would probably be inefficient. It's going to have to traverse a large multiple of the perimeter of the polygon as it spirals.

That would give you the thickest part of the shape, not necessarily the center. If I'm understanding correctly anyway. E.g. imagine a long skinny shape with a big thick circle at the end. The lawnmower would finish shaving the main part of the shape and declare the circle the center!

If I had to design an algorithm to do this, my idea would be to sample a bunch of points on the polygon, then take their median x and y values. Then find the closest spot on the polygon to that value, if it's not inside the polygon.

> That would give you the thickest part of the shape, not necessarily the center.

But we're looking for the "visual center," defined in the article as "a point inside a polygon with as much space as possible around it."

Right, but I think that definition falls apart if you look at pathological shapes instead of nice convex ones. If you just randomly generate polygons, the thickest part of the shape can appear anywhere, including a very far off edge. And if you cut a tiny opening into that part of the shape, the center would completely move.

I was imagining a solution that I think is equivalent to what you suggest. repeatedly shrink the object by a one (or small n) pixel margin. When there's nothing left, back up one step. You'll have one (maybe a few) tiny object that should be inside your largest inscribed circle and near its center.

Too late to edit(?) so self-reply.

This shows the shrinking approach (and was a fun excuse to play around with octave-image): http://imgur.com/a/cM8TU

But does the "pole of inaccessibility" actually work?

Imagine a long rectangle.

The pole of inaccessibility will be a range along most of the length of the rectangle... it won't find the center at all!

Even the illustrated "coastline" example is horizontally centered only by chance, because that happens to be the thickest part.

So not clear at all this finds a plausible "visual center" by any means.

If you read the article, you'll see that one of their optimizations is to start with the centroid of the polygon, sort, and then discard ties, so it should still get the correct answer for your described shape.

> The pole of inaccessibility will be a range along most of the length of the rectangle

How could it be a range like that? Surely some points on the range would be closer to the short edges than others, making them more accessible?

The range is a line parallel to the long edges that runs down the center of the rectangle. It ends when it gets closer to the short edges than it is to the long edges.

Interesting - but how does the author know this isn't already present in proprietary software, but hidden? I get a little nervous about claims to novelty when e.g. Esri has decades of research behind its labelling algorithms.

Clever. I love to see when complex problems can be easily approximated using existing algorithms and techniques. Very cool!

Reply on news.ycombinator.com