1

3 trapezoid and a polygon

Given 2 or 3 trapezoids (orange). At least one side of each trapezoid is adjacent to another trapezoid, forming a simple polygon.

Rectangles represented as a list of four points, starting from the left top most corner and going clockwise, e.g 

[
  {x: 0,  y: 0},
  {x: 50, y: 0}, 
  {x: 75, y: 30},
  {x: 60, y: 30}
]

The task is to make a single polygon (green) that would be represented as a list of points:

[
  {x: 0,  y: 0},
  {x: 50, y: 0}, 
  {x: 75, y: 30},
  {x: 60, y: 30},
  {x: 60, y: 170}
  …
  {x: 0, y: 0}
]
4

2 回答 2

1

  1. create list of all points (code below is static-allocated for simplicity)

    const int _max=128;     // max number of points
int pnts=0;             // actual number of points
double pnt[_max][2];    // points
// add points to pnt,pnts

  2. create structure for polygon (also static for simplicity)

    _struct poly
    {
    int p[_max];        // index of points used
    int n;              // number of points
    poly() { n=0; }
    };

  3. create a list of polygons (for your trapezoids)

    • each trapezoid is a single 4-point polygon
    • convert points to indexes in pnt[]
    • in pnt table must not be a duplicate point !!!

    • (+/-) some accuracy

      const int _maxp=16; // max number of polygons _poly poly[_maxp]; int polys=0 // add trapezoids to poly,polys

  4. now just merge everything what can be merged together (something like this)

    _poly o;                // output merged polygon
_poly *p;   
int i,j,k,a0,a1,b0,b1;
o=poly[0];              // start merging with first polygon
poly[0].n=0;            // after merge mark it as empty

for (p=poly,i=0;i<polys;i++,p++)
 if (p->n)              // ignore empty polygons
  for (a0=p->p[p->n-1],a1=p->p[0],j=0;j<p->n;j++,a0=a1,a1=p->p[j])
   for (b0=o.p[o.n-1],b1=o.p[0],k=0;k<o.n;k++,b0=b1,b1=o.p[k])
    {
    if ((a0==b1)&&(a1==b0))         // if polygons share anti-parallel line then merge them
        {
        _poly t=o;
        for (o.n=0;o.n<k;     o.n++) o.p[o.n]=t.p[o.n];
        for (i=j  ;i<p->n;i++,o.n++) o.p[o.n]=p->p[i];
        for (i=0  ;i<j   ;i++,o.n++) o.p[o.n]=p->p[i];
        for (      ;k<t.n;k++,o.n++) o.p[o.n]=t.p[k];
        p->n=0; i=0; j=1; break;    // mark used polygon as empty and restart from beginning
        }
    if ((a0==b0)&&(a1==b1))         // this is never true if all polygons have the same winding
        {
        // if not then just do merge also but in the oposite direction then above
        }
    }

  5. notes

    • use dynamic lists instead of static allocation
    • to be sure you can check the winding of the input data and correct it before merge
    • this works only if the polygons have the same shared points
    • if not then you need to add line in line detections but that can lead to polygon splitting/overlapping and that is another story (much much more complex)

Hope i did not make a silly mistake somewhere (especially in the merge fors) but I think its clear enough to see the idea behind anyway.

于 2013-11-09T09:37:43.813 回答
1

Since we have all the points on the trapezoids in clockwise orders, let's think of these as sets of directed edges or 'arcs' instead (arrows between successive points, with wraparound).

The arcs we want to exclude are exactly the internal arcs in the polygon, which all come in pairs. I.e. if [a,b,c,d] is one trapezoid, and [d,c,x,y] is another, then my polygon should be [a,b,c,x,y,d], which excludes the pair of arcs (c,d) and (d,c).

You can find the arcs you want to exclude in linear time (via a hash or adjacency matrix). Then finding your polygon is just a matter of stitching the remaining arcs together in order.

Say we're mapping points to their neighbors. In my above example, this would look like: a->(b), b->(c), c->(d,x), d->(a,c), x->(y), y->(d)

After excluding the one bad arc pair (c to d in both directions), we have: a->(b), b->(c), c->(x), d->(a), x->(y), y->(d), as desired.

于 2013-11-09T14:38:10.250 回答