How can I combine shapes(List Vector3)?

Archived Forums Questions & Answers
1

Hello!

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.

alt text
alt text

Thanks for your time!

forum thread: http://forum.unity3d.com/threads/calculating-rpg-radial-movement-bounds-range.271282/

Probably useful: http://gamedev.stackexchange.com/questions/71328/how-can-i-add-and-subtract-convex-polygons

 –

Sir! Have you solved the problem?! Could you please share your solution (preferably the Script) with us? I need to solve this exact problem for different reasons and it would help me very much if you could post about how you solved it! Thank you for your time! =]

 –

3 Answers

3
3

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

  1. 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.
  2. 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.

hey thanks! I'll give this a go!

 –

I managed to get something that works! However, I still must be a little (or very) off because when I do more than one shape, I get unsatisfactory results. Left Side: One shape, working as planned! Right Side: 4 Shapes, must be missing a step.. ![alt text][1] [1]: http://i57.tinypic.com/2ptxa2c.png

 –

Are you sure your line segment tests are segment to segment, not line to line or line to line segment? Are the shapes on the one on the right the ones in your example above? Usually when I implement something this complicated, I have to debug it. Start with two simple polylines...hexagons for example...and then dump the points and the intermediate results and work things out by hand.

 –

Cool, solved I think! To fix that bug, I tested if the start point is inside the shape to add. If it is, I loop through and find other points that are inside that shape, and add those points to the end of my Vector3 list (Reorder my points to fit my needs). Thanks a ton, robertbu! ![alt text][1] [1]: http://oi58.tinypic.com/15f6u0m.jpg

 –

Could I have the script for this, by any chance?

 –
2

What is this shape you are talking about? How are the V3s represented on screen?

From the sound of it, you could just take one of the Lists and then add all the elements from the other lists to via Add(elementToAdd).

If it’s a mesh, you can use MeshCombine.

each "shape" is a list of Vector3s. Every segment of each shape is drawn from one point to another (Debug.DrawLine(point*, point[i+1], Color.magenta). I did this merely to visualize my problem. The goal shape is the blue shape. I've updated my original post to show the representation of each point better.* I have a version that creates meshes for each shape, and then combines them using MeshCombine, but that doesn't seem to be the best way since all the points that are inside the edges are still there for no reason.

 –
4

Could I have the script for this, by any chance?