Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
share|improve this question
    
You have tagged your question (conformal-geometry), but the text of your question doesn't require the map to be conformal. Please clarify this discrepancy. –  MvG Oct 18 '12 at 7:03
    
Given that a ray starts at the origin and extends to infinity in some definite direction $\phi\in{\mathbb R}/(2\pi)$, what do you mean by the two "extrema points" $(xA,yA)$, $(xB,yB)$ on such a ray? –  Christian Blatter Oct 18 '12 at 9:19
    
I suppose he means that these two points are the ones (among those on this particular given ray) that have minimum and maximum distance from the origin, respectively. –  bubba Oct 22 '12 at 11:07
    
@msotaquira: Maybe we don't share the same concept of "ray". To me (and most other people, I think), a "ray" is a semi-infinite line. In other words, it starts at some fixed point (the origin, typically) and it shoots off to infinity in some direction. So, a ray isn't just an infinite line; it's a "half-line". Are your points $(xA,yA)$ and $(xB,yB)$ on the same ray, or are they merely on the same line? Saying it another way -- is the origin allowed to be in between $(xA,yA)$ and $(xB,yB)$? –  bubba Oct 22 '12 at 11:14

2 Answers 2

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.

share|improve this answer
    
My mistake: I'm really mapping to the unit disk, NOT the unit circle! And yes, the points are all aligned on a finite number of rays emanating from the same origin. The mapping you suggested (x,y)↦(x/d,y/d) would work. However, what I want is one of the extrema points of the ray (say (xA,yA) located at a distance dA from the origin) be mapped to the point r=-1 within the disk, whereas the other extremum (say (xB,yB) located at a distance dB$\neq$dA) be mapped to the point r=1 within the disk. How to accomplish this? Thanks again! –  msotaquira Oct 18 '12 at 6:38
    
Sorry if I was not clear. What I want is that both extrema points be mapped to r=1! See the update I just posted on my original question. –  msotaquira Oct 18 '12 at 6:48

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 .

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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