Attached is a demo of a new node: Good_center. Good_center finds a reasonable center point guaranteed to be inside a shape (unlike centroid, which can fall outside a shape).

The attached screenshot shows 9 random shapes. For each, the blue dot shows the position of that shape's centroid and the red star shows the position returned by good_center.

As you can see, good_center always falls inside its shape, no matter how strange. It works for shapes with multiple contours including holes (like the letter A) and disjoint contours (like separate islands in a nation). It lands well into the interior of its shape, often at or near the spot most people would identify as its visual center.

Good_center helps determine the placement of labels in my new place_label node. You can see it in action in the screenshots I posted of the world map in the place_label documentation and the five-way Venn diagram in the overlaps documentation:

http://support.nodebox.net/discussions/show-your-work/559-world-map...

http://support.nodebox.net/discussions/show-your-work/562-overlaps-...

Good_center uses a heuristic algorithm that almost always lands in a reasonable "center" spot without consuming too much processing time. It stars with a grid of 100 spots spread across the bounding box of the shape, deletes those not inside the shape, then measures the distance from each spot to 50 edges of the resampled shape to find the find the minimum distance to an edge. It repeats this for all spots and then takes the spot with the largest minimum distance from an edge (the "farthest inside"). It then starts at this center and repeats the process at half scale to zero in on an even better spot.

Limiting the number of candidate spots and the resampling resolution reduces the processing time at some loss of precision. But after extensive testing on many different kinds of shapes, I found this was a good tradeoff. This node generally produces reasonable center spots; increasing the resolution significantly slowed the performance while producing almost no noticeable improvement in most cases. In short, the centers produced by this algorithm are "good enough".

In addition to labeling, good_center is useful any time you want to place a smaller shape inside an arbitrary larger shape without crossing outside the boundary. Compare with another new node, true_center, which does find a perfect center point but only works for regular polygons and stars.

Good_center will be included in the next rev of my Cartan Node Library.

Enjoy!

John