Gift Wrapping Points

In this project, i draw 100 points on the screen and i try to finds all the points near the border.


Inspired by this video

Nice project :slight_smile:

Convex hull is an interesting example because it's much easier to do non-digitally: Just bang nails into a board at the points of interest, stretch a rubber band around them all, and let go!

That's an interesting thought.

In Snap! the cloud of points may be modeled as a single sprite. Imagine a straight bar of sufficient length as a second sprite. It will be hinged on the first point that's surely part of the hull, then be turned e.g. clockwise until the sprites are reported to touch. Now the point where the bar touches the point cloud will be the new hinge, etc.

It's probably not a very fast algorithm, nor precise, but it would make a good (visually attractive) demonstration of the convex hull concept. And (I guess) few explicit calculations required!

Huh, yeah, that could work! Why wouldn't it be precise?

That’s a hunch. One would need to actually build it to find out.

This could work, but without being precise:

  1. when the sprite is positioned on a point, it already touches the pentrails...
  2. when the sprite turns on itself until it touches the pentrails, when it touches, it will be on the edge of the point (not in its center)

In project #2, i used raycasting (like an infinite line) to find next point.

Very quick, but not precise (not in the center of the point...)

I need to figure out how to stop it !!! but it work...

Is it bad that I prefer realism over precision? Sure, it doesn't go to the center of the point, but it's much like Brian's example, the rubber band is gonna go around the nail, not through the center of it.

I don't think we have to worry about edges vs. centers. We're talking about points, which in principle have zero extent and on a computer have 1x1 pixel extent.