Centroid Question

[TerryRitchie]

Ok you math wizards, I need your input/advice. I've been reading up on centroids and barycenters because I want to find the center point of a given set of x,y points. The suggested math for this as found on the Internet is truly impressive (i.e. wow).

However, why couldn't you just use the center point of the min/max x,y point seen in the set? The code illustrates what I have in mind. Any thoughts on this approach? Good, bad? If bad, why? Thanks for taking the time to read this.

Code: (Select All)

CONST RED~& = _RGB32(255, 0, 0)
CONST GREEN~& = _RGB32(0, 255, 0)
CONST GRAY~& = _RGB32(64, 64, 64)

TYPE iPoint '          x,y point construct
    x AS INTEGER
    y AS INTEGER
END TYPE

DIM rp(19) AS iPoint ' random point
DIM Min AS iPoint '    min x,y seen
DIM Max AS iPoint '    max x,y seen
DIM Center AS iPoint ' center point of random points
DIM p AS INTEGER '     counter

RANDOMIZE TIMER
Min.x = 319 '          start min/max at center of screen
Min.y = 239
Max = Min

SCREEN _NEWIMAGE(640, 480, 32)

p = 0
DO '                                                                                       create random points
    rp(p).x = RND * 640
    rp(p).y = RND * 480
    IF rp(p).x > Max.x THEN Max.x = rp(p).x ELSE IF rp(p).x < Min.x THEN Min.x = rp(p).x ' get max/min x
    IF rp(p).y > Max.y THEN Max.y = rp(p).y ELSE IF rp(p).y < Min.y THEN Min.y = rp(p).y ' get max/min y
    p = p + 1
LOOP UNTIL p > UBOUND(rp)

Center.x = Min.x + ((Max.x - Min.x) / 2) ' get center x
Center.y = Min.y + ((Max.y - Min.y) / 2) ' get center y

p = 0
DO '                                                    draw points in red, lines to center in gray
    LINE (rp(p).x, rp(p).y)-(Center.x, Center.y), GRAY
    CIRCLE (rp(p).x, rp(p).y), 2, RED
    PAINT (rp(p).x, rp(p).y), RED, RED
    p = p + 1
LOOP UNTIL p > UBOUND(rp)


CIRCLE (Center.x, Center.y), 2, GREEN '                 draw green center point
PAINT (Center.x, Center.y), GREEN, GREEN

PRINT Min.x; Min.y, Max.x; Max.y, Center.x; Center.y '  display values

[Pete]

My question would be is there a mathematical model that doesn't require a bruit force approach? If so, we should beat the hell out of the bastard who created it!

Pete

- Trust me. I'm a senior operative in the C.I.A. (Centroid Intelligence Agency).

[bplus]

Mid x, y for a rectangle would be exactly the same for the 2 right triagles that make it up, which would put the centroid right on the edge of the hypotenuse. So I think that proves the idea incorrect.

https://www.google.com/search?client=ope...8&oe=UTF-8

[TerryRitchie]

Mid x, y for a rectangle would be exactly the same for the 2 right triagles that make it up, which would put the centroid right on the edge of the hypotenuse. So I think that proves the idea incorrect.

https://www.google.com/search?client=ope...8&oe=UTF-8

Yeah, I was thinking about that too. I'm basically creating a rectangle around the points and then taking the center point of that rectangle as the center point of the x,y point collective. It "sounds" corrects to me but I'm not sure, that's why I'm asking for input.

Some of the reading I've encountered states you need to use Centroid calculation, others state barycenter calculation, yet others seem to somehow get mass involved. All confusing.

[Pete]

Triangles are fun: ((x1+x2+x3)/3, (y1+y2+y3)/3) 

https://byjus.com/maths/centroid/

When we get into a parabolic spandrel it gets a little funky, but if I had quarter for every time I needed to use one of those, I'd have to climb over the stall to use the pay toilet.

Pete

[justsomeguy]

The mass computation in my physics engine is based upon the following code by Randy Gaul. 

https://github.com/RandyGaul/ImpulseEngi...er/Shape.h

Code: (Select All)

void ComputeMass( real density )
  {
    // Calculate centroid and moment of interia
    Vec2 c( 0.0f, 0.0f ); // centroid
    real area = 0.0f;
    real I = 0.0f;
    const real k_inv3 = 1.0f / 3.0f;

    for(uint32 i1 = 0; i1 < m_vertexCount; ++i1)
    {
      // Triangle vertices, third vertex implied as (0, 0)
      Vec2 p1( m_vertices[i1] );
      uint32 i2 = i1 + 1 < m_vertexCount ? i1 + 1 : 0;
      Vec2 p2( m_vertices[i2] );

      real D = Cross( p1, p2 );
      real triangleArea = 0.5f * D;

      area += triangleArea;

      // Use area to weight the centroid average, not just vertex position
      c += triangleArea * k_inv3 * (p1 + p2);

      real intx2 = p1.x * p1.x + p2.x * p1.x + p2.x * p2.x;
      real inty2 = p1.y * p1.y + p2.y * p1.y + p2.y * p2.y;
      I += (0.25f * k_inv3 * D) * (intx2 + inty2);
    }

    c *= 1.0f / area;

    // Translate vertices to centroid (make the centroid (0, 0)
    // for the polygon in model space)
    // Not really necessary, but I like doing this anyway
    for(uint32 i = 0; i < m_vertexCount; ++i)
      m_vertices[i] -= c;

    body->m = density * area;
    body->im = (body->m) ? 1.0f / body->m : 0.0f;
    body->I = I * density;
    body->iI = body->I ? 1.0f / body->I : 0.0f;
  }

[bplus]

Ok you math wizards, I need your input/advice. I've been reading up on centroids and barycenters because I want to find the center point of a given set of x,y points. The suggested math for this as found on the Internet is truly impressive (i.e. wow).

However, why couldn't you just use the center point of the min/max x,y point seen in the set? The code illustrates what I have in mind. Any thoughts on this approach? Good, bad? If bad, why? Thanks for taking the time to read this.

Code: (Select All)

CONST RED~& = _RGB32(255, 0, 0)
CONST GREEN~& = _RGB32(0, 255, 0)
CONST GRAY~& = _RGB32(64, 64, 64)

TYPE iPoint '          x,y point construct
    x AS INTEGER
    y AS INTEGER
END TYPE

DIM rp(19) AS iPoint ' random point
DIM Min AS iPoint '    min x,y seen
DIM Max AS iPoint '    max x,y seen
DIM Center AS iPoint ' center point of random points
DIM p AS INTEGER '     counter

RANDOMIZE TIMER
Min.x = 319 '          start min/max at center of screen
Min.y = 239
Max = Min

SCREEN _NEWIMAGE(640, 480, 32)

p = 0
DO '                                                                                       create random points
    rp(p).x = RND * 640
    rp(p).y = RND * 480
    IF rp(p).x > Max.x THEN Max.x = rp(p).x ELSE IF rp(p).x < Min.x THEN Min.x = rp(p).x ' get max/min x
    IF rp(p).y > Max.y THEN Max.y = rp(p).y ELSE IF rp(p).y < Min.y THEN Min.y = rp(p).y ' get max/min y
    p = p + 1
LOOP UNTIL p > UBOUND(rp)

Center.x = Min.x + ((Max.x - Min.x) / 2) ' get center x
Center.y = Min.y + ((Max.y - Min.y) / 2) ' get center y

p = 0
DO '                                                    draw points in red, lines to center in gray
    LINE (rp(p).x, rp(p).y)-(Center.x, Center.y), GRAY
    CIRCLE (rp(p).x, rp(p).y), 2, RED
    PAINT (rp(p).x, rp(p).y), RED, RED
    p = p + 1
LOOP UNTIL p > UBOUND(rp)


CIRCLE (Center.x, Center.y), 2, GREEN '                 draw green center point
PAINT (Center.x, Center.y), GREEN, GREEN

PRINT Min.x; Min.y, Max.x; Max.y, Center.x; Center.y '  display values

OK I would compare the proper calc of centroid = ave x and ave y as Pete says and mid x and mid y.

BTW what are centroids used for, I asked Google and got Bull Science.

[aadityap0901]

For a given set of points like: [0, 0], [3, 3], [6, 6] ........
The mid point will be: Mid_X = Average(All X Co-ordinates), Mid_Y = Average(All Y Co-ordinates)

if you want a mass center with a non-uniform distribution of mass as particles:
Mid_Mass_X = Sum(X(I) * M(I)) / Sum (M(I)), Mid_Mass_Y = Sum(Y(I) * M(I)) / Sum (M(I))

For example:
[0, 0], [5, 5], [7, 4]
Mid_Point = [ (0 + 5 + 7) / 3, (0 + 5 + 4) / 3 ] = [4, 3]
For non uniform mass distribution: (written as [X, Y, Mass] at point [X, Y])
[0, 0, 1], [5, 2, 3], [4, 5, 3], [7, 9, 2]
Mid_Point = [ (0 * 1 + 5 * 3 + 4 * 3 + 7 * 2) / (1 + 3 + 3 + 2), (0 * 1 + 2 * 3 + 5 * 3 + 9 * 2) / (1 + 3 + 3 + 2) ] = [4.55, 4.33]

[Kernelpanic]

I would say that the incircle center of any triangle is sought. It is calculated as follows:

PS: The radius is the same distance from all sides of the triangle and thus indicates the incircle center.

Code: (Select All)

'Berechnung des Inkreismittelpunktes eines Dreiecks - 14. Juli 2024

'https://www.biancahoegel.de/geometrie/ebene/inkreis.html

'Mathematik 2 Geometrie S.98ff, 106, 108



Option _Explicit



'ad, bd, cd Seiten eines Dreiecks, AF = Flaecheninhalt, s = Umfang

Dim As Double AF, ad, bd, cd, s, radius, dummy



Locate 2, 3

Print "Berechnung des Inkreismittelpunktes eines Dreiecks"

Locate 3, 3

Print "=================================================="



Locate 5, 3

Input "Laenge der Seite a in cm: ", ad

Locate 6, 3

Input "Laenge der Seite b in cm: ", bd

Locate 7, 3

Input "Laenge der Seite c in cm: ", cd



s = (ad + bd + cd) / 2

dummy = s * ((s - ad) * (s - bd) * (s - cd))

AF = Sqr(dummy)



'Der Radius ist von allen Seiten des Dreiecks gleich weit entfernt,

'und zeigt somit den Inkreismittelpunkt an.

radius = (2 * AF) / (ad + bd + cd)



Locate 9, 3

Print Using "Der Inkreismittelpunkt des gegebenen Dreiecks liegt bei ###.## cm."; radius



End

[TerryRitchie]

For a given set of points like: [0, 0], [3, 3], [6, 6] ........
The mid point will be: Mid_X = Average(All X Co-ordinates), Mid_Y = Average(All Y Co-ordinates)

if you want a mass center with a non-uniform distribution of mass as particles:
Mid_Mass_X = Sum(X(I) * M(I)) / Sum (M(I)), Mid_Mass_Y = Sum(Y(I) * M(I)) / Sum (M(I))

For example:
[0, 0], [5, 5], [7, 4]
Mid_Point = [ (0 + 5 + 7) / 3, (0 + 5 + 4) / 3 ] = [4, 3]
For non uniform mass distribution: (written as [X, Y, Mass] at point [X, Y])
[0, 0, 1], [5, 2, 3], [4, 5, 3], [7, 9, 2]
Mid_Point = [ (0 * 1 + 5 * 3 + 4 * 3 + 7 * 2) / (1 + 3 + 3 + 2), (0 * 1 + 2 * 3 + 5 * 3 + 9 * 2) / (1 + 3 + 3 + 2) ] = [4.55, 4.33]

Ah, ok, so the average is what I am looking for here. Thank you for the information.