Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Polygon Definition and Surveyor Formula Results #80

Closed
fosskers opened this issue Jun 13, 2016 · 1 comment
Closed

Polygon Definition and Surveyor Formula Results #80

fosskers opened this issue Jun 13, 2016 · 1 comment
Labels

Comments

@fosskers
Copy link

fosskers commented Jun 13, 2016

Hi there. In implementing a vector tile codec, I stumbled upon the following "gotcha". The definition of polygon interior rings states (as of spec version 2.1):

An interior ring is DEFINED as a linear ring having a negative area as calculated by applying the surveyor's formula to the vertices of the polygon in tile coordinates. In the tile coordinate system (with the Y axis positive down and X axis positive to the right) this makes the interior ring's winding order appear counterclockwise.

While the surveyor's formula seems to always return a positive value, due to the absolute value.

Question: Does the spec imply we should ignore the absolute value?

As a toy example, consider the following triangle:

(2,2) -> (5,4) -> (2,6)

These are tile coordinates, not the deltas as used in the encoding. Assuming these are clockwise coordinates (they are), we expect a positive area. Sure enough, the surveyor's formula tells us the area is 6, regardless of the application of the absolute value.

Taken counter-clockwise, we have:

(2,2) -> (2,6) -> (5,4)

And the formula gives an area of -6, but only if we ignore the absolute value. A ha! Must be an interior polygon.

To clarify further, when one is decoding polygon geometries, can we not ignore the idea of "winding order" entirely and instead follow these steps:

  1. Discover a MoveTo. Must be a new polygon.
  2. Collect its point deltas (constructing the actual points if needed)
  3. Find its area as given by the surveyor's formula. Consider the points in the exact order they were given and ignore the absolute value.
    • If positive, we have a new exterior ring.
    • If negative, we have an interior ring of the last exterior ring
  4. Repeat

Is my interpretation correct? If so, can the polygon definition be altered to be clearer regarding the results of the surveyor's formula?

@flippmoke
Copy link
Member

@fosskers yes, you ignore the absolute value, that is a good catch. Your steps look correct to me that you listed. A good place to look is the implementation in mapnik-vector-tile.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

2 participants