Boost logo

Geometry :

Subject: Re: [geometry] Boost.Geometry boolean operation usage on many polygons.
From: josh.kim0323 (josh.kim0323_at_[hidden])
Date: 2012-11-27 14:35:30


Hi Bruno, here is my code.
basically this function booleanize gets 10 input arguments.
opcode determines which boolean operation should be performed,
int **polygonList = holds coordinate information for each polygon
int *vnumList = holds number of vertices in each polygon
int pnum = total number of polygons in the list

So I try to convert the input formats to boost.geometry formats, and
perform boolean operation.

Please take a look at the pictures in the first thread, and explain what
I"m doing wrong, or why is it behaving that way.

Thank you for your support!!

-----------------------------------------------------------------------------------------------
-------------------------------------- code begins here
------------------------------
-----------------------------------------------------------------------------------------------

void C_BoostGeometryLibService::booleanize(

int opcode,
int** polygonList1, int* vnumList1, int pnum1,
int** polygonList2, int* vnumList2, int pnum2,
int*** resultPList, int** resultVList, int* resultPnum

) {

  multi_polygon polyset1, polyset2, tmpPolySet, clippedPolySet,
resultPolySet;
  BGPolygon polygon;

  int doClip = 0;

  int minx, miny, maxx, maxy;

  minx = (this->boolWindow).min_x;
  miny = (this->boolWindow).min_y;
  maxx = (this->boolWindow).max_x;
  maxy = (this->boolWindow).max_y;

  vector<BGPoint> polyPoints;

  double diffTime = 0.0;
  int i,j;
  int poly_x, poly_y;

  for (i = 0; i < pnum1; i++) {

    for (j = 0; j < vnumList1[i] - 1; j++) {

      poly_x = polygonList1[i][j*2];
      poly_y = polygonList1[i][j*2+1];

      polyPoints.push_back(make<BGPoint>(poly_x, poly_y));
    }
    boostG::assign_points(polygon, polyPoints);
    boostG::correct(polygon);

    myTimer.setTimer(Eprecision::millisec);

    if (intersects(polygon)) {
      fprintf(stdout, "how is input polygon self intersecting?\n");
    }

    boostG::union_(polyset1, polygon, tmpPolySet);
    boostG::correct(tmpPolySet);

    if (intersects(tmpPolySet)) {
      fprintf(stdout, "how is tmpPolySet self intersecting?\n");
    }

    diffTime = myTimer.checkTimer();
    (this->boolTime) += diffTime;

    boostG::assign(polyset1, tmpPolySet);
    boostG::correct(polyset1);

    if (intersects(polyset1)) {
fprintf(stdout, "how is polyset1 self intersecting?\n");
    }
    boostG::clear(tmpPolySet);
    polyPoints.clear();
  }

  for (i = 0; i < pnum2; i++) {

    for (j = 0; j < vnumList2[i] - 1; j++) {

      poly_x = polygonList2[i][j*2];
      poly_y = polygonList2[i][j*2+1];

      polyPoints.push_back(make<BGPoint>(poly_x, poly_y));
    }

    boostG::assign_points(polygon, polyPoints);
    boostG::correct(polygon);

    myTimer.setTimer(Eprecision::millisec);

    boostG::union_(polyset2, polygon, tmpPolySet);
    boostG::correct(tmpPolySet);

    if (intersects(tmpPolySet)) {
      fprintf(stdout, "how is tmpPolySet self intersecting?\n");
    }

    diffTime = myTimer.checkTimer();
    (this->boolTime) += diffTime;

    boostG::assign(polyset2, tmpPolySet);
    boostG::correct(polyset2);

    if (intersects(polyset2)) {
fprintf(stdout, "how is polyset2 self intersecting?\n");
    }

    boostG::clear(tmpPolySet);

    polyPoints.clear();
  }

  if (intersects(polyset1)) {
    fprintf(stdout, "how is polyset1 self intersecting???\n");
  }
  if (intersects(polyset2)) {
    fprintf(stdout, "how is polyset2 self intersecting???\n");
  }

  myTimer.setTimer(Eprecision::millisec);

  if (opcode == OR)
    boostG::union_(polyset1, polyset2, resultPolySet);
  else if (opcode == AND)
    boostG::intersection(polyset1, polyset2, resultPolySet);
  else if (opcode == DIFF)
    boostG::difference(polyset1, polyset2, resultPolySet);
  else if (opcode == XOR)
    boostG::sym_difference(polyset1, polyset2, resultPolySet);

  diffTime = myTimer.checkTimer();
  (this->boolTime) += diffTime;

  if (intersects(resultPolySet)) {
    fprintf(stdout, "how is resultPolySet self intersecting?\n");
  }
  boostG::correct(resultPolySet);

  int innerPnum;

  *resultPnum = boostG::num_geometries(resultPolySet);
  innerPnum = boostG::num_interior_rings(resultPolySet);

  *resultPnum += innerPnum;

  int* xybuffer = (int*) malloc (sizeof(int)*(this->MAXPTS));
  if (xybuffer == NULL) {
    fprintf(stderr, "xybuffer memory allocation failed\n");
    return;
  }

  (*resultVList) = (int*) malloc (sizeof(int) * (*resultPnum));
  if ((*resultVList) == NULL) {
    fprintf(stderr, "(*resultVList) memory allocation failed\n");
    return;
  }

  (*resultPList) = (int**) malloc (sizeof(int*) * (*resultPnum));
  if ((*resultPList) == NULL) {
    fprintf(stderr, "(*resultPList) memory allocation failed\n");
    return;
  }

  int vCount = 0;
  int pCount = 0;

  BOOST_FOREACH(BGPolygon& p, resultPolySet) {
    //fprintf(stdout, "AMIHERE\n");

    vCount = 0;

    boostG::correct(p);
    (*resultVList)[pCount] = -boostG::num_points(p.outer());

    BOOST_FOREACH(BGPoint& pt, p.outer()) {
      xybuffer[vCount*2] = pt.x();
      xybuffer[vCount*2+1] = pt.y() ;
      vCount++;
    }

    (*resultPList)[pCount] = (int*) malloc (sizeof(int) *
boostG::num_points(p.outer()) * 2);
    if ((*resultPList)[pCount] == NULL) {
      fprintf(stderr, "(*resultPList)[%d] memory allocation failed\n",
pCount);
      return;
    }

    memcpy((*resultPList)[pCount], xybuffer, sizeof(int) * vCount * 2);
    pCount++;

    BOOST_FOREACH(BGRing& r, p.inners()) {
      boostG::correct(r);
      (*resultVList)[pCount] = boostG::num_points(r);
      vCount = 0;

      BOOST_FOREACH(BGPoint& pt, r) {
        xybuffer[vCount*2] = pt.x();
        xybuffer[vCount*2+1] = pt.y() ;
        vCount++;
      }

      (*resultPList)[pCount] = (int*) malloc (sizeof(int) *
boostG::num_points(r) * 2);
      if ((*resultPList)[pCount] == NULL) {
        fprintf(stderr, "(*resultPList)[%d] memory allocation failed\n",
    pCount);
        return;
      }

      memcpy((*resultPList)[pCount], xybuffer, sizeof(int) * vCount * 2);
      pCount++;
    }
  }

  boostG::clear(polyset1);
  boostG::clear(polyset2);
  boostG::clear(resultPolySet);

  if (xybuffer != NULL) {
    free(xybuffer);
    xybuffer = NULL;
  }

  return;
}

On Mon, Nov 26, 2012 at 11:37 AM, josh kim <josh.kim0323_at_[hidden]> wrote:

> what about the problems that I was having? overlay polygon problems and
> the one that I described with pictures in the first thread? To me,
> correctness of the library is more important than the performance.
>
>
> On Sat, Nov 24, 2012 at 3:57 AM, Bruno Lalande [via Boost Geometry] <[hidden
> email] <http://user/SendEmail.jtp?type=node&node=4025156&i=0>> wrote:
>
>> Hi Josh,
>>
>> I was talking about the vector::swap function, which swaps 2 vectors
>> by swapping their respective internal pointer. It's a costless
>> operation.
>>
>> My point was : tmpPolySet is only a temporary multipolygon in which
>> you store the result of union(polyset1, polygon). Then you assign it
>> back to polyset1 so that the result iteratively accumulates into
>> polyset1. Since tmpPolyset is a temporary intermediate result, you
>> clear it at the end of the loop. So rather than assigning it to
>> polyset1, which involves a per-point copy, you might as well swap
>> them. polyset1 would then have the contents of tmpPolySet (which is
>> what you want) and tmpPolySet would have the contents of polyset1
>> (which is something you don't need but you get rid of it just after
>> anyway). This way you achieve the same result without a per_point
>> copy.
>>
>> So, replace this:
>>
>> boostG::assign(polyset1, tmpPolySet);
>>
>> by:
>>
>> polyset1.swap(tmpPolySet);
>>
>> and see if performances improve.
>>
>> To advise further I'd also need to have the declarations of all the
>> variables you're using and what they're supposed to contain, it's hard
>> to read the code without having the preconditions.
>>
>> Regards
>> Bruno
>>
>>
>> On Mon, Nov 19, 2012 at 12:26 AM, josh kim <[hidden email]<http://user/SendEmail.jtp?type=node&node=4025153&i=0>>
>> wrote:
>>
>> > I apologize for not being specific enough. I am using polygon type
>> provided
>> > by Boost Geometry.
>> >
>> >
>> >
>> > typedef boostG::model::d2::point_xy<int> BGPoint;
>> >
>> > typedef boostG::model::polygon< BGPoint, false, true > BGPolygon;
>> >
>> > typedef boostG::model::multi_polygon< BGPolygon > multi_polygon;
>> >
>> > typedef boostG::model::ring<BGPoint, false, true> BGRing;
>> >
>> > typedef vector<BGPolygon> BGPolygonSet;
>> >
>> >
>> >
>> > these are the types I use that are provided by boost geometry.
>> >
>> > I first used BGPolygonSet to pass two sets of polygons to booleanizing
>> > operation, however, I figured that I should use multi_polygon type for
>> doing
>> > that.
>> >
>> > and no. everything is in the for loop.
>> > Here's my code :
>> >
>> > for (i = 0; i < pnum1; i++) {
>> >
>> > for (j = 0; j < vnumList1[i] - 1; j++) {
>> >
>> > poly_x = polygonList1[i][j*2];
>> > poly_y = polygonList1[i][j*2+1];
>> > polyPoints.push_back(make<BGPoint>(poly_x, poly_y));
>> > }
>> > boostG::assign_points(polygon, polyPoints);
>> > boostG::correct(polygon);
>> >
>> > boostG::union_(polyset1, polygon, tmpPolySet);
>> > boostG::correct(tmpPolySet);
>> >
>> > boostG::assign(polyset1, tmpPolySet);
>> > boostG::correct(polyset1);
>> >
>> > boostG::clear(tmpPolySet);
>> > polyPoints.clear();
>> > }
>> >
>> >
>> > I'm using correct polygon just to make sure I can avoid having overlay
>> > problem issue.
>> > and using assign(polyset1, tmpPolySet) to recursively add one polygon
>> to the
>> > list (multipolygon) at a time.
>> >
>> > and what does swap function actually do? it doesn't seem to add a
>> polygon to
>> > the multipolygon data type.
>> >
>> > and what about the overlay polygon issues I'm having? and the
>> unionizing
>> > problem that I explained with pictures? The last picture is what I
>> expect.
>> >
>> > And thank you very much for answering my question!
>> >
>> >
>> >
>> >
>> > --
>> > View this message in context:
>> http://boost-geometry.203548.n3.nabble.com/Boost-Geometry-boolean-operation-usage-on-many-polygons-tp4025139p4025145.html
>>
>> > Sent from the Boost Geometry mailing list archive at Nabble.com.
>> > _______________________________________________
>> > Geometry mailing list
>> > [hidden email] <http://user/SendEmail.jtp?type=node&node=4025153&i=1>
>> > http://lists.boost.org/mailman/listinfo.cgi/geometry
>> _______________________________________________
>> Geometry mailing list
>> [hidden email] <http://user/SendEmail.jtp?type=node&node=4025153&i=2>
>> http://lists.boost.org/mailman/listinfo.cgi/geometry
>>
>>
>> ------------------------------
>> If you reply to this email, your message will be added to the
>> discussion below:
>>
>> http://boost-geometry.203548.n3.nabble.com/Boost-Geometry-boolean-operation-usage-on-many-polygons-tp4025139p4025153.html
>> To unsubscribe from Boost.Geometry boolean operation usage on many
>> polygons., click here.
>> NAML<http://boost-geometry.203548.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
>>
>
>
> ------------------------------
> View this message in context: Re: Boost.Geometry boolean operation usage
> on many polygons.<http://boost-geometry.203548.n3.nabble.com/Boost-Geometry-boolean-operation-usage-on-many-polygons-tp4025139p4025156.html>
>
> Sent from the Boost Geometry mailing list archive<http://boost-geometry.203548.n3.nabble.com/>at Nabble.com.
>
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry
>
>



Geometry list run by mateusz at loskot.net