# Connecting two polygons

This topic is 4168 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I have an abitrary polygon (convex or concav) from which I know all vertices. The directions of the vertices is clockwise. Now I translate this polygon to a specific position. What I want to do now is to join the original polygon and its copy to one polygon. To give a better understanding I have drawn some example pics: The original polygon, in this case a deltoid, is black and its copy is green. I know all vertices from both the original and copied polygon. Now to connect both polygons I have to find out the red colored vertices. But how do i get them? If I haven't something precisely explained, please let me know.. Thanks in advance.

##### Share on other sites
If your original polys are always convex, then it might be easier to just find the smallest convex hull created by the old and new verts.

However if your input polys are also concave, then you'll need something else. Off the top of my head, it seems that (P2,P6) and (P4,P8) are the only new edges which don't cross an existing edge. You should be able to test each potential new edge and discard all the others. Once you've found your new edges you should be able to start from a point on one of them (say, P2) and walk around the edge of the new shape.

##### Share on other sites
You are right with saying that the edges (P2,P6) and (P4,P8) are not crossing but I need P1 and P7 for my new poly as well. And thats the problem: (P1, P5) and (P3, P7) are crossing, thus this doesn't work.

##### Share on other sites
I may be dead wrong about this, but it would seem sufficiently simple to determine the maximum and minimum vertices of the polygon in the direction orthogonal to the translation.

You could calculate

c = ty*px - tx*py,

where (tx,ty) is the translation and (px,py) is a vertex. Then find the maximum and the minimum c. Those will correspond to the vertices forming the two edges of the extruded polygon. In your case vertices P2 and P4 of the original polygon.

After these two vertices have been identified the polygons have to be "clipped". By clipping I mean pruning out the vertices which are between the two vertices on the "inside". Inside of the first polygon is the side (tx,ty) is pointing to and for the second polygon it is the opposite direction. Now forming the polygon should be just simply connecting the end points of the pruned non-closed polygons and thus closing the final polygon.

Is this what you were looking for?

##### Share on other sites
Quote:
 Original post by NMOYou are right with saying that the edges (P2,P6) and (P4,P8) are not crossing but I need P1 and P7 for my new poly as well. And thats the problem: (P1, P5) and (P3, P7) are crossing, thus this doesn't work.

You get those by 'walking' the edge of the shape. If you've found (P2, P6) as a new edge, you can start by adding those verts. Then find P6 in the new shape and step through the points within it until you come to the point in the other edge (P8). Then repeat the process and walk from P4 to P2, picking up P1 in the process. Since your points are all stored in clockwise order this should be simple (although you might need a bit of vector maths to determine whether to walk clockwise or anticlockwise).

##### Share on other sites
For a convex polygon, wouldn't it be the case that any time you have two edges cross (as in figure 2), both are not needed? This gets rid of everything except P5-P6 and P3-P4, but you can recognize those as being unneeded because, after having removed the known-bad edges P3-P7, P5-P8, P1-P5, and P2-P3, P3 and P5 are each only connected to one edge.

I don't have any kind of proof that this will always work, let alone be efficient, but it seems like it should work.

Edit: more generally, you can always remove any two edges that cross; you can then remove any edges where one endpoint of the edge is connected only to that edge. The second step may have to be iterated, depending on the number of edges in your polygon.

##### Share on other sites
There's an entire class of algorithms, including this "construction of a convex hull" problem you're after, called "rotating caliper" algorithms. Hit up wikipedia for that, as well as the link below...

http://cgm.cs.mcgill.ca/~orm/rotcal.html (you're interested in "merging convex hulls")

##### Share on other sites
Decided to quickly implement the idea I mentioned previously in this thread:

typedef struct sVertex{    float x;    float y;} vertex;/* Extrudes the given polygon * vin = input vertices (ordered ccw or cw) * size = count of input vertices * vout = pre-allocated are for output vertices (size+2) * trans = translation */void extrude(vertex *vin, int size, vertex *vout, vertex *trans){    int     minIdx = 0,  maxIdx = 0;     int     startIdx = -1, endIdx = -1;    float   minC = FLT_MAX, maxC = FLT_MIN;    float   dot;    int     i, j, prev, in = 0;    /* Find the min and max vertices wrt to translation */    for(i = 0; i < size; i++)    {        float c = vin.x*trans->y - vin.y*trans->x;        if(c < minC)            minC = c, minIdx = i;        else if(c > maxC)            maxC = c, maxIdx = i;    }	        prev = maxIdx==0 ? size : maxIdx - 1;    dot = (vin[maxIdx].x - vin[prev].x) * trans->x + (vin[maxIdx].y - vin[prev].y) * trans->y;    if(dot > 0)        /* Starting from maxIdx preserves direction */        startIdx = maxIdx,        endIdx   = minIdx;    else        /* Starting from minIdx preserves direction */        startIdx = minIdx,        endIdx   = maxIdx;    in = endIdx < startIdx; /* Are we already at extruded point? */    for(i = 0, j = 0; i < size; i++, j++)    {        if(in) /* Are we extruding? */        {            vout[j].x = vin.x + trans->x;            vout[j].y = vin.y + trans->y;        }        else            vout[j] = vin;        if(i == startIdx) /* Start extruding */        {            j++;            vout[j].x = vin.x + trans->x;            vout[j].y = vin.y + trans->y;            in = 1;        }        if(i == endIdx) /* Stop extruding */        {               j++;            vout[j].x = vin.x;            vout[j].y = vin.y;            in = 0;        }    }}

Much of the branching can be quite easily moved out of the for-loop, however, I'll let someone else to do that ;)

##### Share on other sites
Wow, thank you all guys!!
I am overwhelmed how much help I get offered.
Now I have everything I need.
Again thank you all!

1. 1
2. 2
3. 3
Rutin
22
4. 4
5. 5

• 13
• 19
• 14
• 9
• 9
• ### Forum Statistics

• Total Topics
632936
• Total Posts
3009310
• ### Who's Online (See full list)

There are no registered users currently online

×