Geometry script / General Science and Electronics / Forums

Forums

4hv.org :: Forums :: General Science and Electronics

« Previous topic | Next topic »

Geometry script

1 2 next

Move Thread

LAN_403

AndrewM

Wed Mar 14 2012, 04:33PM

Registered Member #49 Joined: Thu Feb 09 2006, 04:05AM
Location: Bigass Pile of Penguins
Posts: 362

Here's a puzzle for you from a project I'm working on.

Given a list of vertexes defining a closed polygon in 2-space, how do you analytically determine the direction of the outward facing surface normal at each vertex? The normal is an angular bisector of the two sides leading the vertex, obviously, but determining the sign of the outward vs. inward normal is not obvious.

Assume a general case, like that the origin is not necessarily at the center of the enclosed volume, the polygon may have complex curvature, etc.

I need an analytic solution, i.e. not something like "plot it and then check points to see if they're interior."

Pinky's Brain

Wed Mar 14 2012, 05:39PM

Registered Member #2901 Joined: Thu Jun 03 2010, 01:25PM
Location:
Posts: 837

You can walk the edges to see if it winds clock wise or anti-clock wise (you sum all the angles of following edges, if the sum is +180 it's counter clock wise, if it's -180 it's clock wise). If you know the direction of winding you know which side is the interior.

Now of course that's algorithmic, not analytical ... you have to divide the angle by 180 and use it to sign the normal to get an analytical solution :p

AndrewM

Wed Mar 14 2012, 06:03PM

Registered Member #49 Joined: Thu Feb 09 2006, 04:05AM
Location: Bigass Pile of Penguins
Posts: 362

Pinky's Brain wrote ...

You can walk the edges to see if it winds clock wise or anti-clock wise (you sum all the angles of following edges, if the sum is +180 it's counter clock wise, if it's -180 it's clock wise). If you know the direction of winding you know which side is the interior.

Now of course that's algorithmic, not analytical ... you have to divide the angle by 180 and use it to sign the normal to get an analytical solution :p

Im trying to wrap my head around this one - I think it'd require me to have knowledge of which direction the vertex list is ordered in (which I do not).

Pinky's Brain

Wed Mar 14 2012, 07:26PM

Registered Member #2901 Joined: Thu Jun 03 2010, 01:25PM
Location:
Posts: 837

Instead of explaining it here is a better way to determine the winding of a concave polygon :

Again, once you know the winding you know which side of an edge the interior is and which way the normal should point.

Dr. Slack

Wed Mar 14 2012, 07:37PM

Registered Member #72 Joined: Thu Feb 09 2006, 08:29AM
Location: UK St. Albans
Posts: 1659

This method doesn't need the winding direction of the polygon.

The straight line through the vertex that bisects the angle between the two edges has two branches, one starts inside the polygon, the other starts outside.

Place a test point on one of the branches, very close to the vertex. "Very" means close enough that no other sides of the polygon intersect the line between the vertex and the test point. "Very" could mean the smallest floating point number above zero, anything bigger and you might have to check it.

From the test point, travel out to infinity, in any direction (infinity means to at least beyond the bounding hull of the polygon, ie until you know you are outside) counting how many of the polygon's sides you cross. If you cross an odd number of sides, your test point was inside. If you cross an even number of sides, including of course zero, it was outside. You can obviously simplify the intersection calculation problem if the infinity you head towards is along one of the axes, any side with both vertices on the same side of the line doesn't need to be tested further

This is an algorithm, giving you a programmatic method (rather than eyeball) to see whether a point is inside or outside the polygon. I'm not sure an "analytic" method exists for a "list of vertices". An analytic method may well exist for a curve described by formulae that can be differentiated etc.

AndrewM

Wed Mar 14 2012, 08:13PM

Registered Member #49 Joined: Thu Feb 09 2006, 04:05AM
Location: Bigass Pile of Penguins
Posts: 362

Dr. Slack wrote ...

This method doesn't need the winding direction of the polygon.

The straight line through the vertex that bisects the angle between the two edges has two branches, one starts inside the polygon, the other starts outside.

Place a test point on one of the branches, very close to the vertex. "Very" means close enough that no other sides of the polygon intersect the line between the vertex and the test point. "Very" could mean the smallest floating point number above zero, anything bigger and you might have to check it.

From the test point, travel out to infinity, in any direction (infinity means to at least beyond the bounding hull of the polygon, ie until you know you are outside) counting how many of the polygon's sides you cross. If you cross an odd number of sides, your test point was inside. If you cross an even number of sides, including of course zero, it was outside. You can obviously simplify the intersection calculation problem if the infinity you head towards is along one of the axes, any side with both vertices on the same side of the line doesn't need to be tested further

This is an algorithm, giving you a programmatic method (rather than eyeball) to see whether a point is inside or outside the polygon. I'm not sure an "analytic" method exists for a "list of vertices". An analytic method may well exist for a curve described by formulae that can be differentiated etc.

This is exactly the approach I'm trying to avoid. Such searches are computationally expensive, increasing with the square of the vertex count and the size of the control volume. This is not feasible.

Dr. Slack

Wed Mar 14 2012, 10:15PM

Registered Member #72 Joined: Thu Feb 09 2006, 08:29AM
Location: UK St. Albans
Posts: 1659

AndrewM wrote ...

... Such searches are computationally expensive, increasing with the square of the vertex count and the size of the control volume. This is not feasible.

How so? I make it linear in the vertex count. Number of operations is O(number of vertices)

intersections=0
for edge in edge_list:
    if intersects(edge, test_line):
        intersections += 1

Now the function intersects(a,b) takes only 4 points, the two vertices of the edge being tested, and the two ends of the test line (which are constant during the search). I'll leave it as an exercise for the reader to figure out how few operations are needed to see whether two lines interesct, and it ain't many. As I said above, the test on many of the edges can be short circuited by, if the test line runs parallel with the x axis at a height of Y, if (v[0].y-Y) has the same sign as (v[1].y-Y) where v[] are the coordinates of the two vertices of the edge, then the edge cannot intersect the test line. Half of the remaining candidates can be dispatched with a simpler test, more than half if we choose to head to infinity AWAY from the mean position of the polygon vertices.

I will modify the algorithm of my previous post very slightly for simplicity and clarity, and add an important gotcha test

a) from the vertex in question, draw a test line to infinity that is not co-incident with either of the edges
b) count the number of polygon edges that intersect this line
c) if even, the test line leaves the vertex in the outside angle, if odd, it leaves to the inside
gotcha) AS LONG AS the test line does not exactly interesect any vertices of the polygon. If it does, the intersects edges count will be ambiguous, and you must choose a different direction for the test line

AndrewM

Wed Mar 14 2012, 10:27PM

Registered Member #49 Joined: Thu Feb 09 2006, 04:05AM
Location: Bigass Pile of Penguins
Posts: 362

Yes, I see - I didn't grasp that only one vertex needed to be test, I was imagining the test should be repeated for every vertex.

I like it, thx.

Dr. Slack

Thu Mar 15 2012, 09:00AM

Registered Member #72 Joined: Thu Feb 09 2006, 08:29AM
Location: UK St. Albans
Posts: 1659

I had assumed that you wanted a test that could be run from any arbitrary vertex, without keeping track of winding, hence all the hoo-haa about how many edges get crossed. So if used like that repeatedly, it would indeed be O(N^2) for the entire polygon. However, your answer implies that knowing one is sufficient, so you anticipate keeping track of the winding.

Given this, there is a trivial reduction of that algorithm down to one line, if you are allowed to pick a particular vertex, and wind from there.

Pick the vertex with the largest x coordindate, or any one of them if several have the same max x. By definition, there will be no more vertices, so no more edges, between that one and +x infinity. So zero edges will be crossed, and the +x direction from that vertex is outside.

I assume that either your polygon does not self-intersect by construction, or that you run a test to ensure that no two of its edges intersect. That test would be O(N^2) for the polygon.

AndrewM

Thu Mar 15 2012, 03:00PM

Registered Member #49 Joined: Thu Feb 09 2006, 04:05AM
Location: Bigass Pile of Penguins
Posts: 362

The vertex list is ordered - that is, each segment is followed by its nearest neighbor - but there is no consistency as to whether the list proceeds clockwise or counterclockwise.

In truth I oversimplified the problem - the list is a list of faces, i.e. line segments, not merely vertexes. The difference is that the list may contain multiple, unconnected, bodies. Any two bodies will not intersect, nor will any one body intersect itself.

The approach you describe will still work well, however, provided that I am able to distinguish separate bodies and rerun the routine for each one. No biggie.

1 2 next

Moderator(s): Chris Russell, Noelle, Alex, Tesladownunder, Dave Marshall, Dave Billington, Bjørn, Steve Conner, Wolfram, Kizmo, Mads Barnkob