Algorithm for constructing geometric outline for intersecting geometric objects

[aidz15]

Hello Everyone!

Hi I'm a newbie here and I would like to ask for some help regarding my problem. You see, we need to develop a program that will trace the outline of circuit tracks in a circuit board. We already parsed the PCB file as an intersection of rectangles and circles. The thing is we need to create the outline of those intersections and save them on a output file. We think that a plane sweep algorithm must be used but we do not know how to implement it.

Please help us. We badly need it.

Thanks!

[exception]

What is your "outline"? A (counter-clockwise) set of line- and circle segments? How is the geometry represented?
You certainly don't *have to* use a plane sweep algorithm (or were you asked to?), but it might be the fastest/easiest or whatever attribute you want (divide and conquer should work equally well).

And if the problem is what I think it is: just apply the general PS approach - sort lexicographically, insert into elements into y-structure (balanced tree) when performing the sweep (think about what your event points are, and what has to be in the y-structure when processing them. They have to be constructed 'on the way', like in Bentley-Ottmann's line intersection algorithm ). Why don't you write down an algorithm outline? We will help you fill the gaps.

[aidz15]

Hi exception! Thanks for your prompt reply!

I have a CSV File that stores the coordinates of rectangles and circles. Some of these geometric figures are interconnected with each other. So basically, these are the list of all geometric shapes(rectangles and circles to be exact). What we need to do is process this to determine:

1) Those who are interconnected to each other
2) Produce the outline by of those interconnected segments/arcs by eliminating unnecessary lines and arcs.

Is there any way to contact you? So I could send you the project that we have been working on. Thank you and God bless.

[exception]

I have a CSV File that stores the coordinates of rectangles and circles.

There are several ways to store circles and rectangles. You can give a minimal and maximal point for a rectangle if it is parallel to the coordinate system. Or you can store all 4 vertices. You can describe a circle by a center and a radius. Or you can store three arbitrary but distinct points on it.
90% of the work is describing the problem exactly. You didn't do it yet. (The list of questions arising goes on: how are the distinct elements connected? Explicitly or by overlapping coordinates? ...) State your problem in a precise and brief manner, otherwise you won't get much usable help.

Produce the outline by of those interconnected segments/arcs by eliminating unnecessary lines and arcs.

So you don't have to construct anything, only delete parts? If e.g. two circles overlap, the arcs making up the parts divided by the intersection points already exist? (contradiction to your first statement. Again, be precise, since otherwise I have no clue what you want to do or what your problem is)

I could send you the project that we have been working on

No, thanks - (a) I have enough projects on my own (b) while I'm glad to help, I won't do the work for you (c) if solved on the board, the question doesn't have to be answered twice.

[aidz15]

Thanks again for your reply exception.

The csv file contains the following:
For rectangles, all their four vertices and for circles, their center points and radius.


The rectangles and circles are interconnected by overlapping edges or arcs or simply put overlapping each other.

The list in the csv files are not yet sorted (they are not yet grouped into which are intersecting)

So this is my problem:

I need to group those objects in the list based on if they intersect or not. These grouped objects that are interconnected to each other will be called paths.

I need to trace the outline of these paths by determining their intersections and deleting unneeded arcs and lines (those who are inside the rectangle or circle).

Finally, i need to store the coordinates of this outline to a file.

Thank you so much for your time!:)

[aidz15]

I hope you guys can help me! :) Please.

[exception]

Now you're talking! So, you already made out the two big steps:
(I) group overlapping objects
(II) compute the outline (it is still not completely clear, how exactly it is stored: "the coordinates" would be pretty clear if no arks were contained. But since they are, I'd rather make it up from line segments and arks)

For part (I), is anything unclear to you or do you know how to do that? If you don't: what is the missing part and what are your ideas so far (again, be brief, but exact, please)?

For part (II), which seems to be your original question, again, what are your ideas so far? You already mentioned that you wanted to use a plane sweep algorithm. Do you know the line segment intersection algorithm of Bentley and Ottmann? If not, have a look at it. It should give you a pretty good idea how to solve the problem for the rectangles. If any questions are left, you can always ask.

One last thing. Does the result have to be exact? 'double'-arithmetic tends to get pretty ugly in these applications and if your number of objects is rather big, you don't want to use exact rational arithmetic all along. In that case, I'd implement the algorithm as a template taking a Field Number Type; then you can test it with rational arithmetic and if everything is fine you can switch to floating point filters (however, you should not perform construction tasks (like intersection point computation) from the given input as long as possible, but only decision making, since construction always requires an exact number representations).

Edit: You also might want to have a look at CGAL. It might already implement all you need.

[aidz15]

For Part (I), I think I could do that by using brute force which is very time consuming. So far, that what I am considering. But again I think the sweepline algorithm is the most efficient way of doing it but unfortunately I do not know how to implement it.

I think the result should be exact because I need to find the intersection points as to generate the outline of the path.

I think the outline can be stored as a group of line segments and arcs.

Admittedly, I'm a novice in C++ so I hope you can help me.

[exception]

The algorithm has nothing to do with C++.

For (I), think about interval intersection, which can be done in O(n log n) in a "line sweep". Brute force would require O(n²). You can use a similar strategy in two dimensions, using the extreme points of the projections onto the coordinate system axis.
And you *do* know that plane sweep is a category of algorithms, not a readily available program you can execute, right?

I think the result should be exact because I need to find the intersection points as to generate the outline of the path.

This would make things really hard, if you don't want to use a rational type all the time (which is really slow). Therefore, you should substitute thinking by knowing.

Did you read and understand the algorithm I mentioned? It will make some things clearer.

[aidz15]

Yup! I'm studying it right now.

Thanks man! I will get back to you as soon as I understand it.