All committers have signed the CLA.

Hi @sharingan000 👋🏻 Could you give us a bit more context? Why the previous solution was not enough?

Hi @sharingan000 👋🏻 Could you give us a bit more context? Why the previous solution was not enough?

Okay, the essence of the algorithm appears when the distribution of points is uneven

(if you want to see the code for generating this picture, I can send you a link)

Oh! This makes a lot of sense. 🔥

It seems the new implementation performs significantly more operations. Have you measured the execution time? Since we use this function in annotators, people expect the code to execute quickly.

Oh! This makes a lot of sense. 🔥

It seems the new implementation performs significantly more operations. Have you measured the execution time? Since we use this function in annotators, people expect the code to execute quickly.

In milliseconds

Oh! This makes a lot of sense. 🔥

It seems the new implementation performs significantly more operations. Have you measured the execution time? Since we use this function in annotators, people expect the code to execute quickly.

I managed to change the code a little and speed it up, here is the new and more stable data

if you are satisfied with the execution time of this algorithm, I will post a faster version of the algorithm

Hi @sharingan000 👋🏻

Interjecting briefly to ask for more details.

What's k in your table? And in the header - I assume it's the the number of points in a single detection, right? (It could instead mean the number of detections in an image)

Your example was fantastic in illustrating the problem. If there's no downsides to a faster algo and the performance is comparable to ours then by all means - please post it :)

Hi @sharingan000 👋🏻

Interjecting briefly to ask for more details.

What's k in your table? And in the header - I assume it's the the number of points in a single detection, right? (It could instead mean the number of detections in an image)

Your example was fantastic in illustrating the problem. If there's no downsides to a faster algo and the performance is comparable to ours then by all means - please post it :)

k in my table means how many times my algorithm worked more than yours, and the header of the table is the number of points in one polygon.
(I tested 200 times on each set of points, so the results should be stable. In my opinion, despite the fact that my algorithm can work 10 times longer than yours, it still works in less than half a millisecond for a large number of points) , write your opinion about this, if the speed from the table suits you, I will definitely send the updated algorithm

my algorithm has exactly the same asymptotics as yours - O(n), but with a greater constant :)

Thank you, that makes sense.

The slowdown seems small enough to not be an issue.

Please, send it over and we'll review it, do some tests of our own :)

Thank you, that makes sense.

The slowdown seems small enough to not be an issue.

Please, send it over and we'll review it, do some tests of our own :)

I pushed a new algorithm

Hi @sharingan000,

Found a test case where this doesn't give good results, unfortunately.
(I've removed the round of the final result before testing, though I verified that it does not impact the result)

Example 1

We'd expect the center of mass to be slightly above the y=50 line, but it's slightly higher at 45:

Example 2

Continuing with the trend, while we'd expect to see the center of mass move upwards, it, in fact, moved downwards even more, to 40:

Test code:

import numpy as np
import matplotlib.pyplot as plt


def get_polygon_center(polygon: np.ndarray) -> tuple[float, float]:
    polygon = polygon.astype(np.float32)
    shifted_polygon = np.roll(polygon, 1, axis=0)
    points = (shifted_polygon + polygon) / 2
    vectors = shifted_polygon - polygon
    mass = np.sum(vectors**2, axis=1) ** 0.5
    center = (mass @ points) / np.sum(mass)

    return center[1], center[0]
    
def vertices_concave(size: int, thick: int, thin: int) -> np.ndarray:
    assert size > thick > 0
    assert size > thin > 0

    return np.array([
        # ->
        [0, 0], [0, size], [thin, size],
        # <-
        [thin, thin],
        # up
        [size - thick, thin], [size - thick, size], [size, size],
        # down
        [size, 0]])
        

# verts = vertices_concave(100, 25, 2)
verts = vertices_concave(100, 55, 2)
print(verts)

center = get_polygon_center(verts)
center2 = get_polygon_center_2(verts)
print(center)

plt.fill(verts[:, 1], verts[:, 0])
plt.plot(center[0], center[1], 'ro')
plt.show()

@sharingan000, I was wondering - perhaps there was a more commonly known center of mass algorithm for polygons that we could adapt? It would be really good to integrate it now, especially if we have a benchmark close-at-hand

Hi @sharingan000,

Found a test case where this doesn't give good results, unfortunately. (I've removed the round of the final result before testing, though I verified that it does not impact the result)

Example 1

We'd expect the center of mass to be slightly above the y=50 line, but it's slightly higher at 45:

Example 2

Continuing with the trend, while we'd expect to see the center of mass move upwards, it, in fact, moved downwards even more, to 40:

Test code:

import numpy as np
import matplotlib.pyplot as plt


def get_polygon_center(polygon: np.ndarray) -> tuple[float, float]:
    polygon = polygon.astype(np.float32)
    shifted_polygon = np.roll(polygon, 1, axis=0)
    points = (shifted_polygon + polygon) / 2
    vectors = shifted_polygon - polygon
    mass = np.sum(vectors**2, axis=1) ** 0.5
    center = (mass @ points) / np.sum(mass)

    return center[1], center[0]
    
def vertices_concave(size: int, thick: int, thin: int) -> np.ndarray:
    assert size > thick > 0
    assert size > thin > 0

    return np.array([
        # ->
        [0, 0], [0, size], [thin, size],
        # <-
        [thin, thin],
        # up
        [size - thick, thin], [size - thick, size], [size, size],
        # down
        [size, 0]])
        

# verts = vertices_concave(100, 25, 2)
verts = vertices_concave(100, 55, 2)
print(verts)

center = get_polygon_center(verts)
center2 = get_polygon_center_2(verts)
print(center)

plt.fill(verts[:, 1], verts[:, 0])
plt.plot(center[0], center[1], 'ro')
plt.show()

Okay man, i see the problem, but I have a few questions:

1. Why you code
   plt.fill(verts[:, 1], verts[:, 0]), instead of plt.fill(verts[:, 0], verts[:, 1])

2. my algorithm is probably not applicable to non-convex figures, if this fact is important to you, I can suggest two ways to solve the problem: I will test the current algorithm with non-convex figures, or I can try to write an algorithm for finding the center of mass of an already solid figure, which will be the best option for a non-convex figure ( It’s worth noting that your algorithm is undoubtedly the fastest, but it’s probably also not optimal for working with such figures)

3. your algorithm finds the center of mass of the points, my algorithm finds the center of mass of the frame of these points, that is, a cluster of points in one place is the same as one point, but there is an algorithm that fits better than others - this is finding the center of mass of a solid figure, which rests on its area , I can try to implement it (sorry for the partial repetition of the second point)

4. I would suggest implementing three functions in this module at once and using them depending on the situation (depending on what is more important speed or quality), because there are different situations, for example, if you are looking for the center of a bbox, you need to use your algorithm, but if you are looking for the center of a high-quality mask of the facade of a house, your algorithm may not give a sufficiently accurate result

Text me, if you want to see best algorithm :)

@sharingan000, I was wondering - perhaps there was a more commonly known center of mass algorithm for polygons that we could adapt? It would be really good to integrate it now, especially if we have a benchmark close-at-hand

the best algorithm is implemented using triangulation, I will need some time to implement it, maybe tomorrow, I just have 01:14 on the clock

@sharingan000, I was wondering - perhaps there was a more commonly known center of mass algorithm for polygons that we could adapt? It would be really good to integrate it now, especially if we have a benchmark close-at-hand

By the way, if in your code, in the fill method, you swap the coordinates, then my algorithm in the second example will move along X closer to the “heavy” part, yours, on the contrary, will move away

Good point about the swapped fill args. My bad!
This also makes me doubt whether I got the return values right in get_polygon_center as well.

I like your proposal of the two options. We're all short on time, so let's find the best of both worlds.
I hope this doesn't take the fun out of your contribution :)

Here's an algo I found on SO:
https://stackoverflow.com/a/75699662/3369193

Is this what you had in mind when you mentioned triangulation?
Empirically, it gives the correct results, and is in line with Shoelace formula.

It would need an augmentation for the case when all points are on the same line.
(I don't have a good understanding of the negative area - whether that could produce a weight sum of 0 too).

def get_polygon_center_2(polygon: np.ndarray) -> tuple[float, float]:
    polygon2 = np.roll(polygon, -1, axis=0)
    signed_areas = 0.5 * np.cross(polygon, polygon2)
    if signed_area.sum() == 0:
        signed_area = None  # Equal weights. Could just return here instead. 
    centroids = (polygon + polygon2) / 3.0
    center = np.average(centroids, axis=0, weights=signed_areas)
    return center[0], center[1]

Do you think that is correct? If so, would you have some time to test how it compares in terms of runtime, with your proposal?

I don't know which of the two is better to keep yet - maybe both is the answer.

I like your proposal of the two options. We're all short on time, so let's find the best of both worlds. I hope this doesn't take the fun out of your contribution :)

Here's an algo I found on SO: https://stackoverflow.com/a/75699662/3369193

Is this what you had in mind when you mentioned triangulation? Empirically, it gives the correct results, and is in line with Shoelace formula.

It would need an augmentation for the case when all points are on the same line. (I don't have a good understanding of the negative area - whether that could produce a weight sum of 0 too).

def get_polygon_center_2(polygon: np.ndarray) -> tuple[float, float]:
    polygon2 = np.roll(polygon, -1, axis=0)
    signed_areas = 0.5 * np.cross(polygon, polygon2)
    if signed_area.sum() == 0:
        signed_area = None  # Equal weights. Could just return here instead. 
    centroids = (polygon + polygon2) / 3.0
    center = np.average(centroids, axis=0, weights=signed_areas)
    return center[0], center[1]

Do you think that is correct? If so, would you have some time to test how it compares in terms of runtime, with your proposal?

I don't know which of the two is better to keep yet - maybe both is the answer.

You won’t believe it, but I implemented the same algorithm in parallel with you and it works the same way, I made all the time measurements (a table is attached below, where mean is the old algorithm, frame is my first accelerated algorithm, solid is the last algorithm)

I came to the conclusion that you can implement 3 algorithms at once, but choose which one to use depending on the number of points in the polygon (for example: if there are less than 100 points, then use mean, since it is often sufficient for a small number of points and for a small number of points it is much faster than others, but if the number of points exceeds 100 and less than 10000, then you can use solid, since the running time is slightly different from frame, but it is better, and in other cases use frame) (in fact, it is better to check whether the figure is convex and based on this choose frame or solid, but this is an unnecessary operation, so I prefer the option above)

Oh wow, thank you very much!

I'll have a word with the team and see what's best; hopefully merge in soon

I like your proposal of the two options. We're all short on time, so let's find the best of both worlds. I hope this doesn't take the fun out of your contribution :)
Here's an algo I found on SO: https://stackoverflow.com/a/75699662/3369193
Is this what you had in mind when you mentioned triangulation? Empirically, it gives the correct results, and is in line with Shoelace formula.
It would need an augmentation for the case when all points are on the same line. (I don't have a good understanding of the negative area - whether that could produce a weight sum of 0 too).

def get_polygon_center_2(polygon: np.ndarray) -> tuple[float, float]:
    polygon2 = np.roll(polygon, -1, axis=0)
    signed_areas = 0.5 * np.cross(polygon, polygon2)
    if signed_area.sum() == 0:
        signed_area = None  # Equal weights. Could just return here instead. 
    centroids = (polygon + polygon2) / 3.0
    center = np.average(centroids, axis=0, weights=signed_areas)
    return center[0], center[1]

Do you think that is correct? If so, would you have some time to test how it compares in terms of runtime, with your proposal?
I don't know which of the two is better to keep yet - maybe both is the answer.

You won’t believe it, but I implemented the same algorithm in parallel with you and it works the same way, I made all the time measurements (a table is attached below, where mean is the old algorithm, frame is my first accelerated algorithm, solid is the last algorithm)

I came to the conclusion that you can implement 3 algorithms at once, but choose which one to use depending on the number of points in the polygon (for example: if there are less than 100 points, then use mean, since it is often sufficient for a small number of points and for a small number of points it is much faster than others, but if the number of points exceeds 100 and less than 10000, then you can use solid, since the running time is slightly different from frame, but it is better, and in other cases use frame) (in fact, it is better to check whether the figure is convex and based on this choose frame or solid, but this is an unnecessary operation, so I prefer the option above)

if you like this idea I can merge it in about 12 hours

Oh wow, thank you very much!

I'll have a word with the team and see what's best; hopefully merge in soon

ok, thanks, I'll wait for news :)

Oh wow, thank you very much!

I'll have a word with the team and see what's best; hopefully merge in soon

can I write you a private message about developing some algorithms for your repository (geometry)?

can I write you a private message about developing some algorithms for your repository (geometry)?

Feel free to reach out on LinkedIn.

can I write you a private message about developing some algorithms for your repository (geometry)?

Feel free to reach out on LinkedIn.

I am having problems registering on this platform :( (it is probably impossible or very difficult to implement), are there other ways to contact you?

Hi @sharingan000,

Apologies for the delay. I've thought about the next steps and this is what I feel is most optimal for us:

1. Instead of having 3 algorithms cleverly hidden behind a getter class, let's use one. This will be simpler for contributors to understand, and more importantly - for users to discover. It also gives higher consistency: tracking the same object might produce different areas, so we'd like to avoid situations where the centroid is being computed by different algos in subsequent frames.

2. For this, I pick solid. Even if slightly more expensive than yours, given multiple detections, it's expected to produce stabler values centered around the core of the shape, even if it's concave. Do you have the time to replace the contents of get_polygon_center with the solid algo?

3. I'd like to preserve your work as well. Could you leave a line or two of # inside the function, something like:

# This is one of the 3 candidate algorithms considered for centroid calculation.
# For a more detailed discussion, see PR #1084 and commit eb33176

(The reason it's not in the dosctring is that it's a message for the devs - not the users)

4. Lastly, you used both round() and astype(int) before returning the result. At one point I said that round wasn't needed, but I was wrong. Feel free to use either one before returning the Point result.

5. As for a private discussion, the only other alternative I can offer is via X. Other than that, if you have a broader thought regarding future algorithm work, feel free to leave it here for us.

Thank you very much! I can take it from here :)

Thank you very much! I can take it from here :)

ok, X didn't fit either for political reasons, so I won't talk about it anymore
if you have a telegram and can write to me, here is mine: @neon0_o

@SkalskiP, I ran the tests - ready to merge.

Hi @sharingan000 and @LinasKo 👋🏻, I just read the whole conversation. It's so informative, and I'm glad that, in the end, you were able to come up with an optimal solution. 🔥 I'm merging this PR!

I plan to highlight this change in our upcoming supervision-0.20.0 release notes. Could any of you create a colab / script demonstrating why is this albo better? 2/3 examples of polygons where we get a more accurate result?

Hi @sharingan000 and @LinasKo 👋🏻, I just read the whole conversation. It's so informative, and I'm glad that, in the end, you were able to come up with an optimal solution. 🔥 I'm merging this PR!

I plan to highlight this change in our upcoming supervision-0.20.0 release notes. Could any of you create a colab / script demonstrating why is this albo better? 2/3 examples of polygons where we get a more accurate result?

Hi, thanks for the reply. Of course I can, tell me what time to cook please

Hey @sharingan000, appreciate your eagerness to contribute :)

If it helps, here's some roughly hacked-together code I had for testing.
Feel free to use as much or as little of it as you want - only as much as it helps you :)

import numpy as np
import matplotlib.pyplot as plt
from itertools import cycle
from supervision.geometry.utils import get_polygon_center

from algos import PolygonCenterGetter, Point


def plot_polygon(verts: np.ndarray, *centers: Point):
    colors = cycle('bgrcmy')
    size = 20
    plt.fill(verts[:, 0], verts[:, 1])
    for center, color in zip(centers, colors):
        plt.plot(center.x, center.y, f'{color}o', markersize=size)
        size -= 5
    plt.legend(["", "Mean", "Frame", "Solid"])
    plt.gca().invert_yaxis()
    plt.show()


def vertices_concave_hex(y_top: int, y_bot: int, x_left: int, x_right: int) -> np.ndarray:
    """
    A concave hexagon, where sides are vertical and center points are instead inside the figure,
    Also, the 2 edges connecting to the top-middle point are made of 100 vertices instead of just 2.

    """
    EDGE_VERT_COUNT = 5
    h = y_bot - y_top
    w = x_right - x_left

    vertices = []
    vert_tl = [y_top, x_left]
    vert_tm = [y_top + h * 0.25, x_left + w // 2]
    vert_tr = [y_top, x_right]

    vert_br = [y_bot, x_right]
    vert_bm = [y_bot - h * 0.25, x_left + w // 2]
    vert_bl = [y_bot, x_left]

    edge_verts_tm_tl = np.linspace(vert_tl, vert_tm, EDGE_VERT_COUNT)[1:-1]
    edge_verts_tm_tr = np.linspace(vert_tm, vert_tr, EDGE_VERT_COUNT)[1:-1]

    vertices = np.array([vert_tl, *edge_verts_tm_tl, vert_tm,
                        *edge_verts_tm_tr, vert_tr, vert_br, vert_bm, vert_bl])

    return vertices


def vertices_concave(size: int, thick: int, thin: int) -> np.ndarray:
    assert size > thick > 0
    assert size > thin > 0

    return np.array([
        # ->
        [0, 0], [0, size], [thin, size],
        # <-
        [thin, thin],
        # up
        [size - thick, thin], [size - thick, size], [size, size],
        # down
        [size, 0]])


# Simple square
poly = np.array(
    [[0, 10], [10, 10], [10, 0], [0, 0]]
)
centers = []
# centers.append(PolygonCenterGetter.mean_algo(poly))
# centers.append(PolygonCenterGetter.frame_algo(poly))
# centers.append(PolygonCenterGetter.solid_algo(poly))
centers.append(get_polygon_center(poly))

plot_polygon(poly, *centers)


# Envelope
poly = vertices_concave_hex(0, 200, 0, 200)

centers = []
# centers.append(PolygonCenterGetter.mean_algo(poly))
# centers.append(PolygonCenterGetter.frame_algo(poly))
# centers.append(PolygonCenterGetter.solid_algo(poly))
centers.append(get_polygon_center(poly))

plot_polygon(poly, *centers)

# Concave - thin
poly = vertices_concave(100, 25, 2)

centers = []
# centers.append(PolygonCenterGetter.mean_algo(poly))
# centers.append(PolygonCenterGetter.frame_algo(poly))
# centers.append(PolygonCenterGetter.solid_algo(poly))
centers.append(get_polygon_center(poly))

plot_polygon(poly, *centers)

# Concave - thick
poly = vertices_concave(100, 55, 2)

centers = []
# centers.append(PolygonCenterGetter.mean_algo(poly))
# centers.append(PolygonCenterGetter.frame_algo(poly))
# centers.append(PolygonCenterGetter.solid_algo(poly))
centers.append(get_polygon_center(poly))

plot_polygon(poly, *centers)

import numpy as np
from collections import namedtuple

Point = namedtuple("Point", ["y", "x"])


class PolygonCenterGetter:

    @staticmethod
    def mean_algo(polygon: np.ndarray) -> Point:
        """
        Calculate the center of the polygon as the center of mass
        of the points.
        """
        center = np.mean(polygon, axis=0).astype(int)
        return Point(y=center[0], x=center[1])

    @staticmethod
    def frame_algo(polygon: np.ndarray) -> Point:
        """
        Calculate the center of the polygon as the center of mass
        of the frame formed by the points of this polygon.
        """
        polygon = polygon.astype(np.float32)
        shifted_polygon = np.roll(polygon, 1, axis=0)
        points = (shifted_polygon + polygon) / 2
        vectors = shifted_polygon - polygon
        mass = np.sum(vectors ** 2, axis=1) ** 0.5
        center = np.dot(mass, points) / np.sum(mass)

        return Point(y=center[0], x=center[1])

    @staticmethod
    def solid_algo(polygon: np.ndarray) -> Point:
        """
        Calculate the center of the polygon as the center of mass
        of a solid homogeneous figure
        """
        shift_polygon = np.roll(polygon, -1, axis=0)
        signed_areas = np.cross(polygon, shift_polygon) / 2
        if signed_areas.sum() == 0:
            center = np.mean(polygon, axis=0)
            return Point(y=center[0], x=center[1])
        centroids = (polygon + shift_polygon) / 3.0
        center = np.average(centroids, axis=0, weights=signed_areas)
        return Point(y=center[0], x=center[1])

from itertools import cycle
import cv2
from matplotlib import pyplot as plt
import numpy as np
import supervision as sv
from ultralytics import YOLO
from time import time

from algos import PolygonCenterGetter, Point


def plot_polygon(verts: np.ndarray, *centers: Point):
    colors = cycle('bgrcmy')
    size = 20
    plt.fill(verts[:, 0], verts[:, 1])
    for center, color in zip(centers, colors):
        plt.plot(center[0], center[1], f'{color}o', markersize=size)
        size -= 5
    plt.legend(["", "Mean", "Frame", "Solid"])
    plt.gca().invert_yaxis()
    plt.show()


image = cv2.imread("<image>")  # Please use your own image
model = YOLO('yolov8n-seg.pt')

result = model(image)[0]
detections = sv.Detections.from_ultralytics(result)

for mask in detections.mask:
    print(mask.shape)

# Mask is a (525, 825) array of True / False.
# Generate and save an image:
mask = detections.mask[0]
mask = mask.astype("uint8") * 255
cv2.imwrite("mask.png", mask)

# Find vertices, via openCV contours
image = cv2.imread("mask.png", cv2.IMREAD_GRAYSCALE)
contours = cv2.findContours(image, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)

# plt.imshow(image, cmap="gray")
# plt.show()

# Reshape to list of Points(y, x) namedtuples.
contours = contours[0] if len(contours) == 2 else contours[1]
contours = contours[0].squeeze()
contours = [Point(x=cont[1], y=cont[0]) for cont in contours]  # x, y -> y, x
contours = np.array(contours)
print("Num vertices:", len(contours))

centers = []
t0 = time()
centers.append(PolygonCenterGetter.mean_algo(contours))
t1 = time()
centers.append(PolygonCenterGetter.frame_algo(contours))
t2 = time()
centers.append(PolygonCenterGetter.solid_algo(contours))
t3 = time()
print("Time mean:", (t1 - t0) / 1000)
print("Time frame:", (t2 - t1) / 1000)
print("Time solid:", (t3 - t2) / 1000)

plot_polygon(np.array(contours), *centers)

Note that I've adjusted the y,x axes a bit and still my prior mistake might remain.

Thanks again for helping us out!

Hey @sharingan000, appreciate your eagerness to contribute :)

If it helps, here's some roughly hacked-together code I had for testing. Feel free to use as much or as little of it as you want - only as much as it helps you :)

main.py - import algorithms, define polygons, run results
algos.py - algorithms, though it's better to use a local version of supervision instead
segment.py - alternative to main, does segmentation on an image, plots that
Note that I've adjusted the y,x axes a bit and still my prior mistake might remain.

Thanks again for helping us out!

Thank you very much, I’ll try to do a couple more visual tests soon if necessary, but here I want to leave a couple of questions that interest me, since I can’t register anywhere else)

1. How can you become a roboflow contributor?

2. Do you need algorithms related to geometry (I had an idea, for example, create an algorithm that would increase/decrease the resolution of a polygon (number of points)), the fact is that I don’t have much experience in ML to implement any ideas in this part in your repository, but in geometry I can come up with something and I would like to make some other contribution to this wonderful project

Hi @sharingan000,

With respect to your questions:

1. You already are! We welcome contributions from the community and, provided they align with our vision for the product, often include them in the open source repositories we have. If in doubt, think in terms of how a user would use a feature and make it intuitive for them.

You could also look at new issues and PRs popping up, see how other contributors engage with those. If a contributor says they'd like to take on it, we'd assign it to them to make sure there's not clashes, and they can do it. Do note that your case was a bit of an exception in how much time I could dedicate to it - normally it's a bit less 😄

There are also some paid positions, but I myself am new, so I'll refer your to the careers page: https://roboflow.com/careers.

2. If it fixes an obvious issue we have, in a concise manner - just like your contribution did - absolutely! In terms of new algorithms, it's all a matter whether they're useful to the end-user, can be applied to multiple problems, and integrate nicely into the codebase. For example, the polygon downscaling, to my knowledge, is rarely needed when people use Roboflow, so it's unlikely we'd add that. What we see as important tends to appear on the issue board. At the same time, we appreciate you having an eye open for things to help with, that we may have missed!

I hope that answers your questions.