Algorithms

Robo Home | Changes | Preferences | AllPages

Difference (from prior major revision) (minor diff)

Changed: 1c1,22

This just seems like a logical page for the wiki to have. Not everything you can do is covered in Java API. It also gives me a place to ask if anyone knows, given a plot of points and a polygon, an efficient method of finding where to place the polygon to encompass the maximum number of points? -- Kuuran

This just seems like a logical page for the wiki to have. Not everything you can do is covered in Java API. Also, when things are it's useful to know which method to pick for your problem. It also gives me a place to ask stuff :P. -- Kuuran

Algorithm Questions

1) Given a plot of points and a polygon, an efficient method of finding where to place the polygon to encompass the maximum number of points?

Useful Algorithms

1) I've found this useful for making useless melee movements: Convex Hull. It's well described, but basically as follows:

Given a set of points:

1) Select the leftmost point
2) Sort remaining points by bearing (counter-clockwise) to leftmost point
3) Add these three points to the polygon
4) For every point after 3:
1) Calculate the angle between the second last point in the polygon, the last point in the polygon and this point
2) Remove the last point from the polygon until the angles makes only "left" turns
3) Add the point to the polygon

The resulting polygon is the smallest convex polygon that includes all the points given.

This just seems like a logical page for the wiki to have. Not everything you can do is covered in Java API. Also, when things are it's useful to know which method to pick for your problem. It also gives me a place to ask stuff :P. -- Kuuran

Algorithm Questions

1) Given a plot of points and a polygon, an efficient method of finding where to place the polygon to encompass the maximum number of points?

Useful Algorithms

1) I've found this useful for making useless melee movements: Convex Hull. It's well described, but basically as follows:

Given a set of points:

  1) Select the leftmost point
  2) Sort remaining points by bearing (counter-clockwise) to leftmost point
  3) Add these three points to the polygon
  4) For every point after 3:
      1) Calculate the angle between the second last point in the polygon, the last point in the polygon and this point
      2) Remove the last point from the polygon until the angles makes only "left" turns
      3) Add the point to the polygon

The resulting polygon is the smallest convex polygon that includes all the points given.