3
$\begingroup$

Imagine a set of simple (non-self-intersecting) polygons given by the coordinate pairs of their vertices $[(x_1, y_1), (x_2, y_2), \dots,(x_n, y_n)]$. The polygons in the set have a different number of vertices.

enter image description here

How can I use machine learning to solve various supervised regression and classification problems for these polygons such as prediction of their areas, perimeters, coordinates of their centroids, whether a polygon is convex, whether its centroid is inside or outside, etc?

Most machine learning algorithms require inputs of the same size but my inputs have a different number of coordinates. This may probably be handled by recurrent neural networks. However, the coordinates of my input vectors can be circularly shifted without changing the meaning of the input. For example, $$[(x_1, y_1), (x_2, y_2),...,(x_n, y_n)]$$ and $$[(x_n, y_n), (x_1, y_1),...,(x_{n-1}, y_{n-1})]$$ represent the same polygon where a starting vertex is chosen differently.

Which machine learning algorithm is both invariant to a circular shifting of its input coordinates and can work with inputs of different sizes?

Intuitively, an algorithm could learn to split each polygon into non-overlapping triangles, calculate areas or perimeters of each triangle, and then aggregate these computations somewhere in the output layer. However, the labels (areas or perimeters) are given only for the whole polygons, not for the triangles. Also, the perimeter of the polygon is not the sum of the perimeters of the triangles. Is thinking about this problem in terms of triangles misleading?

Could you please provide references on machine learning algorithms that solve such tasks? Or any advice, how to approach this task? It does not have to be neural network and does not have to learn exact analytic formulas. Approximate results would be enough.

$\endgroup$
3
$\begingroup$

You can split each polygon into a collection of triangles and sum up the areas. Not really sure why you would bother with ML.

Anyway if you approximates these polygons as images you could maybe train a CNN. Look at the image classification networks which provide bounding boxes.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I don't want to hardcode it. I want an algorithm to figure out a solution itself. I would bother with ML in this toy problem in order to use it for more complicated system. My question is what kind of ML to use for inputs that are of different size, can be cyclically shifted, and for which the property searched is calculated from its parts. $\endgroup$ – Vladislav Gladkikh Apr 10 at 2:16
  • 1
    $\begingroup$ Look at bounding box object detectors, yolo etc. You're going to need to remove a couple layers and then train. On the positive side, you can generate unlimited training data. $\endgroup$ – FourierFlux Apr 10 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.