Solved

Unioning Regions

Posted on 1998-06-22
1
222 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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

[Webinar] How Hackers Steal Your Credentials

Do You Know How Hackers Steal Your Credentials? Join us and Skyport Systems to learn how hackers steal your credentials and why Active Directory must be secure to stop them. Thursday, July 13, 2017 10:00 A.M. PDT

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Keep your audience engaged and get the most out of your next presentation with these quick Prezi tips.
Many programs have tried to outwit PowerPoint in terms of technology and skill. These programs, however, still lack several characteristics that PowerPoint has possessed from the start. Here's why PowerPoint replacements won't entirely work for desi…
Add visuals to your Prezi to keep your audience engaged. Learn how to embed images, edit them, and more in this video micro tutorial. Select "Insert" from the top menu in your Prezi editor: Select "Image": A toolbar will pop in from the right …
It’s easy to embed any of your public Prezi presentations on your website or social network to share with others. Learn how simple it is in this tutorial.
Suggested Courses

623 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