Outline group of points

Dear All,

I have a group of points, and I want to enclose them with a polygon,
vertices if which are at points from the group. However, the polygon
may be concave - I DON'T want the convex hull (I already have
algorithms for that), I want a polygon that follows the outline of the
group of points.

Now, I can imagine ways of doing this within packages such as ARC/INFO
or ERDAS Imagine (and doubtless there are similar methods in other
packages).

But, I want a stand-alone algorithm that I can implement in Java
(existing Java code would be handy!) I can visualize ways of doing it
with a triangulation, but I really don't want the overhead of carrying
out a trangulation - this is for a display algorithm that is called
frequently, so I want something quick. A modified version of the Gift
Wrap algorithm seems possible, but I can't see how to modify it.

Any suggestions?

Paul

Hi Paul,

What you are looking for is a "simple closed path" (I won't comment on the
"simple" here {;-) ) It forms a non-intersecting polygon from a collection
of points. It works as follows:

* Pick any point to function as your anchor.
* Compute the angle made at the anchor between another point and the
positive horizontal (+infinite x). Repeat for all points.
* Sort by angle.
* Draw the polygon.

As Willem indicated, you may not like your results. If the points
more-or-less represent a non-convex hull you should be ok, but if they are
distributed randomly you will get a porcupine polygon. In that case you
should add another processing step whereby you exclude points from the
polygon that have a very sharp angle *on the outside* of the polygon. In
this case you should also make sure that your anchor is on the outside of
the collection of points (i.e. extreme x or y coordinate).

The "compute the angle" part is easy enough to solve with standard
trigonometry, but also slow. Sedgewick, in his unsurpassed "Algorithms in C"
(should I add an Amazon link here?), comes up with this rather elegant
solution (with some edits on my part), which does not give the angle but it
does have the same sorting properties as angles:

float theta(struct point p, struct point anchor) {
float dx, dy, absxy;
float t;
dx = p.x - anchor.x;
dy = p.y - anchor.y;
absxy = abs(dx) + abs(dy);
t = (absxy == 0.0) ? 0.0 : dy / absxy;
if (dx < 0.0)
t = 2.0 - t;
else if (dy < 0.0)
t = t + 4.0;
return t;
}

HA HA HA HA HA HA!!!

Cheers,
Patrick

wrote:

I didn't say it was a GOOD solution! There is one I have used that
works, though - create a TIN, then eliminate outside triangles
according a suitable rule. It works, but it is something of a
heavyweight solution!

Paul

wrote:

That sounds like the sort of approach I needed. Perhaps I ought to
explain that I need something quick because this is going to be
implemented in a display routine, so it needs to be as light weight as
I can get. I think this has potential - I hadn't thought of creating
the maximally complex polygon and simplifying it! Your suggestion
about removing points with a sharp angle is where the extra bit of
information comes in - I will have to find a suitable value of angle
to use as a cut off - probably 60 degrees or so, if I don't want
things to be too concave.

Thanks

Paul

Hi Paul,

If you say that you need speed I presume it is because the set of points to
display changes. Of course you have to do the calculations only when the set
of points changes and you may be able to exploit that if the changes are not
very often. Consider this approach to weed the interior points:

* Sum the x-coordinates of all points, keep the sum
* Sum the y-coordinates of all points, keep the sum
* Establish the geometric center of the points as P(sumx, sumy)
* Calculate the distance from each point to the geometric center
* Sum the distances, calculate the average
* Discard all points that too close to the center, for instance D(p) <
D(avg) * 0.8
* Compute the polygon of the remaining points

Like this you do not have to expend a lot of computer time on creating the
polygon (which is relatively slow due to the sorting) and then simplifying
it (which again is costly because you have to rearrange the polygon
structure).

If a point is dropped, subtract its coordinates from the sums and
recalculate the set of valid points. If a points is added, add the
coordinates to the sums and recalculate. You may have to use a more robust
estimator to lessen the effect of outliers, if any, but these tend to be
more costly in computational terms.

For real speed, first calculate where the points go in pixel (screen) space,
then do all the calculations in integer precision.

Cheers,
Patrick