Convex Hull Experience?

Does anyone have any experience with, or have code to, create a convex hull?

I’ve ported one from Java, but it’s not behaving and I’m not sure if the code was broken, if my port sucks or other…

Help is appreciated!

Chris,

I put together a quick project that uses the Jarvis March method:

It’s almost entirely based on a port from this code

And you can download the sample project here

Enjoy!

  • Jim

Well that’s really cool.
That’s just a 2D Convex hull right?
I am absolutely going to use that ---- and take credit for it! (joke).

But do you also have 3D convex null experience?

It’s just 2D, and you are welcome.

This algorithm isn’t useful for more than 2 dimensions (planar). I doubt I’ll have time to convert one of the other n dimension algorithms into Xojo.

  • Jim

the 2d is awesome. Really awesome!

Thanks.

I’m kind of mesmerized by it. Have been watching it for at least five minutes …!

I watched it for more minutes than I would like to admit. It’s mesmerizing.

Thank you for sharing the code, Jim!
I noticed the project gets into an endless loop if you set two identical points like when you double click as I did occasionally, so I took the freedom to fix that and replaced the point class by Xojo.Core.Point.

Because the question how to determine if a point is inside a path comes up here from time to time, I added two different versions of the even/odd rule and a fast implementation of the WindingNumber algorithm which should give accurate results even in paths intersecting themselves*. Both rules will determine that left and bottom corner points are inside while the others are marked as outside, so for an accurate result one should probably check if the point to test is identical to one of the path’s points.

The code is here.

  • Which are not connected to the convex hull code necessarily (makes no sense because of course all the points in a hull are inside). I was just too lazy to write drawing code on my own.

Ulrich: I tried downloading your code which appeared as a .dms file that I was unable to open. (I am Mac user)

Just manually change it to .xojo_binary_project

Sorry, I forgot to zip it!

Zip it! :wink:

Ok. Here is a zipped version.

having little trouble with it. I converted the x and y of the Point2D to doubles. I’m eliminating points that are close to being identical.
Sometimes It gets into an endless loop, but oddly I can’t even break in with a breakpoint.

Thoughts?

Try my version. This was caused by two points sharing the same position, and because there is a compiler pragma in the code to get a small speed boost, the debugger cannot step in.

I found the bug. I forgot to increment my count of cups of coffee by 1 between major edits… Sorry all.

you too? that happens to me on a regular basis.
and some days there isn’t enough coffee in the state to do its job.

—sb

Grind my own, brew it strong!

Hmm, maybe a convex hull coffee plot is necessary ??

http://www.instructables.com/id/IoT-Coffee-Pot-Monitor/

We might be getting a little bit off topic somehow … :smiley: