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

Outlines should be checked for crossovers #6

Open
davidcsterratt opened this Issue Jun 29, 2016 · 3 comments

Comments

Projects
None yet
2 participants
@davidcsterratt
Owner

davidcsterratt commented Jun 29, 2016

If an outline contains crossovers, these should be checked for and an error or warning returned.

@briancohn

This comment has been minimized.

Show comment
Hide comment
@briancohn

briancohn Aug 2, 2017

Contributor

outline_is_complex(outline) == is_complex(outline)

looking for intersection of any two line:

image

I wrote a line intersection function for a class project that achieves this:
https://github.com/briancohn/robo-movement-feasibility/blob/iss2/main.py#L40

Feel free to adapt to R!
you'd just have to do this:
Given:

list_of_outline_coordinate_pairs = list((123,154),(154,275), ... )

Apply line intersection check:

lapply(list_of_outline_coordinate_pairs, function(x) {
does_line_cross_with_any_other_point_excluding_self_and_neighbors(x, list_of_coordinate_pairs)
})
Contributor

briancohn commented Aug 2, 2017

outline_is_complex(outline) == is_complex(outline)

looking for intersection of any two line:

image

I wrote a line intersection function for a class project that achieves this:
https://github.com/briancohn/robo-movement-feasibility/blob/iss2/main.py#L40

Feel free to adapt to R!
you'd just have to do this:
Given:

list_of_outline_coordinate_pairs = list((123,154),(154,275), ... )

Apply line intersection check:

lapply(list_of_outline_coordinate_pairs, function(x) {
does_line_cross_with_any_other_point_excluding_self_and_neighbors(x, list_of_coordinate_pairs)
})
@briancohn

This comment has been minimized.

Show comment
Hide comment
@briancohn

briancohn Aug 2, 2017

Contributor

that said, this implementation would be ~O(n^2), where n is number of outline points but it probably would still run very quickly, and you could parallelize easily with parallel::mclapply

Contributor

briancohn commented Aug 2, 2017

that said, this implementation would be ~O(n^2), where n is number of outline points but it probably would still run very quickly, and you could parallelize easily with parallel::mclapply

@davidcsterratt

This comment has been minimized.

Show comment
Hide comment
@davidcsterratt

davidcsterratt Aug 9, 2017

Owner

Thanks Brian. I'd forgotten a bit about what the point of this issue was and this has prompted me to remember.

I think the algorithm you use is found in line.line.intersection() in geometry.R, which is used in remove.intersections(). This function is actually used in idt.connect.segments() for the idt format (but not the csv or ijroi formats). In this case the problem of intersections between crossing lines is fixed by adding new points, rather than been reported as an error or a warning.

I think the issue doesn't tend to arise in the ijroi format, as the ROI function in ImageJ doesn't (I think) allow crossovers anyway. In the CSV format things are less constrained.

I think we should probably implement the check, which would throw an error, for all formats, probably in Outline() (though I would retain the auto-fix in idt.connect.segments() for backwards compatibility). However, I think this is a job for the next iteration of Retistruct - even a change like this can throw up more questions.

Owner

davidcsterratt commented Aug 9, 2017

Thanks Brian. I'd forgotten a bit about what the point of this issue was and this has prompted me to remember.

I think the algorithm you use is found in line.line.intersection() in geometry.R, which is used in remove.intersections(). This function is actually used in idt.connect.segments() for the idt format (but not the csv or ijroi formats). In this case the problem of intersections between crossing lines is fixed by adding new points, rather than been reported as an error or a warning.

I think the issue doesn't tend to arise in the ijroi format, as the ROI function in ImageJ doesn't (I think) allow crossovers anyway. In the CSV format things are less constrained.

I think we should probably implement the check, which would throw an error, for all formats, probably in Outline() (though I would retain the auto-fix in idt.connect.segments() for backwards compatibility). However, I think this is a job for the next iteration of Retistruct - even a change like this can throw up more questions.

@davidcsterratt davidcsterratt self-assigned this Jun 8, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment