Hilbert Sort - Revision history

Admin: /* einer Linie auf ein Flächenstück */

2017-06-27T22:16:14Z

einer Linie auf ein Flächenstück

← Older revision		Revision as of 22:16, 27 June 2017
Line 134:		Line 134:

	[[Image:HilbertCurveOrig.png\|500px]]		[[Image:HilbertCurveOrig.png\|500px]]

			[[Image:HilbertCurveOrig2.png\|500px]]

	{{Quote\|		{{Quote\|

Admin: /* Examples */

2017-06-27T22:13:28Z

Examples

← Older revision		Revision as of 22:13, 27 June 2017
Line 233:		Line 233:
	[[Image:HilbertSortRotation.jpg\|500px]]		[[Image:HilbertSortRotation.jpg\|500px]]

	[[Image:HilbertSortRotation3.jpg\|~~500px~~]]		[[Image:HilbertSortRotation3.jpg\|800px]]

	==Flags==		==Flags==

Admin: /* Examples */

2017-06-27T22:10:58Z

Examples

← Older revision		Revision as of 22:10, 27 June 2017
Line 232:		Line 232:

	[[Image:HilbertSortRotation.jpg\|500px]]		[[Image:HilbertSortRotation.jpg\|500px]]

	~~[[Image:HilbertSortRotation2.jpg\|500px]]~~

	[[Image:HilbertSortRotation3.jpg\|500px]]		[[Image:HilbertSortRotation3.jpg\|500px]]

Admin: /* Examples */

2017-06-27T22:10:51Z

Examples

← Older revision		Revision as of 22:10, 27 June 2017
Line 232:		Line 232:

	[[Image:HilbertSortRotation.jpg\|500px]]		[[Image:HilbertSortRotation.jpg\|500px]]

			[[Image:HilbertSortRotation2.jpg\|500px]]

			[[Image:HilbertSortRotation3.jpg\|500px]]

	==Flags==		==Flags==

Admin: /* Solution Approach */

2017-06-27T08:33:10Z

Solution Approach

← Older revision		Revision as of 08:33, 27 June 2017
Line 154:		Line 154:
	A few keys to successfully solving the Hilbert Curve problem:		A few keys to successfully solving the Hilbert Curve problem:
	* The motive for the Hilbert Curve is that data is grouped by how close it is spatially; if a point is in the lower left quadrant, it will always be visited before another point in the upper right quadrant. This means that ''all'' points in the lower left quadrant will always be visited before ''all'' points in the upper right quadrant.		* The motive for the Hilbert Curve is that data is grouped by how close it is spatially; if a point is in the lower left quadrant, it will always be visited before another point in the upper right quadrant. This means that ''all'' points in the lower left quadrant will always be visited before ''all'' points in the upper right quadrant.
	* The rotation is the tricky part of the problem, mainly because when we rotate the curve, we use the rotated version of the curve as the starting point for any additional calls in that quadrant. So, the ~~rotations~~ have to recurse with us.		* The rotation is the tricky part of the problem, mainly because when we rotate the curve, we use the rotated version of the curve as the starting point for any additional calls in that quadrant. So, the reflections have to recurse with us.
	* The curves are not simply rotated 90 degrees, the curves are actually flipped and rotated about a diagonal axis (going from one corner to another). This affects subsequent rotations.		* The curves are not simply rotated 90 degrees, the curves are actually reflected - flipped and rotated about a diagonal axis (going from one corner to another). This affects subsequent rotations.

	==Implementation Strategy==		==Implementation Strategy==

Admin: /* TOC1 */

2017-06-27T08:32:51Z

TOC1

← Older revision		Revision as of 08:32, 27 June 2017
Line 19:		Line 19:
	** Two problems		** Two problems
	*** First problem, dividing up space and keeping track of coordinates, is going to get messy		*** First problem, dividing up space and keeping track of coordinates, is going to get messy
	*** Second problem, trying to keep track of ~~rotations~~ across multiple levels of recursion is going to get complicated		*** Second problem, trying to keep track of rotation/reflection across multiple levels of recursion is going to get complicated
	** Two solutions		** Two solutions
	*** First solution, who cares about (x,y), all they really care about is which one the curve visits first. So, if you shift (x,y) in a way that does not change the order in which the (x,y) points are visited by a Hilbert curve, then you're perfectly fine.		*** First solution, who cares about (x,y), all they really care about is which one the curve visits first. So, if you shift (x,y) in a way that does not change the order in which the (x,y) points are visited by a Hilbert curve, then you're perfectly fine.
	*** Second solution, if you're allowed to change (x,y) coordinates and rescale, you can also apply the ~~rotations~~ on the fly on the data in this quadrant, before passing them on to the next level of recursion. None of the levels need to know about any other levels.		*** Second solution, if you're allowed to change (x,y) coordinates and rescale, you can also apply the reflections on the fly on the data in this quadrant, before passing them on to the next level of recursion. None of the levels need to know about any other levels.
	** Summary - apply the first -> second recursion step to your square/quadrant. Then apply a rotation/transformation to each of the four resulting squares so that each one is re-oriented (back to "normal" position - such the the curve travels from southwest to northwest to northeast to southeast). Keep them in order in-place. Repeatedly apply this procedure.		** Summary - apply the first -> second recursion step to your square/quadrant. Then apply a rotation/transformation to each of the four resulting squares so that each one is re-oriented (back to "normal" position - such the the curve travels from southwest to northwest to northeast to southeast). Keep them in order in-place. Repeatedly apply this procedure.


	=TOC2=		=TOC2=

Admin: /* Examples */

2017-06-27T08:31:26Z

Examples

← Older revision		Revision as of 08:31, 27 June 2017
Line 232:		Line 232:
	==Examples==		==Examples==

	[[Image:HilbertSortRotation.~~png~~\|500px]]		[[Image:HilbertSortRotation.jpg\|500px]]

	==Flags==		==Flags==

Admin: /* Examples */

2017-06-27T08:28:30Z

Examples

← Older revision		Revision as of 08:28, 27 June 2017
Line 232:		Line 232:
	==Examples==		==Examples==

			[[Image:HilbertSortRotation.png\|500px]]

			==Flags==

			{{CSFlag}}

			[[Category:Sorting]]

	[[Category:CS]]		[[Category:CS]]

Admin: /* Bookkeeping */

2017-06-27T08:12:28Z

Bookkeeping

← Older revision		Revision as of 08:12, 27 June 2017
Line 227:		Line 227:
	would visit them is preserved as the order in which the (now transformed back to its original shape)		would visit them is preserved as the order in which the (now transformed back to its original shape)
	Hilbert curve would visit them.		Hilbert curve would visit them.



			==Examples==

Admin: /* TOC2 */

2017-06-23T16:45:57Z

TOC2

@@ Line 42: / Line 42: @@
 ** Solution Code
 * References
 =Background=

← Older revision		Revision as of 22:16, 27 June 2017
Line 134:		Line 134:

	[[Image:HilbertCurveOrig.png\|500px]]		[[Image:HilbertCurveOrig.png\|500px]]

			[[Image:HilbertCurveOrig2.png\|500px]]

	{{Quote\|		{{Quote\|

← Older revision		Revision as of 22:10, 27 June 2017
Line 232:		Line 232:

	[[Image:HilbertSortRotation.jpg\|500px]]		[[Image:HilbertSortRotation.jpg\|500px]]

	~~[[Image:HilbertSortRotation2.jpg\|500px]]~~

	[[Image:HilbertSortRotation3.jpg\|500px]]		[[Image:HilbertSortRotation3.jpg\|500px]]