Solved

Unioning Regions

Posted on 1998-06-22
1
194 Views
Last Modified: 2010-04-06
How can I union a number of regions represented by a set of pints. The union is also represted by a set of points. Is there an algorithm for doing that. If there is, Please advice.

Thank you.
0
Comment
Question by:Zainal062797
1 Comment
 
LVL 10

Accepted Solution

by:
Jacco earned 50 total points
ID: 1112785
I presume you do 2D region unions.
And that the regions are closed paths.
The combined region is one region.
The drawing order of the point of all united regions is in the
same direction (i.e. clockwise or counterclockwise)

First you need a algoritm for PointInRegion (Windows supplies it PtInRegion). This algoritm will help you identifying point that do not ly within other regions (these points will not become part of the new region).

PointInRegion algoritm:

PointInRegion(X,Y)
- Draw a line from X,Y to outside the region (MinX-1,MinY-1)
- Count the number of times you cross the region lines
  (Iterate all line parts of the region and detect crossing)
  (be aware of the fact that your line might be parrallel to
   one of the lines in the region, prevent that)
Result = Even means the point is outside the region
Result = Odd means the point is inside the region

Union algorithm:

Union([regions])
- Mark all points that are in none of the other regions for deletion
  (some regions might be deleted completely)
- Choose a starting point from the non-deleted points
  (choose the first non-deleted point from a non-deleted region)
- Follow the points of the choosen region around and add them
  to your new region if the line added this way doesn't intersect
  with a line of the other regions.
  - if you end at the starting point this region is a stand alone
    and you should rechoose a start to continue
  - if a line crossing is detected create this cross point as a
    point of the new region step over to the region the crossing
    occured with at the point after the crossing



0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Keep your audience engaged and get the most out of your next presentation with these quick Prezi tips.
Technology opened people to different means of presenting information, but PowerPoint remains to be above competition. Know why PPT still works today.
In addition to being a great web-based presentation tool, Prezi also makes it easy to save your presentation as a PDF to share with others as well. Learn how in this tutorial. Select the share icon from the top menu in your Prezi editor: Select "D…
Illustrator's Shape Builder tool will let you combine shapes visually and interactively. This video shows the Mac version, but the tool works the same way in Windows. To follow along with this video, you can draw your own shapes or download the file…

707 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now