Menu
Avast there fellow programmers!
I have the following problem:
I have two rectangles overlapping like shown on the picture below.
I want to figure out the polygon consisting of point ABCDEF.
Alternate christmas description: The red cookie cutter is cutting away a bit of the black cookie. I want to calculate the black cookie.
Each rectangle is a data structure with 4 2d-vertices.
What is the best algorithm to achieve this?
850
Booleans (Mesh > Booleans) let you model with polygonal objects. Three boolean operations let you combine objects to make shapes that would otherwise be difficult to model using other techniques. You can add, subtract, or intersect objects to create a new, complex shape.
What are the three Boolean operations? Union, subtract, and intersect.
Some Types of Boolean Operators Logic operators or conditionals could be: Denial: It is NOT fulfilled. Conjugation: One thing AND another is fulfilled. Disjunction: One thing OR another is fulfilled.
In 3D Modeling, by Boolean operations we mean creating intersections and unions of objects, as well as subtracting objects from each other. All these are set operations that students know from Venn diagrams.
This is a special case of general 2D polygon clipping. A good place to start is the Weiler-Atherton algorithm. Wikipedia has a summary and links to the original paper. The algorithm seems to match the data structure you've described pretty well.
Note that it's quite possible you'll end up with a rectangle with a hole in it (if the red one is entirely inside the black one) or even two rectangles (eg if the red is taller and skinnier than the black). If you're certain there is only one corner of the red rectangle inside the black one then the solution should be much simpler.
58
constructive solid geometry
39
How precise are the coordinates? If the rectangles are fairly small, the easiest approach might be to just paint them on a canvas, black rectangle first, followed by red. The remaining black pixels on the canvas are the polygon that's left.
Another approach is to split the coordinate grid into a bunch of rectangles based on all of the sides of the rectangles (not counting unbounded rectangles, you have up to 9 rectangles generated if you have two original rectangles). Then just test a representative point from each of these rectangles for membership in the particular polygons to determine which rectangles are in and which are out.
33
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
