• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Etch-a-Sketch Analytic Geometry

 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Let's consider a type of planar geometry that is the same as what we're all used to EXCEPT that the distance between two points is defined as the sum of the absolute values of the differences in their x and y coordinates. i.e. distance(A, B) = |xA-xB| + |yA-yB|. (Basically, it's the minimum amount you'd have to turn the knobs on an Etch-a-Sketch to get from one point to the other.

It shouldn't be too much of a stretch at all to define the distance from a point to a line is the minimum distance from the point to some point on the line.


A. Under this new 'distance' definition, what does a circle look like? (A circle is the set of points that are all some constant distance from a given point.)

B. What about an elipse (the points whose sum of distances from two points (the foci) is some constant)?

C. A parabola (the points that are equidistant from a point and a line)?

D. A hyperbola (the points whose difference of distances from two points is some constant)?

The 'elipse' and 'hyperbola' questions are relatively easy to answer if the foci are on the same horizontal or vertical line. What if we use any two arbitrary points?

Similarly, the 'parabola' question is easy of the given line is horizontal or vertical. What if it's at an arbitrary angle?

Since these questions are "What does XYZ look like", you can either draw a picture or try to describe the results in words.

Have fun.
 
Ranch Hand
Posts: 1923
Scala Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A)
This circle, drawn with the Bresenham-algorightm, might not look like a circle, depending on your font-settings.

If we only regard a quarter of the circle, from center/top to right/center (00:00 to 03:00 o'clock):
We have to walk the radius r down and r right, which is 2 r.
For the whole circle, we have 8 r.

Let's test it empirically (radius=10):

[ May 25, 2006: Message edited by: Stefan Wagner ]
 
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Use the 'reply with quote' button to see the the circle as intended.
We did the travelling salesman problem using this, which we referred to as 'Manhatten distances' due to the rectangular nature.
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Stefan Wagner:
A)
This circle, drawn with the Bresenham-algorightm, might not look like a circle, depending on your font-settings.



But not all the points on that figure are the same distance from the center point.

Let me modify question A) a little by adding a specific point and radius.

A) What does the set of all points that have a distance from (0,0) of 10 look like?
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A diamond, with points at (0, 10), (10, 0), (0, -10), (-10, 0).
 
Ranch Hand
Posts: 112
Android Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Ryan McGuire:
A. Under this new 'distance' definition, what does a circle look like? (A circle is the set of points that are all some constant distance from a given point.)


Originally posted by Ryan McGuire:
B. What about an elipse (the points whose sum of distances from two points (the foci) is some constant)?


Originally posted by Ryan McGuire:
C. A parabola (the points that are equidistant from a point and a line)?


Originally posted by Ryan McGuire:
D. A hyperbola (the points whose difference of distances from two points is some constant)?

Here are 3 possibilities:

Originally posted by Ryan McGuire:
Have fun.


I did! Thanks for this nice puzzle.

Peter

 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A seems easy enough to visualize without a picture. For B and D, I considered solutions for skewed points, (0, 0) and (x, y) where x != y.

B: Ellipses (sum of distances to two points is constant):


The black area is a continuous region in which the sum of distances remains constant.

C: Parabolas (difference in distances to a point and a line is constant)):

I used a different definition here from the one Ryan expressed - the traditional parabola has a difference of zero. This is generalized above to letting the difference be a an arbitrary constant, to see the family of related graphs.

D: Hyperbolas (difference in distances to two points is constant):

[ May 27, 2006: Message edited by: Jim Yingst ]
 
Stefan Wagner
Ranch Hand
Posts: 1923
Scala Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ah! Now I understand the question
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Great job, Jim!

I must admit that I didn't have all the answers worked out when I posed the question. When the hyperbola came out with big black areas at the corners, I was a bit surprised. (But once I saw it, it was obviously correct.)

Drawing the parabola when the line is neither horizontal nor vertical is tad tricky. I have a pencil drawing of one and can digitize it (either scan or draw) if there is enough interest.
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yeah, I woulnd't mind seeing that. I forgot consider the issue with parabolas and skew lines. Figuring out the other cases took too much out of me. Good puzzle, thanks for the fun.
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Jim Yingst:
Yeah, I woulnd't mind seeing that. I forgot consider the issue with parabolas and skew lines. Figuring out the other cases took too much out of me. Good puzzle, thanks for the fun.



Preliminary: The distance from a point to a line is either the horizontal or vertical distance whichever is shorter. Distance from (0, 2) to y=.5x is 2.

Initial case: The line is closer to horizontal than vertical. i.e. |slope| < 1
Start with Focus point F and line L. The midpoint of the vertical line between F and L (labelled A) is one point on the parabola. Draw lines at 45 degrees from the vertical, starting at F until they intercept L. Label those points B and C. draw vertical lines at B and C. Draw a horizontal line from F. where those lines cross are point D and E. The parabola is made up of segments DA and AE and the vertical rays from D and E that don't cross L.



This picture can be mirrored vertically or horizontally for the cases where the slope of L is > or < 0 and point F is above or below L.

If the line has |slope| > 1, then the picture above is rotated 90 degrees (and then mirrored).

Last case: If |slope| == 1
Draw horizontal and vertical lines through F. The midpoints between F and L on those lines are A and B, respectively. The parabola is segment AB plus the vertical ray from A and the horizontal ray from B that don't cross L.



Oy!
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic