Sorry to disturb,
but this is wrong.
Even within a Delaunay triangulation (without any constraint)
you may find query points whose nearest site is not a vertex
of the triangle in which they lie.
In the joint the example, the blue lines draw the Delaunay triangulation
while the red line draw the Voronoi diagram (showing for each site,
its set of closest points).
Every query point in the grey area has for nearest neighbor
a site which is not a vertex in its cell.
Furthermore,
it seems that what you are looking for is not
the nearest neighbor but the nearest visible
neighbor...
What is true is that if you were inserting your query point
in the constrained Delaunay,
the new triangulation would have an edge
between your query point and its nearest visible vertex.
So what you can do, is to use the member function
get_boundary_of_conflicts(Point q, .......),
where q is your query point,
look at all vertices on the output boundary
and get the closest to q :
this is the nearest visible vertex from q.
Tom Kazimiers wrote:
Damien,
thanks for your intrusion and clarification :)
Now, the problem is clear and I am happy that it is not a problem for me
since I needed not the geometrically absolute next vertex, but the
geometrically next vertex respecting constrains. So in your example I
would be lucky if NY is the result of the query. It seems that I made
myself not very clear in the first place, infact, what should one think
else by reading "nearest vertex" :) So thanks for the explanation and
the patience, I will surely need this at another place in my application.
Thanks and regards,
Tom
Damian Sheehy schrieb:
Hi Tom,
Pardon my intrusion - I think the attached image will help clarify
what Andreas is saying.
The thing to bear in mind here is the fact that a constrained Delaunay
triangulation is not fully Delaunay.
In other words, some (or all!) triangles in the triangulation may not
respect the Delaunay (empty circumcircle) property.
This is the case in the attached image; Denver is within the
circumcircle of the larger triangle.
You can clearly see that Denver is the nearest vertex to the query
point, however if you were to base your solution on the nearest vertex
of the enclosing triangle the result would be New York, which is wrong.
To get around this problem you can do the following; make a copy of
your constrained triangulation. Remove the constraints from the copy,
and then you can use it to perform nearest vertex queries.
I hope this helps.
Damian
On Tue, Feb 17, 2009 at 1:29 PM, Tom Kazimiers <
> wrote:
Hi Andreas,
thank you for your reply. If I sit on a vertex close to the constraint
isn't it the case that I get
a face that is on the constraints side the vertex is in? Actually, I
wonder if one face can be "crossed"
by a constraint so that some vertices are on one constraint side and
some on the other. I guess not,
since all faces are delaunay triangles. So if I get a face lieing
to the
"left" of the constraint through a
vertex lieing to the "left" of the contraint, all vertices of the face
should lie on the "left" side of the
constraint, don't they?
The solution I currently use relies at least on this assumption
-if this
is not true, it will not safely work, true.
A function called "closesst_vertex" does not exist for constrained
delaunay triangulations, so I go through
the face to the vertices.
But, maybe I understood something wrong :)
bye, and thanks,
Tom
Andreas Fabri schrieb:
> Hi Tom,
>
> If you have a constraint running from San Francisco to New York
City,
> and you sit on a vertex close to the constraint somewhere in the
middle
> of the US and the geometrically closest vertex is on the other
side of
> this constaint, then the function closest_vertex gives you either a
> vertex on your side or even the vertex of SF or NYC, but not
what you
> are looking for.
>
> andreas
>
>
> Tom Kazimiers wrote:
>> Hi,
>>
>> sorry to come back on this, but my question why my solution to
get the
>> nearest vertex to a given position
>> in a constrained delaunay triangulation is oversimplified is
not clear
>> to me.
>> Mariette said that the is not said that the nearest vertex to a
given
>> position has not to be a vertex of the face
>> I get by using "locate(position)". How can this be if it is a 2D
>> triangulation?
>>
>> Thanks in advance and regards,
>> Tom
>>
>> Tom Kazimiers schrieb:
>>> Mariette Yvinec schrieb:
>>>
>>>> Tom Kazimiers wrote:
>>>>
>>>>> Hello,
>>>>>
>>>>> as I am relatively new to CGAL I am not very familiar with some
>>>>> concepts
>>>>> or design decisions taken.
>>>>> For example have I currently the problem (or wish :P ) to
make fast
>>>>> "nearest vertex queries" on constrained delaunay triangulations.
>>>>> In the manual I found a "nearest_vertex ( Point p, Face_handle
>>>>> f=Face_handle())" method only for
>>>>> CGAL::Delaunay_triangulation_2<Traits,Tds> and this is what I
>>>>> would need
>>>>> in a constrained delaunay triangulation. Since I did not
find it I
>>>>> implemented it in the following way:
>>>>>
>>>>> // Typedefs CGAL
>>>>> struct K :
>>>>> CGAL::Exact_predicates_inexact_constructions_kernel {};
>>>>> typedef
>>>>> CGAL::Constrained_triangulation_face_base_2<K>
Fb;
>>>>> typedef
>>>>> CGAL::Exact_predicates_tag
Itag;
>>>>> typedef
CGAL::Triangulation_data_structure_2 <
>>>>> CGALLaunchSite<>, Fb > Tds;
>>>>> typedef
CGAL::Constrained_Delaunay_triangulation_2<K,
>>>>> Tds, Itag> CDT;
>>>>> typedef CDT::Vertex_handle
>>>>> Vertex_handle;
>>>>> typedef CDT::Face_handle Face_handle;
>>>>> typedef CDT::Point
PointCDT;
>>>>> typedef K::Vector_2
VectorCGAL;
>>>>>
>>>>> ...
>>>>>
>>>>> // Nearest vertex query
>>>>> PointCDT cgal_pos(position.x(), position.z());
>>>>> Face_handle handle =
>>>>> m_cdt.locate(cgal_pos);
>>>>> Vertex_handle v0 =
>>>>> handle->vertex(0);
>>>>> Vertex_handle v1 = handle->vertex(1);
>>>>> Vertex_handle v2 = handle->vertex(2);
>>>>> VectorCGAL vec0(v0->point(),
>>>>> cgal_pos);
>>>>> VectorCGAL vec1(v1->point(), cgal_pos);
>>>>> VectorCGAL vec2(v2->point(), cgal_pos);
>>>>> PrecisionType distance0 =
>>>>> vec0.squared_length();
>>>>> PrecisionType distance1 = vec1.squared_length();
>>>>> PrecisionType distance2 = vec2.squared_length();
>>>>> if (distance0 < distance1) {
>>>>> if (distance0 < distance2) {
>>>>> return &*v0;
>>>>> } else {
>>>>> return &*v2;
>>>>> }
>>>>> } else {
>>>>> if (distance1 < distance2) {
>>>>> return &*v1;
>>>>> } else {
>>>>> return &*v2;
>>>>> }
>>>>> }
>>>>>
>>>>>
>>>>> Is there any more easy or "convenient" way to do this? I ask
since a
>>>>> similar method exists for the triangulation without constrains.
>>>>>
>>>>> Thanks again and in advance,
>>>>> I hope that I did not miss anything in the manual :),
>>>>> Tom
>>>>>
>>>>> P. s.: Is there a way to make a constrained delaunay
"terrain" (e.
>>>>> g. a
>>>>> CDT with elevation, but that is only in XY space delaunay)?
>>>>>
>>>> your solution is oversimplified because the nearest vertex
need not
>>>> be a vertex of the face including the query location.
>>>>
>>>> The CGAL traits class Triangulation_euclidean_traits_xy_2
>>>> is designed to compute the elevation of
>>>> the Delaunay triangulation in xy space of 3d points.
>>>> It will lack of intersection test to compute a constrained
Delaunay
>>>> triangulation in xy space.
>>>>
>>>>
>>> Mariette,
>>>
>>> thank you for your answer. Why does the nearest vertex not
need to be a
>>> vertex of the face?
>>> If the (2D-) point is included in a face the nearest vertex
can only be
>>> part of it, could't it? If not, where could the nearest vertex be?
>>> (to clarify, I ment 2D space with a non-intersecting mesh -
sorry, I
>>> did
>>> not say this before)
>>>
>>> I also found the the traits class you mentioned (it was used
in the
>>> terrain example), but I see no way
>>> to insert it as a parameter for a constrained delaunay
triangulation.
>>>
>>> Thanks and regards,
>>> Tom
>>>
>>
>
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
------------------------------------------------------------------------
--
Mariette Yvinec
Geometrica project team
INRIA Sophia-Antipolis
|
