Results 1 to 6 of 6

Thread: TPointArray.getConvexHull() causing memory leak

  1. #1
    Join Date
    Jan 2012
    Location
    East Coast
    Posts
    733
    Mentioned
    81 Post(s)
    Quoted
    364 Post(s)

    Default TPointArray.getConvexHull() causing memory leak

    Title. When I use this function it jumps Simba's memory usage by about 1.5MB and does not go down, causing Simba to quickly eat up all of the RAM on my machine and then crash.

    @slacky; I saw you wrote the function, could you offer some insight?

  2. #2
    Join Date
    Feb 2012
    Location
    Norway
    Posts
    995
    Mentioned
    145 Post(s)
    Quoted
    596 Post(s)

    Default

    Quote Originally Posted by Ross View Post
    Title. When I use this function it jumps Simba's memory usage by about 1.5MB and does not go down, causing Simba to quickly eat up all of the RAM on my machine and then crash.

    @slacky; I saw you wrote the function, could you offer some insight?
    I'll have a look, give me a few.
    Edit: This is quite something. Very interesting, I have an updated version which is simplefied a lot (full rewrite), times faster, but even that one leaks. For no obvious reason.
    Last edited by slacky; 09-13-2015 at 03:43 PM.
    !No priv. messages please

  3. #3
    Join Date
    Jan 2012
    Location
    East Coast
    Posts
    733
    Mentioned
    81 Post(s)
    Quoted
    364 Post(s)

    Default

    Quote Originally Posted by slacky View Post
    I'll have a look, give me a few.
    Thank you, I just had it confirmed by a few others as well.

  4. #4
    Join Date
    Feb 2012
    Location
    Norway
    Posts
    995
    Mentioned
    145 Post(s)
    Quoted
    596 Post(s)

    Default

    Quote Originally Posted by Ross View Post
    Thank you, I just had it confirmed by a few others as well.
    Working version (full rewrite):
    Simba Code:
    function TPointArray.ConvexHull(): TPointArray;
    var
      pts: TPointArray;
      h,i,k,u: Int32;
      function CrossProd(r, p, q: TPoint): Int32;
      begin //cross-product of rp and rq vectors.
        Result := (p.x-r.x) * (q.y-r.y) - (p.y-r.y) * (q.x-r.x);
      end;
    begin
      if High(self) <= 2 then Exit(self);
      pts := Copy(self);
      SortTPAByX(pts,True);

      H := High(pts);
      SetLength(result, 2 * (h+1));

      for i:=0 to h do
      begin
        while (k >= 2) and (CrossProd(result[k-2], result[k-1], pts[i]) <= 0) do
          Dec(k);
        result[k] := pts[i];
        Inc(k)
      end;

      u := k+1;
      for i:=h-1 downto 0 do
      begin
        while (k >= u) and (CrossProd(result[k-2], result[k-1], pts[i]) <= 0) do
          Dec(k);
        result[k] := pts[i];
        Inc(k);
      end;
      SetLength(result, k-1);
    end;

    So, the one in SRL should be replaced with this one. The issue you found is somewhat hard to point out, seems to be caused by a small bug in Lape. I don't wanna mess with the version of ConvexHull found in SRL anyways, it has been uglyfied from the original (the one I wrote), making it harder to track down issues. Hence why I just give you a new version. @Olly
    Last edited by slacky; 09-13-2015 at 04:01 PM.
    !No priv. messages please

  5. #5
    Join Date
    Jan 2012
    Location
    East Coast
    Posts
    733
    Mentioned
    81 Post(s)
    Quoted
    364 Post(s)

    Default

    Quote Originally Posted by slacky View Post
    Working version:
    Simba Code:
    function TPointArray.ConvexHull(): TPointArray;
    var
      pts: TPointArray;
      h,i,k,u: Int32;
      function CrossProd(r, p, q: TPoint): Int32;
      begin //cross-product of rp and rq vectors.
        Result := (p.x-r.x) * (q.y-r.y) - (p.y-r.y) * (q.x-r.x);
      end;
    begin
      if High(self) <= 2 then Exit(self);
      pts := Copy(self);
      SortTPAByX(pts,True);

      H := High(pts);
      SetLength(result, 2 * (h+1));

      for i:=0 to h do
      begin
        while (k >= 2) and (CrossProd(result[k-2], result[k-1], pts[i]) <= 0) do
          Dec(k);
        result[k] := pts[i];
        Inc(k)
      end;

      u := k+1;
      for i:=h-1 downto 0 do
      begin
        while (k >= u) and (CrossProd(result[k-2], result[k-1], pts[i]) <= 0) do
          Dec(k);
        result[k] := pts[i];
        Inc(k);
      end;
      SetLength(result, k);
    end;

    So, the one in SRL should be replaced with this one. The issue you found is somewhat hard to point out, seems to be caused by a small bug in Lape. I don't wanna mess with the version of ConvexHull found in SRL anyways, it has been uglyfied from the original (the one I wrote), making it harder to track down issues. Hence why I just give you a new version.
    @Olly
    Thank you! Repped

    edit:
    Simba Code:
    pts := Copy(self);

    doesn't know which overloaded method to call @slacky;

  6. #6
    Join Date
    Feb 2012
    Location
    Norway
    Posts
    995
    Mentioned
    145 Post(s)
    Quoted
    596 Post(s)

    Default

    Quote Originally Posted by Ross View Post
    Thank you! Repped

    edit:
    Simba Code:
    pts := Copy(self);

    doesn't know which overloaded method to call @slacky;
    Err.. SRL-6 added a local copy-method to their type-helpers for no reason what so ever -.- I bet it was just to irritate me, them trolls.
    Simba Code:
    function TPointArray.ConvexHull(): TPointArray;
    var
      pts: TPointArray;
      h,i,k,u: Int32;
      function CrossProd(r, p, q: TPoint): Int32;
      begin //cross-product of rp and rq vectors.
        Result := (p.x-r.x) * (q.y-r.y) - (p.y-r.y) * (q.x-r.x);
      end;
    begin
      if High(self) <= 2 then Exit(self);
      pts := System.Copy(self);
      SortTPAByX(pts,True);

      H := High(pts);
      SetLength(result, 2 * (h+1));

      for i:=0 to h do
      begin
        while (k >= 2) and (CrossProd(result[k-2], result[k-1], pts[i]) <= 0) do
          Dec(k);
        result[k] := pts[i];
        Inc(k)
      end;

      u := k+1;
      for i:=h-1 downto 0 do
      begin
        while (k >= u) and (CrossProd(result[k-2], result[k-1], pts[i]) <= 0) do
          Dec(k);
        result[k] := pts[i];
        Inc(k);
      end;
      SetLength(result, k-1);
    end;
    Last edited by slacky; 09-13-2015 at 04:17 PM.
    !No priv. messages please

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •