I’m trying to draw a path around a cluster of objects. I have a vector of objects, each of the objects representing a circle. They have a middle (ofPoint) and a width and a height.
Now I’m trying to draw a shape with vertexes around this cluster. I attached an image of what I’m trying to do.
The problem is that I don’t know how to detect which objects are on the “outside” and how to calculate where to put the vertexes.
Sounds like a convex-hull problem. You would probably have to create a set of points defining the boundary of each shape and input that set of points into the convex-hull algorithm.
im working on something exactly the same as you in box2d, where im drawing a wobbly line around a number of clustered circles.
convex hull sounds like a good idea, although it will give you a nice round shape around each circle, but a straight line between the circles. so it depends if you are happy with that and don’t mind if the line is not curved all the way around. you’d be able to smooth it out by drawing with ofCurve() and actually that might look pretty good.
ive taken a different approach in box2d where im casting a ray from the center of the cluster and checking the last point it hits (the perimeter of the cluster). i then use those points to draw a line around the cluster using ofCurve(). im finding that the fewer points i use with ofCurve(), the smoother the line looks but it tends not to be as accurate, so sometimes you do get some of the circles going outside of the line.
be interested to hear if anyone else has any other approaches…
Thank you guys, that was awesome.
I ended up using the Convex Hull algorithm. I used cos and sin to find points on the edges of all my ellipses, and then I inputted those points into the algorithm. I used the Convex Hull Approximation algorithm, as it is very fast and works.
I found a c++ implementation on this page: