2

Suppose I have two pentagons, A and B with vertices

(x1, y1), (x2, y2), ... (x5, y5) for A

and

(x'1, y'1), ... (x'5,y'5) for B.

I know the correspondence of the vertices:

(x1, y1) <==> (x'1, y'1)

Similarly all the vertices.

I need a procedure to transform all the points inside A to B.

I found a similar problem for quadrilaterals in Transform quadrilateral into a rectangle?.

In my case, they are not quadrilateral, they are pentagons. I would actually like a solution that works for an arbitrary number of vertices (pentagon, hexagon, etc.).

Community
  • 1
  • 1
noname noname
  • 71
  • 1
  • 6
  • Are the polygons strictly convex and are all three-tuples of vertices noncolinear? I doubt there is a generic algorithm for mapping points from one polygon to another with the same vertex count, as the mapping will not be bijective in tons of degenerate cases. – Blender Jun 10 '12 at 02:30
  • The polygons are not necessarily convex, but are non-collinear. I found a solutions at http://alumni.media.mit.edu/~cwren/interpolator/. But, for the concave case, (in fact for convex too) it is not working for more than 4 vertices. – noname noname Jun 10 '12 at 02:42
  • So much theory. But in practice, his pentagons are gonna be convex or nearly convex and spider web stretching algorithm can be applied, which I'm too lazy to expound here. – Boris Stitnicky Jun 10 '12 at 02:42
  • Ok, noname, you commented while I typed. In concave cases, you'll in practice need to make a decision on how you will consistently find a spider web center in various concave misshaped pentagons. Afterwards, the rest is easy. – Boris Stitnicky Jun 10 '12 at 02:45
  • Thanks Blender and Boris. At this point I don't know how to use spider web, but I am going to look at it. – noname noname Jun 10 '12 at 02:53

3 Answers3

4

If you were mapping a triangle to a triangle you would use barycentric coordinates.

For mapping polygons to polygons, you can use generalized barycentric coordinates. There are several families of these. One of those families - mean value coordinates - were introduced in this paper and followup. A good bibliography of the whole subject, which has exploded in the past decade, can be found here. Another early paper which describes so-called harmonic and Wachpress coordinates is here.

brainjam
  • 18,863
  • 8
  • 57
  • 82
0

I think you just subdivide the polygon radially into triangles (make pizza slices from the center, extending out to the vertices) and then find the (u, v) coordinates of any point in the original polygon.

Once you have that information, finding the corresponding triangle in the second polygon will be trivial (you already know what points constitute its vertices) and (u, v) mapping for a triangle is well-documented.

Blender
  • 289,723
  • 53
  • 439
  • 496
  • Your problem is with the word "radially" - how do you find the center? There are concave cases, you know. His pentagons are not pizzas, read the comments above. – Boris Stitnicky Jun 10 '12 at 02:49
  • I don't think the concave/convex cases make a difference. The triangles will map just the same in every case (things will break down, however, if your triangles become degenerate). As for the center, just find the centroid: http://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon – Blender Jun 10 '12 at 02:52
  • An what if the centroid is outside the pentagon? Then you can end up mapping a point outside to a point inside a let's say another convex pentagon. I don't thing that this is what noname wants. – Boris Stitnicky Jun 10 '12 at 02:57
  • How can it map outside to inside (or vice versa) if the polygons are convex? – Blender Jun 10 '12 at 03:04
  • "The polygons are not necessarily convex, but are non-collinear" - citing the asker. – Boris Stitnicky Jun 15 '12 at 19:15
0

I would suggest, but I cannot prove it, that for pentagons (but probably not hexagons and higher n polygons), when for each vertex you color a set of points in the interior of the pentagon that can be seen from that vertex, then their intersection will alway be non-empty and you can choose the center of the spider web (or deformed pizza, if you like) from that intersection arbitrarily and subsequently use the triangle mapping.

Boris Stitnicky
  • 12,444
  • 5
  • 57
  • 74
  • Also, I believe that although you cannot use this method for concave hexagons, I believe that it would work with two "spider web centers", and heptagon with 3, octagon with 4 etc. I hope my intuition is not mistaken here. Am I writing clear enough? – Boris Stitnicky Jun 10 '12 at 03:03