CODEWITHSUNDEEP
algorithmgeometrycomputational-geometry
niro
niro

Reputation: 977

How to select outer line segments

I am having 2D line segments. My goal is to make different closed polygons. But, in here, I want to select most outer line segments when there are few parallel line segments stay closed to each other. with different line combinations, I can make different closed polygons.I was thinking and struggling to know how to get most outer lines as I need the polygon which make by outer most lines. (Polyogns are at the end constructed by intersecting adjoying line segments.) I was thinking to get a large bounding box containing all segments and get the centroid and then find the perpendicular distances to each line. In this process, I found nearby line segments which oriented close to each other (i.e. near parallel lines). So, from those nearby parallel lines I want outer most one. (that is red one). But If I used the centroid and compare the distnaces, then longest distance (among nearby parallel lines) does not give correct outer most line when more concave and convex turns exist as some cases outer most (red) one does not give by the longest distance. What I have is; end point coordinates of each line segments. (that is vector data)

So, I am looking for some good way to get most outer line segments from nearby parallel lines. For you to understand I have attached a sample data which i have. The most outer line segments are shown in red color. finally this red lines give me the boundary of my polygon. So, I want to get red lines out of corresponding nearby parallel black lines.

NOTE: My line segments are oriented into different direction. And not only to X & Y axes. Also, nearby lines donot make always 90 or 180 angles with adjacent lines.

please suggest me a method. thanks in advance

for example, if A,B and C,D are nearby parallel line segments. then outer most line should be B and C. But, If i compare distances from centroid (O), then I can get C as outer most, but B can not get as distance from O to B is smaller than O to A. My method fails in this type of spots. So, look alternatives..

enter image description here

Upvotes: 0

Views: 558

Answers (1)

Matteo Mannino
Matteo Mannino

Reputation: 399

A general way to find lines is using the Hough Transform.

http://en.wikipedia.org/wiki/Hough_transform

However, the sample data you give has lines parallel to the axes. I don't know if that is the nature of all of your data, but if it is then the Hough Transform basically breaks down to simply summing up the intensities by rows for lines parallel to the x-axis and summing by columns for lines parallel to the y-axis.

You will end up with two 1D arrays, one with row sums and one with column sums. Since the lines are black and the foreground is white, local minimums in these arrays will represent line locations along each axis. Since you only need the outer lines, you do not have to sum every column/row - just start at the edges of the image and compute the sums until you hit a local min. Once you have the line's placement on the axis, you can traverse that cut of the axis in the image to find the endpoints of the line.

Upvotes: 1

Related Questions