Program to connect points and merge colinear lines

I'm developing a program to connect a set of (x,y) points in a polygon so that the resulting cell array contains a list of line segments. Each row of this cell array contains two points, which describe the endpoints of each line segment of the polygon. Furthermore, if a line segment found to be connected to another line segment, a test is performed to determine if the lines are colinear. I've got this program nearly finished except for some errors in appending the cell array after testing positive for coplanar lines.

The code can be found here. https://www.dropbox.com/s/9489qfah2iu5ywn/connect.m

I've included comments within the code to help explain what I'm doing.

Answer 1

[Image Analyst]

Do you have a question? If not, if you think it will be useful generally to people, then you can upload to the File Exchange when you're done. I do have a question. How can a bunch of lines in the x-y plane NOT be coplanar? As far as I can tell, they're all coplanar.

[Harold]

I meant co-linear. I want to detect if any of the line segments are co-linear with any other line segments. If they are, I want to merge them at the common point; i.e get rid of the common point and keep the other two points. The question I had was if there was a better way to test for co-linearity of line segments than the way that I'm doing using a function call in arrayfun().

[Image Analyst]

Sorry, I didn't look at your code, but I know you'll need to be aware of this entry in the FAQ if you're going to be comparing real numbers for equality.

[Harold]

Yes, I've taken measures against this.

Update: I may have this close to being solved. I've approached it another way. I first run the loop I have for connecting the points. Then after, I run a while loop to merge line segments. I've tested it on one cell array, where all but the last row are co-linear. It works for this case but not if the co-linear line segments are not in sequential order in the cell array. Without getting into to much detail, I have to code a test to either grab the 1st point of line segment 1 and the 2nd point of line segment 2, or grab the 2nd point of line segment 1 and the 1st point of line segment 2. This depends on where the location of the common point is in each line segment, either the 2nd column for line segment 1 and the 1st column for line segment 2 or the 1st column of line segment 1 and the 2nd column for line segment 2.

[Image Analyst]

Not sure what you're doing - a before and after diagram might help. You aren't just doing the convex hull are you?

[Harold]

I've thought about using this but it won't work for polygon that have a dip. Image a triangle with a wedge taken out of the side. The convex hull will only draw a boundary that contains all the points. Actually my line connecting programming works. It's just that what I do afterwards won't work flawlessly unless I get rid of unnecessary points; i.e extra points from co-linear lines.

What I'm doing next is to create raster lines like what is shown here http://ars.els-cdn.com/content/image/1-s2.0-S016636151300002X-gr12.jpg

I've already developed code for this. First thing I do is take vertical lines spaced out at some spacing that I calculate dx = (xmax-xmin)/numdivision. I then just increment my x value by dx. I find all line segments where the current x value is between the x values of the line segments. I then calculate the y intersection value with these lines, using the equation of a line vectorized. Here's the part that messes up with the extra points. If the current x value happens to equal a x value of any line segments, the line is not included in the list for y intersection computation. If I can figure out another way of selecting the lines that get used in the y intersection calculation, then I don't need to get rid of the extra line segment points. However, I think that it would still benefit someone else and it's also better coding.

[Harold]

Ok, I think I have this program finished. I would still like to do some more testing with various polygon shapes and also with holes in the polygons. I would also still like to clean up the code a bit more because I do a couple cell2mat and mat2cell conversions. I want to see if I can re-write some of the operations I do as a cell function so I don't have to convert from cell to matrix to do them.