1. geometric problem
Hi all. I have a small problem which has evaded every attempt I have
made to solve it. I need a routine that does the folowing:
* Given an arbitrary rectangular polygon {V1, V2, V3, V4} where Vx is
a vertex point {x, y} and the vertexes are ordered clockwise on the
rectangle starting at the top left, so that the line V1 -> V2 might be
called the top,
* Also given a point {x, y} that could be inside or outside the polygon
* Evaluates two expressions mag_x and mag_y such that both expressions
will be linearly interpolated between opposing lines on the polygon
(left side and right side for mag_x and top to bottom for mag_y) to
provide a value in the range of 0 to 1 while the point is inside the
polygon on either 'axis', and < 0 or > 1 when it is outside.
Phew! Basically I want to project a point in an arbitrary polygon into
a cartesian space that is the equivalent of a unit square, keeping track
of orientation. This is the reverse of a procedure I use to map such a
coordinate system into an arbitrary polygon. That was easy. Now I need
it back!
I have had so little success coming up with capable code that i decided
to ask better minds than mine. I have tried seriously twice, enough
times to realize I don't really know whats going on. My first attempt
tried to weight vectors orthagonal to opposing sides (dont laugh) and
was a complete failure. My second attempt found the intercept between
opposing lines, and their angles, then found the angle of a line
connecting the point to the intercept and then evaluated the mag by
comparing the angles. This procedure had more success, but needed to
deal with so many 'special cases', i.e. paralell, and worse, near
paralell lines, angle quadrant problems, etc. that I eventually gave up
on it in despair. I really need something that can handle any weird
input.
I'm sure there is a simple solution, some kind of simultaneous equation,
but I slept through that class at school (doh!) Please would somebody
with more math than me help me out please. Um, if I havent explained
this very well and you need more information don't hesitate to mail me.
Thanks,
Nick
2. Re: geometric problem
I'm not sure how you went from the regular, cartesian basis, to your
arbitrary rectangular basis, but here's how I'd do it (then going the
other way is easy):
First we need to define a new basis for our rectangle. Using your
orientation of the vertices, I'd use the vector
X = V1-V4= [xv1 - xv4]
[yv1 - yv4]
(where xv1 is the x component of vertex 1, etc) as our new 'y' basis
vector, and
Y = V3-V4= [xv3 - xv4]
[yv3 - yv4]
as our new 'x' basis vector. To project the point on our new basis, we
can combine X and Y into a matrix [X Y], and multiply the matrix by the
coordinates of our point:
[(xv1 - xv4) (xv3 - xv4)] [x] [(xv1 - xv4)x + (xv3 - xv4)y] [x']
[(yv1 - yv4) (yv3 - yv4)] [y]=[(yv1 - yv4)x + (yv3 - yv4)y]= [y']
I know that there are some libraries in the archives that will do the
calculations for you. They would also make the reverse calculation
easy.
Having this equation gives you what you need to go backwards. Now, if
you have x' and y', you can solve for x and y. You're right, here, you
can simply solve 2 simultaneous equations, or you can find the inverse
of the matrix, and multiply the right hand side of the equation.
I know there is a simple formula for the inverse of a 2x2 matrix, but it
escapes me for the moment. However, the matrix libraries in the
archives should be able to solve this for you.
This procedure assumes that you're considering V4 to be the origin. If
that's not so, just add V4 to any 'normal' point (after the
transformation), and subtract V4 from any point based on your
rectangular basis (before the transformation) that you're looking at to
make the transformation come out right.
Note that it doesn't matter what angle the polygon is at in relation to
the standard x/y axes.
Matthew W Lewis
KAPCO
>-----Original Message-----
>From: Nick [mailto:metcalfn at ALPHALINK.COM.AU]
>
>
>Hi all. I have a small problem which has evaded every attempt I have
>made to solve it. I need a routine that does the folowing:
>
>* Given an arbitrary rectangular polygon {V1, V2, V3, V4}
>where Vx is
>a vertex point {x, y} and the vertexes are ordered clockwise on the
>rectangle starting at the top left, so that the line V1 -> V2 might be
>called the top,
>* Also given a point {x, y} that could be inside or outside
>the polygon
>
>* Evaluates two expressions mag_x and mag_y such that both expressions
>will be linearly interpolated between opposing lines on the polygon
>(left side and right side for mag_x and top to bottom for mag_y) to
>provide a value in the range of 0 to 1 while the point is inside the
>polygon on either 'axis', and < 0 or > 1 when it is outside.
>
>Phew! Basically I want to project a point in an arbitrary polygon into
>a cartesian space that is the equivalent of a unit square,
>keeping track
>of orientation. This is the reverse of a procedure I use to map such a
>coordinate system into an arbitrary polygon. That was easy.
>Thanks,
>Nick
>
3. Re: geometric problem
I'll attempt to sum up what I _think_ you've said :)
You have the following:
V1
/ \.
/ V2
/ |
V4 |
`-. P `. -- All Vn to Vm lines are *supposed* to be straight :)
`-. |
`-.V3
And want to translate to:
V1'------V2'
| |
| |
| P' |
| |
V4'------V3'
You never said how big V'(1,2,3,4) has to be though...
Why you want to do this (unless you're writing a ray-tracer) is beyond me,
but I'll have a go. I'm thinking on my feet here. Be warned!
The first sensible thought that occurs is the following: (this will not
provide a correct answer. Approximation only)
1) Figure out the coordinates of the rectangle (X) that would completely
surround V(1,2,3,4).
In this case (from the diagrams above) they're:
X1 = {V4.x,V1.y}
X2 = {V3.x,V1.y}
X3 = V3
X4 = {V4.x,V3.y}
2) Alter the P position like so:
P.x = P.x + (X(1,2,3,4).x - V(1,2,3,4).x ) / 4
P.y = P.y + (X(1,2,3,4).y - V(1,2,3,4).y ) / 4
^^^ This is really the all-important bit. There's probably a much
better way to do this, but I'd have to sit for a few hours to work it
out. As it stands, I've used an arithmetical mean of the differences of
respective x and y coordinates. Maybe a geometric mean may have been
better... ;)
3) Scale X(1,2,3,4).x, X(1,2,3,4).y and P to the sizes you want them to be
(multiply or divide) to turn them into V'(1,2,3,4) and P'.
You'll have to offset the coordinates so that one of the Xs is {0,0}
for the scaling. Add the offset back in to complete the calculation.
4) If this was homework, I hope I got it horribly wrong. ;)
HTH,
Carl
PS If you don't understand the notation that I munged for this post,
mail again and I'll explain it. :)
--
Carl R White -- cyrek- at -bigfoot.com -- http://www.bigfoot.com/~cyrek
aka Cyrek -- No hyphens :) -- Bigfoot URL Alias
4. Re: geometric problem
Get a book called "Fundamentals of Interavtive Computer Graphics" by
J.D. Foley & A. Van Dam ... It has all the math and some good short
-cuts in it... Its not a quick read but very helpfull ... It also has a
reference to other books and papers(some are able to be found on the
net.. the urls excape me right now)....
GV
>From: Nick <metcalfn at ALPHALINK.COM.AU>
>Reply-To: Euphoria Programming for MS-DOS
<EUPHORIA at LISTSERV.MUOHIO.EDU>
>To: EUPHORIA at LISTSERV.MUOHIO.EDU
>Subject: geometric problem
>Date: Fri, 19 Mar 1999 03:30:59 +1000
>
>Hi all. I have a small problem which has evaded every attempt I have
>made to solve it. I need a routine that does the folowing:
>
>* Given an arbitrary rectangular polygon {V1, V2, V3, V4} where Vx
is
>a vertex point {x, y} and the vertexes are ordered clockwise on the
>rectangle starting at the top left, so that the line V1 -> V2 might be
>called the top,
>* Also given a point {x, y} that could be inside or outside the
polygon
>
>* Evaluates two expressions mag_x and mag_y such that both expressions
>will be linearly interpolated between opposing lines on the polygon
>(left side and right side for mag_x and top to bottom for mag_y) to
>provide a value in the range of 0 to 1 while the point is inside the
>polygon on either 'axis', and < 0 or > 1 when it is outside.
>
>Phew! Basically I want to project a point in an arbitrary polygon into
>a cartesian space that is the equivalent of a unit square, keeping
track
>of orientation. This is the reverse of a procedure I use to map such a
>coordinate system into an arbitrary polygon. That was easy. Now I
need
>it back!
>
>I have had so little success coming up with capable code that i decided
>to ask better minds than mine. I have tried seriously twice, enough
>times to realize I don't really know whats going on. My first attempt
>tried to weight vectors orthagonal to opposing sides (dont laugh) and
>was a complete failure. My second attempt found the intercept between
>opposing lines, and their angles, then found the angle of a line
>connecting the point to the intercept and then evaluated the mag by
>comparing the angles. This procedure had more success, but needed to
>deal with so many 'special cases', i.e. paralell, and worse, near
>paralell lines, angle quadrant problems, etc. that I eventually gave
up
>on it in despair. I really need something that can handle any weird
>input.
>
>I'm sure there is a simple solution, some kind of simultaneous
equation,
>but I slept through that class at school (doh!) Please would somebody
>with more math than me help me out please. Um, if I havent explained
>this very well and you need more information don't hesitate to mail me.
>
>Thanks,
>Nick
>
Get Your Private, Free Email at http://www.hotmail.com
5. Re: geometric problem
He He, perhaps I should clarify some things. I'm a dunce at stuff like
this, which is of course why I'm writing a fractal program :) This is what
it's for. I'll begin at the start. When I want to draw a fractal, or part
of a fractal, I wish to specify the corners of the fractal picture as one
might specify a polygon. I wanted code to allow any rotation, scale,
distortion etc. that was possible without a hiccup.
What it does: to translate from 'screen' space to 'fractal' space where the
screen space is determined by the current resolution, and the fractal space
is bounded by a four vertex polygon. I achieved this the following way:
step 1 : divide the screen coordinate by the resolution to get a range 0
to 1
step 2: find a point on the line from vertex 1 to vertex 2 proportional
to the x-range
step 3: find a point on the line from vertex 4 to vertex 3 proportional
to the x-range
step 4: find a point on the line from step 2 to step 3 proportional to
the y-range
Perfect! Theres the point to feed into the iterator. This works in all
cases, even with crossed lines, super stretching and stuff. All
transformations are achieved by manipulating the fractal polygon. This
works fine.
Now, when I store a sequence of polygon corners for an animation, I could
choose to store the polygon vertices as points in screen space or points in
fractal space. Having points in screen space raises the problem of what to
do after zooming, when the sequence no longer defines the same space. Hmm,
not very good. Well, what about storing polygons as points in fractal
space? Great, now the points are independent of any zoom scale, but, um,
now I need the points back in screen space to do the animation preview and
control panel.
Thanks for the responses so far, I'll have to nut each one out and try them
on for size. I hope this post resolves some curiosities. It's not for
raytracing, and most certainly not for homework, I havn't seen the inside of
a school for six years. Oh yes, and I need it to be accurate, or there's
not much point really. (ugh..sorry:)
Thanks again,
Nick
Nick wrote:
> Hi all. I have a small problem which has evaded every attempt I have
> made to solve it. I need a routine that does the folowing:
>
> * Given an arbitrary rectangular polygon {V1, V2, V3, V4} where Vx is
> a vertex point {x, y} and the vertexes are ordered clockwise on the
> rectangle starting at the top left, so that the line V1 -> V2 might be
> called the top,
> * Also given a point {x, y} that could be inside or outside the polygon
>
> * Evaluates two expressions mag_x and mag_y such that both expressions
> will be linearly interpolated between opposing lines on the polygon
> (left side and right side for mag_x and top to bottom for mag_y) to
> provide a value in the range of 0 to 1 while the point is inside the
> polygon on either 'axis', and < 0 or > 1 when it is outside.
>
> Phew! Basically I want to project a point in an arbitrary polygon into
> a cartesian space that is the equivalent of a unit square, keeping track
> of orientation. This is the reverse of a procedure I use to map such a
> coordinate system into an arbitrary polygon. That was easy. Now I need
> it back!
>
> I have had so little success coming up with capable code that i decided
> to ask better minds than mine. I have tried seriously twice, enough
> times to realize I don't really know whats going on. My first attempt
> tried to weight vectors orthagonal to opposing sides (dont laugh) and
> was a complete failure. My second attempt found the intercept between
> opposing lines, and their angles, then found the angle of a line
> connecting the point to the intercept and then evaluated the mag by
> comparing the angles. This procedure had more success, but needed to
> deal with so many 'special cases', i.e. paralell, and worse, near
> paralell lines, angle quadrant problems, etc. that I eventually gave up
> on it in despair. I really need something that can handle any weird
> input.
>
> I'm sure there is a simple solution, some kind of simultaneous equation,
> but I slept through that class at school (doh!) Please would somebody
> with more math than me help me out please. Um, if I havent explained
> this very well and you need more information don't hesitate to mail me.
>
> Thanks,
> Nick
6. Re: geometric problem
OK, that makes it a little more complicated, but not much. The sticking
point is that you need to use a 3x3 matrix instead of a 2x2. Here's how
it works:
(I'm assuming that V1 is the upper left and corresponds to (1,0) using
standard coordinates, and the other vertices are labeled clockwise.)
Let vector d = V1-V4
c = V3 - V4
a = V2 - V1
To translate from standard to the fractal, we need to find the vector:
axy - cxy + cx + dy
Here's why:
First, we find your points along the top and bottom sides ( ax , cx ).
Then we get the vector e = ax + d - cx. This gives us the vector from
the point on the bottom line to the top line.
Then we need to scale e by our y value, which gives us ey = axy + dy -
cxy.
If we add this to cx, we get the vector to the point in fractal space:
axy - cxy + cx + dy
Now, there's no way to do this using a 2x2 matrix because of the xy
terms. So we add that to our computations, and our matrix will look
like:
[c1 d1 (a1 - c1) ] [ x ] [x' ]
[c2 d2 (a2 - c2) ]*[ y ]=[y' ]
[c3 d3 (a3 - c2) ] [ xy] [xy']
Of course, you can ignore the xy value when plotting. It's only
important to calculate the values. And the reverse translation is just
the solution to the simultaneous equations! (Nick, I sent that process
to you privately.) The matrix libraries in the archives should be able
to solve that for anyone interested.
Matthew W Lewis
KAPCO
>-----Original Message-----
>From: Nick [mailto:metcalfn at ALPHALINK.COM.AU]
>
>What it does: to translate from 'screen' space to 'fractal'
>space where the
>screen space is determined by the current resolution, and the
>fractal space
>is bounded by a four vertex polygon.
