Map 2D points inside a closed curve to unit disk

Question

Hy everyone,

I have a set of 2D cartesian points (x,y coordinates) lying inside an arbitrary closed contour , something like this: arbitrary_closed_contour

by 'arbitrary' I mean that the closed curve does not resemble any circle or ellipse.

What I want to do know is to map each pair of x,y coordinates to unit circle, thus obtaining something like this: points mapped to unit circle

How to accomplish this? I must confess up to this point I'm clueless!

Thanks for any suggestion.

Update: (based on @bubba comments)

Some clarifications:

1. I want to map each pair of (x,y) coordinates to the unit disk, not the unit circle.
2. The points I want to map emanate all from the same origin of coordinates. They're also distributed along a set of rays radially distributed
3. Each of these rays have two extrema points ((xA,yA) and (xB,yB)) each of them located at a different distance from the origin. Constrain: when mapped each of these points should be located on r=1

Answer 1

You're really mapping points to the unit disk, not the unit circle.

It looks like the points are all aligned on a finite number of "rays" that emanate radially from the origin. If so, this makes things much easier.

On a given ray, you map points as follows: Let $d$ be the distance from the origin to the outermost point on the ray. The mapping for points on this ray is then just $(x,y) \mapsto (x/d, y/d)$.

If you want a single mapping/deformation that applies uniformly to all points, regardless of what ray they lie on, then some sort of interpolation between rays would be needed. But I won't go into that unless you confirm that you need it.

Answer 2

Your question reads like you're looking for an implementation of the transformation whose existence is stipulated by the Riemann mapping theorem; particularly as you tagged it conformal-geometry.

Literature

Unfortunately, these beasts are rather hard to compute even for simple shapes, with huge numerical issues. The best continuous solutions seem to be based on Schwartz-Christoffel mappings. There is (at least) a whole book on the subject, which might be useful to you:

Driscoll and Trefethen Schwarz-Christoffel Mapping, Cambridge press, 2002

Recent developments in discrete differential geometry provide discretized concepts of conformal maps. One that I have intimate knowledge of is described in this article:

Springborn, Schröder and Pinkall, Conformal Equivalence of Triangle Meshes, ACM Transactions on Graphics 27:3

Algorithm

So what I'd do is the following:

1. Triangulate both your input shape and the circle in an arbitrary way
2. Choose an arbitrary triangle as intermediate step
3. Map both triangulations onto the triangle using my own implementation of the algorithm from the paper referenced above
4. Use the projective interpolation scheme described in that paper to map points first onto the triangle and from there onto the circle

There are a lot of arbitrary choices in the above approach. There is an arbitrary choice of a triangle, and for both partial mappings there is a choice which vertices of the triangulation should correspond to the corners of the triangle. In the continuous theory, the choice of the triangle is arbitrary, as is the choice of one set of corner vertices. The second choice of corner vertices fixes a Möbius transformation, as the conformal map is unique only up to Möbius transformations.

In practice, however, these choices will have significant impact on numeric stability. In a first attempt, I'd try the following heuristics. From the polygonal outline of the triangulated input shape, choose those vertices where the interior angle is minimal, and map those onto the corners of the triangle. Sum up the edge lengths along the rim of the polygon between these points, and use these three lengths as the edge lengths of your triangle. Also use these lengths as arc lengths along the rim of the circle to choose the corresponding vertices there as well. Make the triangulation of your shapes reasonably regular. With a bit of luck, this will work well enough. If not, new ideas might be required.