Solved

Unioning Regions

Posted on 1998-06-22
1
217 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

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

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.
Technology opened people to different means of presenting information, but PowerPoint remains to be above competition. Know why PPT still works today.
In this second Micro Tutorial in the series,  viewers will learn more basic shortcuts and functions of Illustrator. In this tutorial you will learn about the eyedropper tool, zoom , ellipses and more.
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…

738 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