# Segment subtraction

This topic is 3343 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi there, What I am trying to do is a cut-down version of polygon outline CSG. For the polygon below (square) I have its vertices laid out in counter-clockwise direction. When I want to "carve" a certain section out of it (designated as red area), I need to re-generate polygon vertices taking into the account newly created carve-in segments (designated by curve Start->End). Original polygon vertices have their index in the array specified next to them. What do you think is the most optimal solution for "embedding" new curve vertices into polygon vertices list? I have tried standard List<T> Insert, but in case where Start > End (from end of polygon vertices list onto the beginning) this doesn't work. I also thought of implementing circular list so that vertices overbound will be clamped. Red region signifies vertices on polygon list that must not end up in modified list, start and end are points where incision occurs and ends up. The 1-4 numbers inside polygon indicate possible case scenarios, and this is where I am unsure what to do - do each case (8 total) separately, or try to figure out an algorithm for them all. This is possible since all cases share the same information, but I just cannot nail it down yet.

##### Share on other sites
What's your algorithm for deciding whether to retain the inside or the outside of the area? That is, what tells you that case 3 is not different than case 4? Is it always the case that one and only one vertex is "cut out?"

Assuming it's always that case that one/only-one vertex is to be removed, reverse the order of the Start-End array if End is on a line-segment that is not the "next" CCW line-segment starting from segment list[1]-list[0]; that is, after locating the insertion point for Start in the list, End must be on the next segment or the test fails. This test includes case 4 where the line-segments "wrap" to the beginning of the list. Then you can use a single algorithm to erase old and insert new.

Before the above test, list.push_back(list[0]) and push_back(list[1]) before that test, making the list "circular" and case 4 is not "special." When testing is done, pop the last 2 elements before you insert the new array.

1. 1
2. 2
3. 3
Rutin
21
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633654
• Total Posts
3013170
×