Reordering polygon vertices - FME Talk

Message from discussion Reordering polygon vertices

avtmd

More options Apr 28, 4:04 am

From: avtmd <w...@avt.at>

Date: Mon, 28 Apr 2008 01:04:01 -0700 (PDT)

Local: Mon, Apr 28 2008 4:04 am

Subject: Re: Reordering polygon vertices

  Reply to author
  |
  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

Wow, that's been a great weekend discussion!
May I dare to add another idea?

1) The corner problem: I have posted a way to find a polygon's
"corner" in coordinate system representation earlier, see
http://groups.google.com/group/fmetalk/browse_thread/thread/c172d5e96...
(I hope I got the link right, the message was "Extract NE cornder of
polygon", "3 Jan. 2007 by Hans van der Maarel", but you don't need to
follow it, I'll explain it here too).
The basic idea is to rotate the polygon by 45 degrees, so you can
easily find all the points that are closest to a 45 degree axis ...
which is a good representation of the corner point even for a general
polygon. The closest points are simply obtained as min / max
operations. Of course, the rotation is not really done with the data,
it is simply accomplished by an addition or subtraction of a point's
coordinates, in your case:
The SW corner is simply the point with minimal x(i)+y(i), where i is
the index of all points of that polygon.

2) The rotation problem:
You have to find out the point index of the (new) first point. Then
you can reorder the points by a modulo operation on the point indices.

This approach will work for any polygons, not only squares.
Implementation can be done in several ways. The easiest would
certainly be to do it within a TCL or python script: Extract all
coordinates of the polygon except the last one (this would be present
twice) into an array. Calculate x(i)+y(i) and find the minimum of
these values. Then you have the list index of the first (at the same
time last) point. Now run a loop for all list indices starting from
that index with modulo by the number of points, running till that
index is reached again. Or you do two loops, one from i to the number
of points -1, the other one from 0 to i.

With transformers you would have to do a lot more operations, of
course.

Maybe that helps,

Wolfgang

On 27 Apr., 01:14, kimo <k...@ollivier.co.nz> wrote:

> I got the idea from an example previously seen in the Python Cookbook
> for computing convex hulls. It discusses finding the lowest point and
> sorting into clockwise order using Graham's Scan Algorithm. I had
> initially thought of calling a Python script using this code, or using
> the logic in a list handler, but it was quite complicated for an
> apparently simple problem, and not really in the spirit of using
> transformers and FME. I am sure that list handling is robust, but
> this problem puts a lot of skill back on the scripter to implement
> properly. This algorithm would be able cope with the general case to
> answer the original question completely.
> Routine from Python Cookbook Ed 2 chapter 18.17 p 686. Actually it's
> not Graham's Scan (1972) at all
> It is really Andrew's Monotone Chain Algorithm (1979), but never mind,
> I tested it and it worked after debugging.http://en.wikipedia.org/wiki/Graham_scanfor a graphical explanation

> I understand how an expert can do "anything" once you have a list of
> coordinates, but I consider if I have to get down to that detail as a
> 'spatial language failure' either because I have not been able to
> express the problem in terms of the 'spatial language' available in
> FME or there is not yet a 'verb' (transformer) to handle the concept.
> It's Dale's team's job to implement Graham's Algorithm. I want
> spatial feature manipulation to become more SQL-like where you specify
> the result without having to code the implementation. That is what I
> find fascinating about transformers and topology.

> On Apr 27, 6:53 am, "Jason Birch" <Jason.Bi...@nanaimo.ca> wrote:

> > That's a good solution.

> > I was working under the assumption that the sctweedy's "so far" meant that I couldn't count on the polygons remaining as simple squares.

> > I wouldn't have come up with anything as elegant as your solution even if I had accepted these constraints though; use of the ConvexHullReplacer was a great call.

> > I'd agree with full-feature processing being faster, but I've found lists to be entirely reliable and one of the parts of FME that I like most.

> > The only way that I know of to "attach" to Google Groups is to use the email interface instead of the web interface.

> > Jason

> > ________________________________

> > From: kimo
> > Subject: [fme] Re: Reordering polygon vertices

> > Too much detail! Much too hard. Surely with all the power in the
> > transformers you don't have to bit twiddle?

> > winmail.dat
> > 5K

> Dow
> nlod- Zitierten Text ausblenden -

> - Zitierten Text anzeigen -

Reply to author Forward