I want to learn about sweep-line algorithms, and the first sentence on Wikipedia says, "In computational geometry, a sweep line algorithm or plane sweep algorithm is an algorithmic paradigm that uses a conceptual sweep line or sweep surface to solve various problems in Euclidean space."

I don't really understand the Wikipedia page on Euclidean space. Could someone please explain what Euclidean space is to me in layman's terms?

" In one dimension, this is the real line; in two dimensions, it is the Cartesian plane; and in higher dimensions it is a coordinate space with three or more real number coordinates. "

Pretty much your standard 2D or 3D coordinate system. Instead, you might want to look into non-Euclidean to see what it is not.

First take *Cartesian space*, that is a coordinate space formed by taking pairs or tuples of real numbers as the coordinates, e.g. [1.0, 2.0] would be a point in 2D Cartesian space. (It's called "Cartesian" because it's formed by taking the *Cartesian product* of real lines). Then add to that a specific *distance function* called the "Euclidean metric" and you have yourself a *Euclidean space*. The Euclidean metric mostly corresponds to the usual notion of shortest straight-line distance between points. Other metrics are "taxicab metric" (imagine measuring walking distance in a city, you can't travel in a straight line through buildings, you have to stick to streets as they are layed out in a grid), or the discrete metric (distance to all other points is 1, otherwise the distance of a point to itself is 0). Don't ask me about Hyperbolic or Elliptic spaces, I think the metric requirements are similar but the underlying geometry is obviously different ?

Thanks, both of you! I appreciate it.

An unrelated tip: when you find a complicated Wikipedia article, sometimes it's worth checking the Simple English Wikipedia for the same article. The quantity and quality of articles varies, but it helps sometimes.

In this case, https://simple.wikipedia.org/wiki/Euclidean_space is very short. But with the help of some other links in that article it explains the concept.

A Euclidean space is one that behaves like the ones you know and love.

Ifyou put a right angle triangle ANYWHERE and at any orientation in Euclidean space then the square of the length of the longest side will be equal to the sum of the square of the length of the other two sides.

The sum of the interior angles in a triangle will always be 180. Parallel lines will never touch. Familiar trigonometric functions will correctly produce the results you expect when you apply them to geometric problems. And so on.

In a non-Euclidean space one or more of these things will behave differently.

11 hours ago, 1024 said:

An unrelated tip: when you find a complicated Wikipedia article, sometimes it's worth checking the Simple English Wikipedia for the same article. The quantity and quality of articles varies, but it helps sometimes.

I didn't know that existed. Thanks!

The collection of points described with n real coordinates is called R^n. R^n is a vector space, meaning you can add and subtract elements of R^n ("vectors"), and you can scale them (multiply each coordinate by the scaling factor).

R^n can also be given the structure of an affine space, meaning you can add a vector to a point to get another point, and you can subtract points to get the vector between them. This might look very similar to the vector-space structure of R^n, but notice that in affine space there is no special point designated as the origin, you can't scale a point, you can't add two points... (but you can compute a weighted average of points).

Notice that in affine space we haven't defined a notion of distance or angle. If you define the distance the usual way, you have Euclidean space.

Another useful structure for game programming is projective space. When you see people using 4 coordinates for 3-dimensional space, that's a sign that projective geometry is being used.

2 hours ago, alvaro said:

The collection of points described with n real coordinates is called R^n. R^n is a vector space, meaning you can add and subtract elements of R^n ("vectors"), and you can scale them (multiply each coordinate by the scaling factor).

R^n can also be given the structure of an affine space, meaning you can add a vector to a point to get another point, and you can subtract points to get the vector between them. This might look very similar to the vector-space structure of R^n, but notice that in affine space there is no special point designated as the origin, you can't scale a point, you can't add two points... (but you can compute a weighted average of points).

Notice that in affine space we haven't defined a notion of distance or angle. If you define the distance the usual way, you have Euclidean space.

Another useful structure for game programming is projective space. When you see people using 4 coordinates for 3-dimensional space, that's a sign that projective geometry is being used.

You should add some LaTeX in there to make it even more daunting.

Yeah, that can sound intimidating. I just wanted to briefly describe the way we think about this in math. There are enough terms there to look up the details elsewhere. But the best place to learn these things is probably college.