Finding the center of an irregular shape lazarus / 21-General ---------------------------------------------------------------------- valter.home · 2021-05-28 13:18 Hello everybody, I'm trying to find the center of a polygon but it should be inside the shape. Applying the Centroid formula (e.g. for a triangle G (x, y) = ((x1 + x2 + x3) / 3, (y1 + y2 + y3) / 3)) I get the point I'm looking for but if the shape is very irregular the point is obviously outside it. Do you have any ideas? ---------------------------------------------------------------------- winni · 2021-05-28 15:32 Hi! Create a Bounding Box and the take the center of that. Search the minimum and maximum of x and y for all points. Then build a rectangle: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i var R: Trect;     ...R := Rect (MinX, MinY, MaxX, MaxY)   Now you can create the center of the rectangle Winni ---------------------------------------------------------------------- howardpc · 2021-05-28 16:15 Quote from: valter.home on May 28, 2021, 03:18:27 pmI'm trying to find the center of a polygon but it should be inside the shape. winni's suggestion is a good one. Note, however, that it does not guarantee that the "centre" is inside the polygon. There are shapes whose "centre" is outside the shape. You can't alter that sort of topology. It is simply an exception to your preference that "the center ... should be inside the shape". ---------------------------------------------------------------------- wp · 2021-05-28 16:20 What is the "center" of a polygon? In my opinion this is the "center of gravity". Suppose you plot the polygon on a piece of cardpaper and cut out the polygon; then this is the point at which you have to attach a thread so that the polygon remains horizontal when the other end of the thread is held up. A general procedure to calculate it is given in https://stackoverflow.com/questions/5271583/center-of-gravity-of-a- polygon. However, it has to be accepted that this kind of center point can be outside the polygon (well - the thread model requires some fancy construction in this case). ---------------------------------------------------------------------- lucamar · 2021-05-28 16:26 Quote from: wp on May 28, 2021, 06:20:47 pmWhat is the "center" of a polygon? I think he means the geometric center ... which leaves us as we were, since it can also be outside the figure in question ---------------------------------------------------------------------- valter.home · 2021-05-28 18:39 What you say is mathematically true. Perhaps calling it the center of the shape is incorrect. In the Unity engine, once a mesh is created, MyMesh.Center always returns a midpoint within the mesh, whatever its shape. Unfortunately I have no idea which algorithm it uses but the point returned is "visually" optimal. ---------------------------------------------------------------------- Edson · 2021-05-28 18:48 Quote from: valter.home on May 28, 2021, 08:39:51 pmWhat you say is mathematically true. Perhaps calling it the center of the shape is incorrect. In the Unity engine, once a mesh is created, MyMesh.Center always returns a midpoint within the mesh, whatever its shape. Unfortunately I have no idea which algorithm it uses but the point returned is "visually" optimal. You could use the closest point to the centroid, that is inside the polygon. It should be at the border when centroid is outside the polygon. ---------------------------------------------------------------------- valter.home · 2021-05-28 20:33 QuoteYou could use the closest point to the centroid... Yes, after several researches I believe this is the best solution. ---------------------------------------------------------------------- Edson · 2021-05-28 20:59 If you don't like a point in the border, you could project the line to the polygon to obtain two points A and B, and get the point in the middle. Although this don't give always the best location. Look at the picture. Have you checked this: https://blog.mapbox.com/a-new-algorithm-for- finding-a-visual-center-of-a-polygon-7c77e6492fbc ? ---------------------------------------------------------------------- valter.home · 2021-05-29 09:15 Yes, I had already found this article and was working on it. Thanks so much. ---------------------------------------------------------------------- engkin · 2021-05-31 13:05 Quote from: jamie on May 31, 2021, 01:06:31 pmQuote from: Edson on May 28, 2021, 10:59:22 pmIf you don't like a point in the border, you could project the line to the polygon to obtain two points A and B, and get the point in the middle. Although this don't give always the best location. Look at the picture. Have you checked this: https://blog.mapbox.com/a-new-algorithm-for- finding-a-visual-center-of-a-polygon-7c77e6492fbc ? I must be living in a censored country now, I can only see parts of that page and the C++ source leads me to a 404 site. Polylabel is on GitHub. Here is the correct C++ Link and Javascript Link. Microsoft will not censor you, not yet! ---------------------------------------------------------------------- engkin · 2021-05-31 13:21 Lol. I just fixed the C++ link, again. ---------------------------------------------------------------------- VTwin · 2021-05-31 16:16 Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i { PolygonCentroid  Returns the center of gravity (barycenter) of a simple (non  self-intersecting) polygon defined by vertices (x,y). The area is also  returned, although PolygonArea is more efficient if the center is not needed.  The area will be positive for anticlockwise ordered vertices, and negative  for clockwise. Uses triangle summation. Adopted from Bowyer and Woodwark,  1983, p. 70-72. }procedure PolygonCentroid(x, y: Vector; var xc, yc, area: double);var  third: double;  xct, yct, x0, y0, xprev, yprev: double;  xt, yt: double;  asum, atri, ainv: double;  i, n: integer;begin  xc := 0.0;  yc := 0.0;  area := 0.0;  n := Length(x);  if n < 3 then    exit;  xct := 0.0;  yct := 0.0;  x0 := x[n-1]; // common vertex for triangles  y0 := y[n-1];  xprev := x[0];  yprev := y[0];  asum := 0.0;  for i := 1 to n-2 do begin    xt := x[i];    yt := y[i];    atri := (x0-xt)*(yprev-y0) + (xprev-x0)*(yt-y0);    xct += atri * (xt+xprev);    yct += atri * (yt+yprev);    asum += atri;    xprev := xt;    yprev := yt;  end;  if Abs(asum) > 1e-9 then begin    ainv := 1.0/asum;    third := 1.0/3.0;    xc := (xct * ainv + x0) * third;    yc := (yct * ainv + y0) * third;    area := asum * 0.5;  end;end; ---------------------------------------------------------------------- VTwin · 2021-05-31 20:23 There are many definitions for the "center" of a triangle: https://en.wikipedia.org/wiki/Triangle_center I normally  consider the centroid, center of mass, or barycenter, (as wp) but it depends on what you are looking for. It is necessary to be specific. https://en.wikipedia.org/wiki/Centroid The code I posted gives the centroid of any non-self-intersecting polygon, including triangles. ---------------------------------------------------------------------- engkin · 2021-06-01 05:32 Thanks, Jamie. Hope you don't mind. Corrected a few mistakes and made the points movable. The red dot is the target point, the other one is the centroid. Right-click to add more points. Use the mouse to hold and move any point. ---------------------------------------------------------------------- VTwin · 2021-06-01 14:10 Nice demo. I now understand that the "pole of inaccessibility" is the desired point. ---------------------------------------------------------------------- engkin · 2021-06-01 14:59 Quote from: VTwin on June 01, 2021, 04:10:50 pmNice demo. I now understand that the "pole of inaccessibility" is the desired point. The article posted by Edson in reply #8 is really nice. Quote from: jamie on June 01, 2021, 02:31:53 pmNeed to work on that Sqrt(MinDisSq) again. Without the ABS around MinDisSq there is a - value that pops in there if you add some points and move it off the screen or around at different places. I don't think you need to change it. GetSegDistSq returns positive numbers always: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i     Result := round(dx * dx + dy * dy); Here is a comment from the Javascript file: Quote// get squared distance from a point to a segment I believe the error you're seeing is probably a range error from trying to round and fit a double value bigger than MaxInt into an integer variable in the same line: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i     Result := round(dx * dx + dy * dy); ---------------------------------------------------------------------- DomingoGP · 2021-06-05 15:23 Based on the implementation of jamie and engkin I have reimplemented the routine using floating point variables and a Priorityqueue instead of a list. I have also implemented the routine to work with BGRABitmap using TPointF. I have allowed myself to include the license (ISC) just like the original project. jamie, I have put your data as co-author of the routine (I think they are correct, if not, correct me). engkin, I can give you credit in the file but I need your real data. P.S. I have tested it in a real map project and it works fine. The project now depends on BGRABitmap, but the dependency can be removed by commenting out the definition   {$ define IMPLEMENT_TPOINTF} ---------------------------------------------------------------------- engkin · 2021-06-05 18:29 Quote from: DomingoGP on June 05, 2021, 05:23:06 pmengkin, I can give you credit in the file but I need your real data. Thank you for your efforts. I did not do anything worth to be credited. ---------------------------------------------------------------------- DomingoGP · 2021-06-13 14:35 I have used this function in https://github.com/DomingoGP/geopackageViewer and works fine. but i had to change the test for CellSize because if the polygons are too small i get OutOfMemory error. const   MIN_POLYGON_SIZE=10;   //if CellSize = 0 then      // error out of memory   //begin   //  Result.PlotX := MinX;   //  Result.PlotY := MinY;   //  Result.Distance := 0;   //  Exit;   //end;   if CellSize < MIN_POLYGON_SIZE then  // poligon to small, return center.   begin     Result.PlotX := (MinX+MaxX)/2;     Result.PlotY := (MinY+MaxY)/2;     Result.Distance := 0;     Exit;   end;