Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I have a single point featureclass that represents the left and right sides of a landform (the points are coded as either 'right' or 'left'). Visually I can pick out and digitize two lines along these points, however, I need to do this automatically using ArcObjects or calls to geoprocessing functions in Arc10.

The figure below shows the two separate lines that I want to automatically select (in red).

Polyline selection from points

It is not as easy as selecting by attribute (e.g. 'right') and using Point to Polyline since there is no guarantee that these points are collected in order - the output polylines often jump all over the place.

Using a bounding polygon (see figure again) I have attempted to: 1) Split the polygon into lines at its vertices. 2) Select by attribute on the points (e.g. 'right). 3) Select by location on the polylines where they intersect the selected points.

The issue with this is I end up with extra lines selected as the points at the top of each desired line intersect with the "top" and "bottom" lines of my polygon.

Am I overthinking this? I just need to select the two longest 'sides' of the irregular polygon. Eventually I need to batch process this task on many point featureclasses, so they may not be as clear-cut/spaced as the above example.

EDIT: My desired output is a polyline featureclass containing the two separate polylines coded as right and left, respectively.

share|improve this question
    
For the points on a particular side would it be safe to assume that the correct order of the points is the one that minimizes the total length of the polyline? –  Kirk Kuykendall Jul 6 '11 at 0:17
    
Thinking about this on the spot, yes, I think that is a fair assumption. –  Radar Jul 6 '11 at 0:21
    
What if you started with an arbitrary point for a side, then found the next closest point (that hasn't been visited yet) and built up a collection. Then with the resulting collection break it into two parts if it has a long segment and rejoin the parts? –  Kirk Kuykendall Jul 6 '11 at 0:24
    
I attempted this solution, but there are instances where the line will intersect itself. If you look at the figure from @Hornbydd, you'll see a case where it's possible the line will cross over itself given nearer points at the concavity. –  Radar Jul 6 '11 at 21:12
1  
Do you have any information other than the point feature class? If not, then the problem is impossible. As an example, take Hornbydd's example drawing. Take the black line out of the picture, and start visualizing how many reasonable paths you can take through the seven points near the concavity. You can easily come up with several hundred (maybe even over a thousand) different paths that do not self-intersect. Without some level of ordering information on the points, you cannot draw the polylines. If you do have the bounding polygons, then blah238 has hit on the right solution. –  blord-castillo Jul 7 '11 at 15:52
show 4 more comments

4 Answers

up vote 4 down vote accepted

Not to be meant as a serious complete answer, but rather just an idea to toss around - I wonder if Thiessen polygons could perhaps be of any use in this case.

Points broken down into Thiessen polygons

Now, the trick is to find a reliable algorithm to identify those polygon boundary segments which form the centerline. Once you have the centerline, it is easy to decide on which side a point lies. Any ideas?

As a side note: I know this should be a comment, not an answer, but since you cannot post uploaded images in comments, I figured I'd dare to make an exception.

share|improve this answer
1  
This is an interesting idea, but it doesn't work in all cases. If there is a large gap between points on one side the centerline breaks. The funny thing is, I would eventually like to derive the centerline from the output polylines using a custom Thiessen polygon method. –  Radar Jul 6 '11 at 19:11
    
An alternate way of creating centrelines (that need a bit of cleaning up at their ends) is to turn the polygon into a raster, then use the Thin tool and convert the resulting raster to vector again. You could easily build a ArcToolBox model to string that logic together but this assumes you have Spatial Analyst. –  Hornbydd Jul 7 '11 at 9:20
    
+1 cool graphic. I wonder if you selected only those points where lines that intersect at an angle greater than some threshold you'd get just the nodes that fall on the centerline, then trace along those nodes to get a complete polyline that includes intermediate ones you may have missed. –  Kirk Kuykendall Jul 7 '11 at 14:48
1  
Just an update - I ended up using a Thiessen approach. I basically created Theissen polygons, broke them into lines, selected only those lines which had both a 'right' and 'left' attribute (derived from the input points) and then connected those lines. –  Radar Oct 3 '11 at 21:19
add comment

(Converting my comment to an answer)

If you already have bounding polygons created for all of your landform features, the vertices of those polygons should already be ordered consistently, assuming they are topologically valid. If so, you should be able to solve this using GP tools:

  1. Use Feature Vertices to Points to convert the polygons' vertices to points. The FID is the index of each vertex, although if you have multipart polygons the tool does not appear to account for that by creating a part index attribute, but it DOES keep both the coincident start and end points for polygon parts so you could use some trickery to attribute the parts using that fact. But in your case since you are just looking for the outer ring anyways this should not be a problem. Otherwise you could use some Python to iterate through the parts and vertices and create the points and attributes yourself.

  2. Perform a Spatial Join between the resulting points and your original points in order to pick up your left/right attribute at which point you should be able to use Points to Line successfully.

share|improve this answer
    
This is an excellent answer and you really shed some light on this problem. I am however having an issue. Spatial Join is running, but producing an empty point featureclass when I attempt to join the original points (with the 'right/'left' attributes) to the new featureclass (with the correct point order). Any idea why this would not work? I tested it in reverse and all the fields join, but this output obviously doesn't help. –  Radar Jul 7 '11 at 22:06
    
No idea why it works one way but not the other, that doesn't compute to me. But as with any spatial overlay analysis I would check that they have the same coordinate systems, and that the coordinates between the points in one feature class are exactly the same as the other (if not, either either apply an XY tolerance in the environment settings or add a small search radius value to make up for very small coordinate discrepancies). –  blah238 Jul 7 '11 at 23:58
add comment

I was trying to think up a solution to this interesting problem but I could only generate more problems! I think there is a scenario that must be considered when stringing the points together to form a polyline and these are spikes as shown in the image below.

Spike in path

If this is a sceanrio that never exists then my thought process was:

  1. Select points that code up as RIGHT
  2. Get the extent of the selection
  3. You will have 2 points that intersect the extent boundary, choose one (this is starting point).
  4. create a dictionary and for all points add them to the dictionary where the key is the distance from the the starting point and item is the point ID.
  5. Sort dictionary by key then write the key order back to your FeatureClass as a new sort order field.
  6. Sort order field is what you use in your point to polyline tool.
  7. Repeat process for all points coded as LEFT.

This logic assumes all points are unique identifed and there are no "stacked points". But this logic fails if you get the above scenario... :(

share|improve this answer
add comment

If you have the bounding polygon over the points how about you build a topology graph with the polygon and the points. You can then walk the topological edges, get the parents (which will get you the two points on either end of the edge), and work out if the point polarity attribute is the same. If they are then use that edge geometry to start making a line along that side.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.