### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: Finding the center of an irregular shape  (Read 6617 times)

#### jamie

• Hero Member
• Posts: 4752
##### Re: Finding the center of an irregular shape
« Reply #15 on: May 31, 2021, 09:46:12 pm »
I converted that JavaScript(PolygonLabel)  over to a fpc unt with a windows test for..

I got it to compile and run without error and tried it with a triangle. Although it reports a X,Y in the triangle it does not report it in the middle, its off a little.

I created the code the best I could from Java over to pascal and used old style dynamic objects with a  constructor to make it look as close to the Java script as possible..  It works but like I said I need to examine the values it's returning a little closer.

I will most likely post the unit here at some point.
The only true wisdom is knowing you know nothing

#### VTwin

• Hero Member
• Posts: 1037
• Former Turbo Pascal 3 user
##### Re: Finding the center of an irregular shape
« Reply #16 on: May 31, 2021, 10:23:28 pm »
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.

« Last Edit: May 31, 2021, 11:00:54 pm by VTwin »
“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.0
macOS 10.13.6: Lazarus 2.0.12 (64 bit Cocoa)
Ubuntu 18.04.3: Lazarus 2.0.12 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.0.12 (64 bit on VBox)

#### jamie

• Hero Member
• Posts: 4752
##### Re: Finding the center of an irregular shape
« Reply #17 on: June 01, 2021, 01:41:53 am »
here is the translation as best as I could get it to work with some changes ..

I found that the sqrt function in JavaScript allows minus numbers and gives you minus results.

it seems fpc has prevented this from happening so I had to pull off a trick of using ABS around the value and then put the sign back on the results which corrected for an issue I was having because it wasn't finding center very well.. with the simple test I used it seems to find center much better now..

attached is a demo with unit file, do as you please with it.
The only true wisdom is knowing you know nothing

#### engkin

• Hero Member
• Posts: 2872
##### Re: Finding the center of an irregular shape
« Reply #18 on: June 01, 2021, 07:32:55 am »
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.

#### jamie

• Hero Member
• Posts: 4752
##### Re: Finding the center of an irregular shape
« Reply #19 on: June 01, 2021, 12:56:43 pm »
Thanks.

I see you changed the code for the sqrt - problem and also changed some types to floats.

I was going to put a Poly number type at the top of the source so that it can be easily recompiled because I don't like generics.

Also you added the extra field for the return "Centroid". I was thinking that maybe a flag could be put in there to indicate if the centroid falls out side of the shape in which case the "Plot" could be used instead and there by having a final "Plot" in the field.

It seems for average shapes the centroid is closer in some aspects.
The only true wisdom is knowing you know nothing

#### jamie

• Hero Member
• Posts: 4752
##### Re: Finding the center of an irregular shape
« Reply #20 on: June 01, 2021, 02:31:53 pm »
Need 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 haven't got the exact point values that generates this negative number yet but I think what I did should avoid the issue...

I'll get back on that one later .

Seems all I need to do is wrap MinDistSq with ABS because the GetSegDistSq is returning a - number depending on what is going on...

Code: Pascal  [Select][+][-]
1.   if MinDistSq = 0 then
2.     Result := 0
3.   else
4.   begin
5.     Result := Round(Sqrt(Abs(MinDistSq)));
6.     if not Inside then
7.       Result := -Result;
8.   end;
9.
I have that at the end of PointToPolygonDist now.
« Last Edit: June 01, 2021, 03:15:40 pm by jamie »
The only true wisdom is knowing you know nothing

#### VTwin

• Hero Member
• Posts: 1037
• Former Turbo Pascal 3 user
##### Re: Finding the center of an irregular shape
« Reply #21 on: June 01, 2021, 04:10:50 pm »
Nice demo. I now understand that the "pole of inaccessibility" is the desired point.
« Last Edit: June 01, 2021, 04:12:50 pm by VTwin »
“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.0
macOS 10.13.6: Lazarus 2.0.12 (64 bit Cocoa)
Ubuntu 18.04.3: Lazarus 2.0.12 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.0.12 (64 bit on VBox)

#### engkin

• Hero Member
• Posts: 2872
##### Re: Finding the center of an irregular shape
« Reply #22 on: June 01, 2021, 04:59:30 pm »
Nice demo. I now understand that the "pole of inaccessibility" is the desired point.

The article posted by Edson in reply #8 is really nice.

Need 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][+][-]
1.     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][+][-]
1.     Result := round(dx * dx + dy * dy);

#### DomingoGP

• New Member
• Posts: 15
##### Re: Finding the center of an irregular shape
« Reply #23 on: June 05, 2021, 05:23:06 pm »

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

• Hero Member
• Posts: 2872
##### Re: Finding the center of an irregular shape
« Reply #24 on: June 05, 2021, 08:29:06 pm »
engkin, 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

• New Member
• Posts: 15
##### Re: Finding the center of an irregular shape
« Reply #25 on: June 13, 2021, 04:35:28 pm »

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;