StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>A very interesting question. Here is my solution, that allows for variable resolution. Although, fine-tuning it may not be simple, as it's mostly intended to narrow down </p> <p>Every k points, calculate the convex hull and store it as a set. Go through the at most k points and remove any points that are not in the convex hull, in such a way that the points don't lose their original order.</p> <p>The purpose here is that the convex hull will act as a filter, removing all of "unimportant points" leaving only the extreme points. Of course, if the k-value is too high, you'll end up with something too close to the actual convex hull, instead of what you actually want.</p> <p>This should start with a small k, at least 4, then increase it until you get what you seek. You should also probably only include the middle point for every 3 points where the angle is below a certain amount, d. This would ensure that all of the turns are at least d degrees (not implemented in code below). However, this should probably be done incrementally to avoid loss of information, same as increasing the k-value. Another possible improvement would be to actually re-run with points that were removed, and and only remove points that were not in both convex hulls, though this requires a higher minimum k-value of at least 8.</p> <p>The following code seems to work fairly well, but could still use improvements for efficiency and noise removal. It's also rather inelegant in determining when it should stop, thus the code really only works (as it stands) from around k=4 to k=14. </p> <pre><code>def convex_filter(points,k): new_points = [] for pts in (points[i:i + k] for i in xrange(0, len(points), k)): hull = set(convex_hull(pts)) for point in pts: if point in hull: new_points.append(point) return new_points # How the points are obtained is a minor point, but they need to be in the right order. x_coords = [float(x) for x in x.split()] y_coords = [float(y) for y in y.split()] points = zip(x_coords,y_coords) k = 10 prev_length = 0 new_points = points # Filter using the convex hull until no more points are removed while len(new_points) != prev_length: prev_length = len(new_points) new_points = convex_filter(new_points,k) </code></pre> <p>Here is a screen shot of the above code with k=14. The 61 red dots are the ones that remain after the filter.</p> <p><img src="https://i.stack.imgur.com/yHmHD.jpg" alt="Convex Filter Example"></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload