programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# Delaunay Triangulation

Greenhorn
Posts: 12
• Number of slices to send:
Optional 'thank-you' note:
Dear forum,

I'm in the process of creating the Delaunay Triangulation from a set of points on the plane. All points are processed unsorted one after another, that is, the triangle is searched on the existing triangulation, where the new point belongs in. For such a thing, I can imagine the method polygon.contains (). The problem is the three outer triangles, which consist of at least one of two fictitious points (they don't have concrete coordinates) with certain properties (are very far away from the whole set, etc ...). I want to extend the polygon.contains () so that it does not distinguish between triangle with or without fictitious points.

In other words, I need a new SuperTriangle class, hierarchically higher than Polygon, whose contains() will be able not only to traverse normal triangles with vertices with given coordinates, but also SuperTriangles, with fictitious vertices and still return true or false.

Is there an elegant way to do this without having to rewrite contains() from scratch?

ioannis
Delaunay.png

Marshal
Posts: 28271
95
• Number of slices to send:
Optional 'thank-you' note:

Ioannis Michailidis wrote:In other words, I need a new SuperTriangle class, hierarchically higher than Polygon, whose contains() will be able not only to traverse normal triangles with vertices with given coordinates, but also SuperTriangles, with fictitious vertices and still return true or false.

Conventionally one thinks of the Object class as being the "top" of the class hierarchy. So it sounds like you're trying to make SuperTriangle be a superclass of Polygon. But I think you really want SuperTriangle to be a subclass of Polygon. Am I right?

Is there an elegant way to do this without having to rewrite contains() from scratch?

Well, if you want SuperTriangle to be a subclass of Polygon whose contains() method works differently, then you're going to have to write a contains() method. However from your description if you want part of SuperTriangle's calculations to work the same as Polygon's calculation then it would be appropriate for SuperTriangle's contains() method to call "super.contains()" for that part.

Ioannis Michailidis
Greenhorn
Posts: 12
• Number of slices to send:
Optional 'thank-you' note:
Well, this point lies in the core of the question. I think that a SuperTriangle with some virtual vertices is a Superclass of a normal triangle and not vice versa. I am afraid if I simply extend Polygon, consequently bad things will happen..

Is there no pattern in which a subclass "becomes" a superclass?

Paul Clapham
Marshal
Posts: 28271
95
• Number of slices to send:
Optional 'thank-you' note:

Ioannis Michailidis wrote:Well, this point lies in the core of the question. I think that a SuperTriangle with some virtual vertices is a Superclass of a normal triangle and not vice versa. I am afraid if I simply extend Polygon, consequently bad things will happen.

It's fairly easy to figure out whether Polygon is a subclass of SuperTriangle. Ask yourself: "A Polygon IS-A SuperTriangle... true or false?" To me that's false, because presumably a square isn't a SuperTriangle. (I'm assuming these are the ordinary triangles and polygons familiar to Pythagoras and so on.) Now let's try this: "A SuperTriangle IS-A Polygon... true or false?" Well, yeah, obviously. So SuperTriangle is a subclass of Polygon.

Is there no pattern in which a subclass "becomes" a superclass?

Nope.

But I don't understand what these bad things are which you are afraid of. A SuperTriangle is a Polygon, except it behaves differently in some way. You would take care of those differences by overriding methods.

However... if adding SuperTriangle to your data model causes Polygon to not work correctly, then yes, you'll have to fix Polygon in some way to take care of that.

Ioannis Michailidis
Greenhorn
Posts: 12
• Number of slices to send:
Optional 'thank-you' note:
The way from Polygon to SuperTriangle goes through two steps. Triangle -> Polygon -> SuperPolygon. For normal Polygons/ Triangles, those familiar to Archimedes, a Triangle IS A Polygon. However, I am interested in the second part, you are right, I should have called my new class SuperPolygon for clarity. A Polygon knows if it contains a point, by traversing all of its clearly definded edges and checking if the point always lies on the right. A SuperPolygon should be able to do that also with non-defined virtual vertices/edges. For me a Polygon IS A SuperPolygon, and therefore a Subclass of SuperPolygon.

Bartender
Posts: 5491
212
• Number of slices to send:
Optional 'thank-you' note:
Why must a polygon  be a subset of this superpolygon? Why not simply have a superpolygon with fields polygon and a List of virtual points? And how does such a virtual point look?

Paul Clapham
Marshal
Posts: 28271
95
• Number of slices to send:
Optional 'thank-you' note:
I have this part of my brain which works on problems when I've already decided not to work on them. And then this afternoon it popped up and told me what you really meant. Similar to what Piet said, it looks to me like you really need to modify your Polygon class to allow both (real) points and fictitious points.

At least that's one possibility. Your suggestion of having SuperPolygon as that class which can have real and fictitious points, and Polygon as a subclass which can only have real points, that's another possibility. But when one class is a specialized version of its superclass, that can be a design error. For an illustration of what I mean, consider a Rectangle class with width and height attributes. And then consider a specialized subclass of Rectangle called Square, which would somehow force the width and height to be the same. For an explanation of why that's a problem, have a look at A Square Is Not a Rectangle, written by somebody far better than me at object-oriented design.

So that's why I would suggest tearing apart Polygon and making it work with fictitious points. But I don't know a lot about your class design, so there might be reasons why it's not a design error.

Ioannis Michailidis
Greenhorn
Posts: 12
• Number of slices to send:
Optional 'thank-you' note:
You guys are suggesting composition over inheritance? When I get to this crossroad, instinctively I go over Composition over Inheritance I am a little on the fence with this, but I would rather take inheritance.

Going for virtual points without coordinates doesn't bring us any further. The point location structure D will be some kind of DAG with the leaves corresponding to the current triangulation and the internal nodes to triangles that were in the triangulation at some earlier stage. The algorithm will work his way from the first triangle P0 P-1 P-2 through to the current triangle containing the new point, some of these triangles will consist of virtual points as well. The only way I see for a class to be able to answer the contains() question is for it to be a SuperPolygon knowing its position in the DAG (the virtual points are only two and in a galaxy far, far away from the rest of the set...)

The current Polygon class is simply Polygon You are suggesting I should mess with it (how?)

Paul Clapham
Marshal
Posts: 28271
95
• Number of slices to send:
Optional 'thank-you' note:

Ioannis Michailidis wrote:The current Polygon class is simply Polygon You are suggesting I should mess with it (how?)

Well, now that I know it's a standard class from the API, I wouldn't suggest messing with it (since you can't). You didn't mention that originally, which therefore made my advice less useful.

So now I don't know what to suggest. But that's mostly because I don't know what you've already done. If the Polygon.contains() method doesn't work for you and you don't have any other code already in place which you're supporting, then maybe write your own Polygon class. But if the only reason you need a version of Polygon is to use the contains() method, then maybe write a contains() method in your own code which works for you.

Ioannis Michailidis
Greenhorn
Posts: 12
• 1
• Number of slices to send:
Optional 'thank-you' note:
I am in the preimplementation phase, working on how to go about it. Everything is still open and there can always be a shorter, more elegant way, this is why I appreciate the exchange of ideas with you guys.

Ranch Hand
Posts: 133
12
• Number of slices to send:
Optional 'thank-you' note:
Well, I wish I'd seen this discussion back when your originally posted it.  I regret that I couldn't reply sooner.

I encountered this problem in my own Delaunay Triangulation (triangle mesh) implementation, including the special case of a triangle with a fictitious vertex.

I think your best solution would be to simply implement your own contains method from scratch.   First off, none of the standard polygon classes are going to understand the idea of a fictitious vertex (for everyone else: triangles with fictitious vertices are often used in Delaunay Triangulations to handle the region outside the bounds of the triangle mesh).   Second off, because the triangle has special properties (it's always a convex polygon, it has a fixed number of sides), it's easy to code a custom contains() method.  For example,  simply test a point against each edge to see if it is on the left or right side of the edge.  If you know that the triangle is oriented counterclockwise, then an inside point must lie to the left of each edge (always left or always right, a mix means the point is exterior).  If the triangle is clockwise, the point must be to the right.  And if you don't know the orientation, just recall that the inside point must be on the same side of each edge.  In the case of your fictitious triangle test, you would perform the left/right-side test for the true edge and then try dropping the point down to the edge line to see if lies within the segment.  Of course, there are complicating factors in this because an exterior point could lie in the pie-shaped wedge between two exterior border segments.

If you look at the GeometricOperations class in the Tinfour Project you will find some code related to this computation.  In Tinfour, all the triangles are always oriented counterclockwise, so you would have to make adjustments for your own logic.

 Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters?