18
$\begingroup$

I want to make an algorithm grouping all the details having the same shape. each detail is defined by its surface, and a list of contour lines.

First I believed that having the same perimeter length and same surface would be enough, but I saw on that link that it is wrong hypothesis.

If I take as additional condition that the two shapes have the same number of segments, would it be enough? Or else how can I check that?

The problem is for each detail, they can get rotation, or symmetry.

Edit :

Thanks for your answers, I finally found a way to solve the problem (answer below)

$\endgroup$
  • $\begingroup$ Wouldn't a kite/parallagram be a counter example? I think it'd be very hard to find the precise conditions that will allow you to say definitively: you can't cut a shape up into pieces are rearrange them with the same perimeter. Number of legs is certainly not enough. $\endgroup$ – fleablood Jul 25 at 6:06
  • $\begingroup$ @stevengregory yes, but the linked answer was regarding 2 details with same surface and perimeter. I am trying to find a solution taking more parameters in account, as number of segments, or list of angles between segments... I think if I take in account list of segments with the list of their length and list of angles between each segment that would be enough. $\endgroup$ – Siegfried.V Jul 25 at 8:06
  • $\begingroup$ Well I found solution, will first test it when working, then post my answer here, thanks anyway. $\endgroup$ – Siegfried.V Jul 25 at 12:34
  • $\begingroup$ Can't look for it now, but there was an interesting video on the Numberphile youtube channel this month talking about how to detect uniqueness of a shape (or a similar issue, I'm not sure). You might want to see it. $\endgroup$ – Mark says Reinstate Monica Jul 25 at 15:39
  • $\begingroup$ @Mark found solution, I am now developping it, I write answer later when I finish to test it. Just excuse me I am new on "Mathematics" stack (I use to be on stackoverflow), may my answer e graphical, or can I explain it with a bit of code? $\endgroup$ – Siegfried.V Jul 25 at 15:56
82
$\begingroup$

In the spirit of the no-words answer to the linked question:

two shapes made up of squares which have the same perimeter and area but which are different shapes

$\endgroup$
  • 10
    $\begingroup$ I like the simplicity of this, because the demonstration of a single counterexample is sufficient to disprove the conjecture. That ends the discussion nicely. $\endgroup$ – Monty Harder Jul 25 at 16:14
31
$\begingroup$

Inspired by Hagen von Eitzen's answer, a particular pair of tetrominoes furnishes another counterexample (minimal among polyominoes):

enter image description here

$\endgroup$
  • 7
    $\begingroup$ To spoil the no-words approach: Both have area $4$, both have perimeter $10$, and both are octagons (same number, $8$, of segments). $\endgroup$ – Jeppe Stig Nielsen Jul 26 at 22:16
  • 6
    $\begingroup$ You're correct, of course, but I preferred to leave the counting to the reader. $\endgroup$ – Travis Willse Jul 26 at 23:05
13
$\begingroup$

No, it is still not enough. Even for quadrilaterals it is not enough. Take a kite with sides $1,1,3,3$ and the angle between the two $1$s a right angle. The perimeter is $8$ and the area is $\frac 12(1+\sqrt{17})$. Now take a rhombus with sides of $8$. It also has a perimeter of $8$ and you can choose the angle to make the areas match. It is even worse for more sides. The area and perimeter are just two constraints, while there are lots of degrees of freedom.

$\endgroup$
  • $\begingroup$ ok thanks, can you see my edit please? $\endgroup$ – Siegfried.V Jul 25 at 6:37
  • $\begingroup$ found a solution, will first test in in practical, then post it here $\endgroup$ – Siegfried.V Jul 25 at 12:35
  • 1
    $\begingroup$ Here is a more complex example that refutes a weaker version of the asker's idea. Even if you specify that it is a quadrilateral, and you specify that the side lengths taken in order are $1, 1, 3, 3$ (which is stronger than merely requiring the perimeter to be $8$, of course), and specify that the area is $\frac12 (1+\sqrt{17})$, that still does not determine the quadrilateral up to congruence (no angles are specified). The reason is that it can be either the convex kite you mentioned, or a non-convex "arrowhead". $\endgroup$ – Jeppe Stig Nielsen Jul 26 at 22:38
  • $\begingroup$ (continued) For some areas, like $2.9$ (any number between $2\sqrt 2$ and $3$ should work), the two non-congruent quadrilaterals with sides taken in order $1,1,3,3$ are both convex. $\endgroup$ – Jeppe Stig Nielsen Jul 26 at 23:04
7
$\begingroup$

enter image description here

Possibly the simplest counterexample: Form two sides of a triangle with line segments of unequal length. In one version, mirror it. In the other, rotate it 180°.

$\endgroup$
  • $\begingroup$ Even has twice the same angles. $\endgroup$ – vonbrand Aug 7 at 9:17
3
$\begingroup$

Well, I finally managed to do that, but it was longer than expected :

My shape is defined by a list of Contour element, Contour is defined by 2 points and a radius.If this is a segment then radius=0, if this is an arc, radius is positive if I turn in trigonometric direction, negative if opposite side).

I make a first check, checking if areas are equal(just to identify faster if shapes are equal or not).

For each shape, I browse each segment(or circle arc) ClockWise direction and I return 3 results :

  • List of the lengths of segments(just Pythagoras, don't check radiuses)
  • List of radiuses of each segment/arc
  • List of angles between each segment and consecutive segment

I then can compare them (let's take in account that I start from the same point on each figure). In C# I just made a loop trying to start from different points.

If all 3 lists are equals, this means the shapes are equal and without rotation.

Then for symmetry problem I just will recalculate 3 above lists for second shape, but browsing contours in opposite direction, if the results are equal(angles and radiuses just will be opposite sign), so it is the same shape with symmetry.

$\endgroup$
  • 5
    $\begingroup$ It is good that you have solved your problem, but this does not answer the question that you asked. $\endgroup$ – Rory Daulton Jul 26 at 15:26
  • 2
    $\begingroup$ @RoryDaulton exactly, in fact I didn't formulate correctly question, that's why I accepted the other answer that answered perfectly, just added that answer for who would meet the same problem. $\endgroup$ – Siegfried.V Jul 26 at 15:47
  • 1
    $\begingroup$ @RoryDaulton - Actually, it does directly answer the question asked in the OP itself. It is only the question in the title that is not answered by it (and therefore appropriate that Siegfried V has accepted Hagen von Eitzen's answer to that question). $\endgroup$ – Paul Sinclair Jul 26 at 16:46
  • 1
    $\begingroup$ Depending on how many times you have to check for equality, it might make sense to enforce a canonical starting vertex, rather than looping over all possible starting vertices. For instance: define a sorting function on the triples (length, radius, angle), and when you create your objects make sure that each list of triples is the smallest (lexicographically) among its cyclic permutations. If you implement it properly, I think it should cost O(n log n) to create a shape with n edges, and O(n) to compare them, rather than O(n) to create them and O(n^2) to compare them. $\endgroup$ – Federico Poloni Jul 28 at 9:45
  • $\begingroup$ @FedericoPoloni In fact that's a good idea, not only for time spent, but the code would be easier to implement. But not totally sure this would work if I don't take segments in the good order (symmetry)? How do you imagine that sorting function? In my case I think this wouldn't work (not sure), because I also have to check if each segment has some chamfers (can call it 3D?) and each detail has some drillings inside so for Drilling I calculate a List of distances between each drill and each of the angles of my shape. Thanks anyway for the idea that I will look at, just for simplifying my code. $\endgroup$ – Siegfried.V Jul 28 at 11:10
0
$\begingroup$

Yes, as others have demonstrated, you can have different shapes given the same area, perimeter, and number of segments.

Furthermore, it seems to me you can have different shapes given any number of arbitrary metrics. Take this terrible looking key, for instance:

enter image description here

You could easily imagine an infinite number of keys like this each uniquely represented by 7 numbers. For this key, those values would be 2, 3, 1, 2, 3, 1, 2.

These need not be integers.

You could imagine a million-toothed key being uniquely represented with a million numbers.

Now, technically you can use a single real number to represent a million real numbers. However, I don't believe any such function that does this conversion is continuous, and so likely isn't useful for you. When they aren't continuous, you'll have metrics like 5.213283 and 5.213284 represent wildly different shapes.

I would consider perimeter and area nice, continuous metrics. Any small perturbations to the points of the polygon result in a small change in those values.

Note: I could be completely wrong. I look forward to looking up that numberphile video later today.

$\endgroup$
  • $\begingroup$ Well that's nice, but nothing new regarding other answers, the question was more, how to solve that, even if I didn't formulate it correctly in title. Anyway I found how to do it(answer below). $\endgroup$ – Siegfried.V Aug 9 at 2:45
-1
$\begingroup$

A famous problem was posed in 1966, "Can you hear the shape of a drum?" That is, can you find two different planar domains whose spectrum is the same? It was known that any two such domains must have the same area and the same perimeter. The question was answered negatively by Gordon, Webb and Wolpert in the early 1990s. Here is their example:

enter image description here

Notice that the number of sides is also the same, so this answer's the OP's question with even more conditions imposed.

$\endgroup$

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.