- Post Reply Bookmark Topic Watch Topic
- New Topic

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
all forums

this forum made possible by our volunteer staff, including ...

Marshals:

- Campbell Ritchie
- Liutauras Vilda
- Jeanne Boyarsky
- Devaka Cooray
- Paul Clapham

Sheriffs:

- Tim Cooke
- Knute Snortum
- Bear Bibeault

Saloon Keepers:

- Ron McLeod
- Tim Moores
- Stephan van Hulst
- Piet Souris
- Ganesh Patekar

Bartenders:

- Frits Walraven
- Carey Brown
- Tim Holloway

posted 1 year ago

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?

Thanks in advance.

ioannis

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,

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

Thanks in advance.

ioannis

Delaunay.png

posted 1 year ago

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?

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 wrote:In other words, I need a new SuperTriangle class,

hierarchically higherthan 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

posted 1 year ago

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?

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

posted 1 year ago

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.

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 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

posted 1 year ago

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.

posted 1 year ago

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?

posted 1 year ago

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.

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

posted 1 year ago

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?)

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?)

posted 1 year ago

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 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

posted 1 year ago

- 1

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.

posted 7 months ago

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.

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.

- Post Reply Bookmark Topic Watch Topic
- New Topic

Boost this thread!