This week's book giveaway is in the Other Open Source APIs forum. We're giving away four copies of Storm Applied and have Sean Allen, Peter Pathirana & Matthew Jankowski on-line! See this thread for details.

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.

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.

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
Ranch Hand

Joined: Feb 18, 2005
Posts: 1030

4

posted

0

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?

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

Each number system has exactly 10 different digits.

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

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):

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
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

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
Ranch Hand

Joined: Feb 18, 2005
Posts: 1030

4

posted

0

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.