What are some ways to combine 2+ shapes into one shape? Each “shape” is a list of Vector3s, and I need make all shapes into one shape. The only results I get with google are combining shapes in photoshop and illustrator.

I made this to help portray my question. I have 5 shapes here (pink outlines), and need to make those into the blue shape.

Here is an algorithm off the top of my head for 2D. It requires two functions:

PointInsideShape() - this determines whether a specific point is inside or outside of a shape. The typical solution walks the polyline and checks whether the point is on the right or left of the line formed by each segment. If it is on the same side for all segments, it is inside. Given floating point imprecision, you may have give a very small fudge factor when deciding which side. That is, if the a point is very close to the line, then it can be considered as being on both sides. You will find many posts on the net concerning checking points against polylines.

LineSegment/LineSegment intersection. You will find code posted on the net for this (using a couple of different solutions) for segment/segment intersection. I believe the code in the Math3D script in the Unity Wiki is most of the way there.

In addition, you will need to define a Vector3 that is not possible on any shape. Maybe (Mathf.Infinity,Mathf.Infinity,Mathf.Infinity) will work.

Eliminate all points that are within another shape and whose neighbors are within another shape. Note you cannot eliminate from the original since you need the paths for testing points. Use a copy and set each eliminated Vector3 to the ‘not possible’ value.

Walk the resulting arrays and break out all contiguous sections where the values are not ‘not possible’ into their own array or list.

The results of these two steps will give you a set of arrays of points where the first and last point are inside some shape, but all other points in each array are outside edges of the combined shape.

Start with one of these segments. Test the segment of the last two entries against the line segment formed by the first two and last two of every other segment. When you find an intersection, then you know the next segment to walk. The ordered segments will form one (or more) shapes. That is, you need to make sure that all segments are used. If not, start with an unused segment and form another shape.

Note when working with polylines you always need to consider the wrap of the last point to the first. Sometimes it is easiest to include an extra Vector3 at the end that is equal to the first entry.

Again this works in my head, but 1) I just made it up without referring to any CSci literature, and 2) there may be special cases that I have not considered.