Merge paths

Archived Forums Questions & Answers
1

I have a list of circular paths as an array of Vector3s. These circles highlight an area AROUND two (or more) objects.

16321-untitled-1.png

As the image shows, I have this working fine. However, I need a way of “merging” these paths together to form ONE path around all of the objects. Like the second image shown

16322-untitled-2.png

I was thinking, one way of doing this, could be to use a sphere collider to check whether any of the nodes are within the sphere (from each objects) and then delete those nodes, leaving the outer nodes to render the line. This seems very messy and lots can go wrong.
I am going to use something like LineRenderer to render the line, so it wont have to calculated on each frame (as these are static objects).

Another idea I have, is rather than drawing the circle paths, then manipulating them, is there a better way of getting the group of objects, and calculating the outer path properly...

 –

do the points share the same height?

 –

@vexe Nope. That's what is making it tricky. I am using Terrain.SampleHeight to make the points sit above the terrain, but it means my initial plan of using a shader to merge two texture won't work. I need it as a poly really so I can do further checks to see if another object is within the boundary.

 –

of course, you only care about cases where the two circles intersect/touch each other, right? - And will you ever have your circles each have its own radius, or will you always use a shared one?

 –

yep. Although, there could be more than two circles.

 –

2 Answers

2
3

I upvoted this question because I really like it. I imagine there’s a lot of ways to solve this, you could go all mathy about it, and solve circle equations, intersections and whatnot.

Or (I think a simpler way, not necessarily the best) would be to use raycasting (even a linecast would work) as @raimon.massanet said (I’m not sure if this is what he had in mind), my idea is, to let each of those objects scan its surrounding area just like a radar, the length/distance of how further away from your object you’d scan, is r - delta: r is the radius of the circle, delta is a small value. If the scanner ray ever detect a point, you nuke that point because it definitely doesn’t belong to the current circle (since it’s inside its radius), but to another circle. Do the same for all the other objects.

This will work for any number of circles, regardless of the circles’ radius. But first, again you’d have to project everything to 0 height as per the previous comment from raimon.

Here’s an illustration using the best drawing tool ever exist (MS Paint) - (I think MS now lets you download a trial version)

16333-circles.png

In the first state there’s no intersection, nothing’s happening. In the 2nd, 3 circles intersect, the scratches indicate points that have been deleted, because they’re inside the circle’s radar. Notice how the ray/line scanner doesn’t reach the circle’s area, it’s slightly less than its radius.

Also, in order for your ray/line to detect the points, they can’t be just a Vector3 or else there’s nothing to detect, they have to be gameObjects I believe, you could make a Point class, have it inherit from MonoBehaviour and all it has is a Vector3 property representing its position (returns transform.position)

If you’re a circle, How can you tell if a point is inside you?
Simple, if the distance between you and that point is less than your radius.

I’ve put some simple equations, on where you’d have an intersect between 2 circles, when there’s none, etc in the awesome MS Paint draw as well (dist is the distance between two circles, r1 is the radius of circle1, r2’s the same for circle2)

Again, just yielding some ideas…

I missed your answer in the comments and posted my own, exactly the same answer (+1 for that BTW). A sure sign of an answer is if it has pictures...

 –

I also would like to point out something... > If you're a circle, How can you tell if a point is inside you? is the funniest thing I've ever read on UA

 –

I deleted my answer because it's the same as yours and you posted yours first (as a comment, naughty). You're right Vexe. What needed to be done is to compute the intersection points all mathematical-like, then determine which side should be removed. That would probably be even more performant than checking the distance of thousands of points. Easy, assuming they're ordered correctly in their list/array.

 –

Oh, so the paths are perfect circles? I thought the paths were polygons... Then the solution is much easier, as pointed out buy @Jamora and @vexe, because then you only need to calculate distance to centers. You need to remove a point P if it DOES NOT belong to circle c1 but its distance to the center of c1 is smaller than the radius of c1. You should do that for all points P and all circles different than the circle to which P belongs. This has been suggested before by @Jamora, @vexe and @Bunny83, but I thought I would summarize.

 –
2

I would delete the points in one path that are inside the area defined by the other path, and vice-versa. You can use ray casting for that:

http://en.wikipedia.org/wiki/Point_in_polygon

You should end up with the points that are in the boundary.

Since the shapes are circles it's easier to simply check the distance of a point from the other circle midpoint. If it's smaller the radius of the circle it's inside. In the end you have to find which "end" of one arc is connected to which other arc. It might be possible to save some hints during point elemination to make this task easier.

 –

@Bunny83, Checking the radius has already crossed my mind, however, this wont work, as some of the circles could be smaller than others.

 –

@verenion: That's not a problem at all ;)

 –